Transcript Document

Island Network Analysis
MSTs and Dominating sets
By Aaron Desrochers
1
Every network system created by man or by nature, has a corresponding graph
model of that system. For example, one can take a group of islands and create
a plethora of different types of graphs, as shown by anthropologist Per Hage
and mathematician Frank Harary in their co-written books Island Networks
and Exchange in Oceania.
I will highlight two graph theoretic concepts; the use of minimum spanning
trees and dominating sets, and their applications to anthropology and
2
archeology.
Oceania is located to the
northeast of the continent of
Australia.
Around 1500 B.C, travel between these islands was a necessary part of survival
for the people of Oceania. In the study of these early cultures, archeologists and
anthropologists can use graph theory to verify their research on the spread of
different cultures and also better understand interactions between islands in
an island network.
3
Some definitions
A spanning tree of a graph G is a subgraph of G that is a tree containing all the
vertices of G.
In a weighted graph, a minimum spanning tree is a spanning tree whose sum of
edge weights is as small as possible. It is the most economical tree of a graph with
weighted edges.
3
1
1
3
1
3
12 4
1
2
5
1
2
4
2
1
3
2
1
4
1
2
5
1
2
4
2
4
D
G
C
A
E
B
F
A
B
C
D
E
F
G
A
*
1
1
1
0
0
0
B
1
*
1
0
1
1
0
C
1
1
*
1
1
0
1
D
1
0
1
*
1
0
1
E
0
1
1
1
*
1
1
F G
0 0
1 0
0 1
0 1
1 1
* 1
1 *
An Adjacency Matrix of an undirected graph is a (0,1)-matrix with a one for
vertexes that are adjacent and a zero for those vertexes not adjacent.
When a graph is weighted one can use a similar adjacency matrix, where the
value of the edge between two vertexes is recorded instead of a one to find a
minimum spanning tree.
5
Long ago, travel between the islands of Oceania was hazardous, mainly because
the boats used were nothing more than wooden canoes. So traveling islanders
would island hop as much as possible during their long sea voyages, traveling
the shortest distances possible in their necessary interaction between other
islands.
Thus, a finding a minimum spanning tree of an island networks gives us the
paths that ancient islanders paddling wooden canoes would have taken
thousands of years ago.
MSTs have been used to verify archeological data that show the spread and
influence of cultures in different island clusters in Oceania.
6
Trees in Oceania
([2] page 6)
Even before the study of graph theory began, the early
natives of Polynesia used a tree to illustrate the hierarchy
in their society.
7
Minimal Spanning Trees
One can turn an island cluster into a complete graph with paths from
each island to all of its neighbors. The distance between these islands
can be measured very easily and applied as weights to the edges of the
graph. From this we can construct an adjacency matrix, and from this
matrix we can find with a minimum spanning tree that hits all the
G
islands.
10
D
A
4
3
9
7
1
6
2
3
3
3
1
6
C
5
2
6
2
F
2
B
4
E
10
12
8
A
B
C
D
E
F
G
A B
* 3
3 *
1 2
4 6
6 4
9 10
10 12
C
1
2
*
2
2
5
7
D
4
6
2
*
3
3
3
E
6
4
2
3
*
2
6
• Prim’s algorithm states: Setting n= to the number
of vertices, repeat the following step until the tree
T has n-1 edges: Add to T the shortest edge
between a vertex in T and a vertex not in T
(initially pick any edge of the shortest length).
F G
9 10
10 12
5 7
3 3
2 6
* 1
1 *
Here n = 7; T will have 6 edges
G
10
A
D
4
3
9
1
6
7
2
3
1
6
3
3
C
5
2
6
2
F
2
B
4
E
12
10
9
D
A
1
2
1
C
2
2
F
2
B
E
This minimum spanning tree is simple to find, but it has a very interesting
application in anthropology. The paths between the islands in the MST were
the safest and thus the most traveled by the ancient mariners of Oceania.
10
DOMINATING SETS
According to Hage and Harary, “solutions to
many network problems can be found by
decomposing a graph into sub graphs…. In
certain types of communication problems, a
graph may be decomposed into its dominating
sets.”
A dominating set S of a graph G has every node (vertex) of G either in
it or adjacent to it. Consider this graph.
{1,6,8,9} is a
dominating set
[2] page 205
11
The Five Queens problem
A good example of a dominating
set is the Five Queens problem in
chess. How can one position five
Queens on a chess board so that
they command or occupy every
square on the board without
threatening each other?
12
Another important feature of
dominating sets, the minimum
dominating set, illustrated by
the 5 Queens problem is:
“ There may also be six, seven,
or eight Queens in a minimal
dominating set (so that the
removal of one Queen leaves a
non-dominating set). Hence the
five Queens constitute a
minimum dominating set. ”
The set {1,8,9} is a minimum dominating set.
[2] page 205
13
Harary defines independent
dominating sets as a set in which no
nodes are adjacent.
{1,4,7,10} is an independent
dominating set.
[2] page 205
One can look at the number of nodes in each set and determine a
domination number. The domination number  (G ) is “the smallest
number of nodes in any dominating set, hence it is the cardinality of
a minimum dominating set.
In the graph on the previous slide,  (G ) =3
Lastly, “the
independent domination number  ' (G) is the smallest number of
nodes in any independent dominating set.  '(G)  4
14
How does Domination apply in Oceania?
Hage and Harary apply the concept of dominating sets in the
western Caroline Islands in order “to analyze distributional
aspects of power relations.” They assume that, “given the
traditions of warfare, conquest and hierarchy in the
Carolines…all the islands in the network were either
dominated or dominating.” According to Harary  (G ) and
, '(G)  4 ,so there must be 4 dominating islands in the
network.
15
“Elato and Satawal paid tribute to Lamotrek in return for the right to exploit
neighboring uninhabited islands for marine recourses.”
“Puluwat dominated, through conquest and colonization, the neighboring
islands of Pulusuk, Pulap, and Namonuito”
“Ulithi dominated Fais and Sorol in an informal but fundamental way: These
two islands, alone amoung all others in the western Carolines, had, at an early
date, lost their navigational skills and had to rely on Ulithi for communication
with all other islands.”
Since dominating islands do not threaten each other, either Woleai or Ifaluk
must make up the last member of the independent dominating set.
16
“Woleai did not dominate its neighbors in the recent past but
instead turned in on itself and developed an intra-atoll
structure…We suppose that either Woleai dominated
Eaurpik, Faraulep, and Ifaluk or that Ifaluk dominated
Eaurpik, Faraulep or perhaps most likely, that Woleai and
Ifaluk dominated at different times.”
17
Class Exercise
A
H
D
E
B
I
C
G
F
Find an independent dominating set and minimal dominating set
in this make believe island network.
{B,E,I} and {A,F,H} are independent
dominating sets with  '(G)  3 they are
also a minimal dominating set.  (G ) =3
J
18