Transcript EE681_Grover_Module4

E E 681 - Lecture 4
Graph theory and routing
(initial background)
W. D. Grover
TRLabs & University of Alberta
© Wayne D. Grover 2002, 2003
Graph terminology / concepts
• A graph consists of a finite set of vertices (“nodes”) and a
set of edges (“spans”), such that each edge joins a pair of
nodes.
• Nodes are adjacent if they are joined by an edge.
• Such an edge is incident on the nodes it connects.
• A graph is simple if it has no parallel edges or self-loops.
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
2
Graph terminology / concepts
• A graph with parallel edges is called a multigraph.
• A graph in which a number is associated with every edge is
called a weighted graph or “capacitated”.
• An edge is directed if its vertices are an ordered pair.
• The number of spans incident on a vertex is called the
degree of the node.
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
3
Graph terminology / concepts
• A path is a connected edge sequence in which all edges are
distinct.
• If all vertices are also distinct (except possibly the origin
and terminus vertices) the path is called simple.
• If the vertices in a cycle are distinct it is called a simple
cycle or circuit. (Note this implies that all edges in the
sequence of the walk are also distinct.)
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
4
Routing and flows in transport networks
B
A
Span A-B
a unit-capacity
link
B
F
A
Route - ~ geographical
Bandwidth management
or cross-connection
facility at the link-unit
capacity level
C
a path
u te
its ro
G
D
E
path - ~ signal over
a route
span - ~ transmission
systems
link - ~ unit bandwidth
unit hop
Need to be attentive to these terms
for precise communication
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
5
Hamiltonian and Eulerian Cycles
(a) a Hamiltonian cycle visits all nodes once,
not necessarily traversing all spans
(b) an Eulerian cycle crosses all spans
once, but may revisit nodes
• A cycle that connects all of nodes once, is a Hamiltonian
cycle.
• A cycle that traverses all edges once (but may revisit nodes)
is an Eulerian cycle.
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
6
Hamiltonian Cycles
• the question: “does graph G contain a Hamiltonian cycle?”
is an NP-complete decision problem.
– Hamiltonians are more likely in highly connected networks.
– any graph of N nodes where every node has degree > N/2 is
Hamiltonian
• Q. What would be the significance for transport network
design?
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
7
Eulerian Cycles
• An Eulerian cycle exists (and requires that) every node have
even degree
• Q. What would be the significance for transport network
design?
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
8
Isomorphism and Homeomorphism
• Graphs G and H are isomorphic if a 1:1 correspondence can
be constructed between nodes in G and H for which: if there
is an edge between two nodes in G then there is also an
edge between the corresponding nodes in H.
(i.e., topological equivalence )
•
Graphs G and H are homeomorphic if they can be
isomorphic only by adding or deleting degree-2 nodes from
edges.
– relevance to mesh network design and ring-mesh hybrids.
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
9
Homeomorphism
(a)
(b)
(c)
Three networks that are homeomorphic
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
10
Planarity
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
11
Planarity - “Euler’s Formula”
• A connected planar graph divides the plane into nonoverlapping faces, some bounded (i.e., those interior to the
graph) and some unbounded (at an outside edge of the
graph),
• the number of faces |F| is related to the number of nodes |V|
and edges |E| of any planar graph:
|F| = |E| - |V| + 2
|E| = 9
|V| = 5
 |F| = 6
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
12
Trees, spanning trees
A graph G
A tree on G
A spanning tree on G
• Q. Significance
– to data communications ?
– to survivability ?
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
13
Two-connected and bi-connected graphs
(a)
(b)
A bi-connected network (a)
has no degree-one
Bi-connected
connected
points(c).
(c)
sites
(b) and no articulation
Two-connected
(has a “bridge” node)
or “articulation point”
This graph that is not
connected
E E 681 - Lecture 4
© Wayne D. Grover 2002, 2003
14
Data structures for representing graphs
node
node
• Incidence matrix
Contains a “1”
where edge exists
“0” otherwise
Q. Directed
vs. Undirected
graphs?
• Adjacency list:
node node distance (etc.)
e.g. “snif”
file format
E E 681 - Lecture 4
List contains entries only
for edges that exist
© Wayne D. Grover 2002, 2003
15
Distinct and disjoint routes
(a) disjoint
0
(a) span-disjoint
0
1
2
1
2
3
14
14
13
3
13
6
14
13
6
5
9
5
8
9
7
8
7
10
10
7
10
4
4
11
12
“disjoint” = fully disjoint
(nodes and spans)
E E 681 - Lecture 4
6
5
8
12
1
2
3
9
(a) distinct
0
4
11
“span disjoint” =
may have common nodes
© Wayne D. Grover 2002, 2003
12
11
“distinct” =
just different in
at least one detail
16