A graph consists of two sets, V and E
G = (V,E)
V is a finite, nonempty set of vertices
E is a set of pairs of vertices called edges
Directed Graphs (digraphs) -- the edges are ordered pairs of Vertices (arrows indicate direction) <u,v>: u is the tail and v is the head of the edge u --> v.
|
|
|
|
|
Two vertices u and v in an undirected graph are called adjacent if there is an edge from the first to the second. The edge (u,v) is incident on vertices u and v.
In the undirected graph of panel (a), vertices 1 and 2 are adjacent, as are 3 and 4, but 1 and 4 are not adjacent.
A path is a sequence of distinct vertices, each adjacent to the next. Panel (b) shows a path.
A cycle is a path containing at least three vertices such that the last vertex on the path is adjacent to the first. Panel (c) shows a cycle.
 |
 |
 |
For directed graphs we can make similar definitions.
We require all edges in a path or a cycle to have the same direction, so that
following a path or a cycle means always moving in the direction indicated by
the arrows.
Such a path (cycle) is called a directed path (cycle). A directed
graph is called strongly connected if there is a directed
path from any vertex to any other vertex.
A weakly connected graph is where the direction of the graph is
ignored and the connectedness is defined as if the graph was undirected.
The directed graphs in panels (b) and (c) show pairs of vertices with directed
edges going both ways between them.
Since directed edges are ordered pairs and the ordered pairs (v,w) and
(w,v) are distinct if v != w, such pairs of edges are
permissible in directed graphs. Since the corresponding unordered pairs are
not distinct, however, in an undirected graph there can be at most one edged
connecting a pair of vertices. Similarly, since the vertices on an edge are
required to be distinct, there can be no edge from a vertex to itself.
(Although we shall not do so) sometimes these requirements are relaxed to allow
multiple edges connecting a pair of vertices and self-loops connecting a vertex
to itself. (page 115)
More definitions:
Subgraphs: page 115 and figures on 116
A connected component (or simply a component) H of an undirected graph is a maximal connected
subgraph. By maximal, we mean that G contains no other subgraph that is
both connected and properly contains H. (figure 2.28)
Note: G4 is disconnected but it has two connected components H1 and H2.
A strongly connected component is a maximal subgraph that is strongly
connected. (figure 2.29) Note here that G3 is not strongly connected, but it has two strongly connected components.
Note that when we talk about simply connected it is usually undirected graphs since for directed graphs we
say either strongly or weakly connected. Also note that the definition of being strongly connected components does not say that the subgraphs that make them up must union to make
the entire original graph, rather just what are the components that are maximal.
| Application | Verticies | Edges |
| Circuit Networks | Points of Connection | Component Wires |
| Transport Networks | Stations | Routes |
| Maps | States/Regions | Adjacency Relations (e.g. Graph Coloring) |
| Program Flow Analysis | Procedures/Modules | Calls |
Finding shortest paths, project planning, identification of chemical compounds, statistical mechanics, genetics, linguistics, etc.
Graph Implementations (section 2.6.3)
Keep in mind graphs on page 114 for examples
FirstImplementation: Adjacency Matrix
Connected vertices on a graph are ordered pairs in a matrix. (for weighted
these are values) Figure 2.30
Positive: easy to visualize
Negative: often sparse, waste time and space
How many edges? Is it connected? O(n2)
 |
| Scan for nodes with increasing radius |
Depth-first search (DFS):
Roughly analogous to preorder traversal of an ordered tree(Note section 6.1). Consider visually (and for trees).
See algorithm and description on page 324. Also see analysis. O(n+e)
 |
| include edges into simple path as long as possible. Back up and try again |
Example from text
Connected components:
If G is an undirected graph, then one can determine whether or not a
graph is connected by simply making a call to either DFS or BFS and then
determining if there is any unvisited vertex.
The set of connected components of a graph can be obtained by making repeated
calls to either DFS or BFS on vertices which are not in a connected component
yet.
Spanning trees
When the graph G is connected, a depth-first or breath-first search
starting at any vertex visits all the vertices in G. In this case the edges of
G are partitioned into two sets T (for tree edges) and N (for nontree edges),
where T is the set of edges used or traversed during the search and N the set
of remaining edges.
The edges in N can be classified as cross edges or back edges
Any tree consisting solely of edges in G and including all vertices in G is
called a spanning tree.
See figures 6.5 (DFS and BFS spanning)
Note: If a nontree edge is introduced into any spanning tree, then a cycle is
formed. Hence we do not add them and call them back edges or cross edges.
Some significant properties:
Claim: depth-first spanning trees have no cross edges
A spanning tree is a minimal subgraph, G', of G such that V(G') = V(G)
and G' is connected. (A mimimal subgraph is one with the fewest number of
edges.)
Finding minimal subgraphs is a very common type of problem. (e.g.,
communication networks, traveling salesperson problem)
Biconnected components
A vertex v of G is an articulation point iff the deletion of v,
together with the deletion of all edges incident to v, leaves behind a graph
that has at least two connected components.
A biconnected graph is a connected graph that has no articulation
points.
Figure 6.6 is not biconnected, 6.7 is biconnected
Articulation points are undesirable in graphs that represent communication
networks. Why?
A biconnected component of a connected graph G is a maximal biconnected
subgraph H of G. By maximal, we mean that no other subgraph that is both
biconnected and properly contains H. ( Biconnected components of graph shown in Figure 6.6)
The biconnected components of a connected, undirected graph G can be found by
using any depth-first spanning tree of G.
See pages 329-333.
U is an articulation point iff
(1) u is either the root of the depth-first spanning tree that has two or more children
(2) u has at least one child, w, such that it is not possible to reach
an ancestor of u using a path composed soley of w, descendents of w, and a
single back edge.
consider and do the depth-first tree
Assume nodes are labeled according to depth first numbering
Let Low(w) = smallest depth first number which can be reached using a path containing descendents of w and at most one back edge. graph 9 with low
Now, someone smart looked at this and made a nice recurrence relation for you:
Low(w) = min{dfn(w), min{Low(x)|x is a child of w}, min{dfn(x)|(w,x) is a back
edge} }
so
U is an articulation point iff
(1) u is either the root of the spanning tree that has two or more children
(2) or u is not the root and u has a child w such that Low(w) >
dfn(u).
See Figure 6.9: (a) has dfn, (b) has DF Spanning tree, Low[1:10] = {1,1,1,1,6,8,6,6,5,4}
Node vertex 3 is an articulation point as it has a child 10 such that low(10) = 4 > 3 = dfn(3).
Node vertex 2 is an articulation point as it has a child 5 such that low(5) = 6
> 6 = dfn(2)
Node vertex 5 is an articulation point as it has a child 6 such that low(6) =
8 > 7 = dfn(5)
Consider vertices 1,4,5
Node vertex 4 is not an articulation point since it is possible to reach
an ancestor via a child of 4: descendent 3, descendent 2, and a back edge.
Function DFS is easily modified to compute dfn and low for each vertex of a
connected graph. (Algorithm 6.9)
Once articulation points are determined, biconnected components can be found
All edges will be either
Communications Breakdown Analysis
Find maximal biconnected components and articulation points
