A graph G is a pair, G ¼ (V, E), where V is a finite nonempty set, called the set of
vertices of G and E V V . That is, the elements of E are pairs of elements of V. E is
called the set of edges of G. G is called trivial if it has only one vertex.
Let V(G) denote the set of vertices, and E(G) denote the set of edges of a graph G. If the
elements of E are ordered pairs, G is called a directed graph or digraph; otherwise, G is
called an undirected graph. In an undirected graph, the pairs (u, v) and (v, u) represent
the same edge.
Let G be a graph. A graph H is called a subgraph of G if V(H) ? V(G) and
E(H) ? E(G); that is, every vertex of H is a vertex of G, and every edge in H is an
edge in G.
A graph can be shown pictorially. The vertices are drawn as circles, and a label inside the
circle represents the vertex. In an undirected graph, the edges are drawn using lines. In a
directed graph, the edges are drawn using arrows.
V(G1) = {1, 2, 3, 4, 5} E(G1) = {(1, 2), (1, 4), (2, 5), (3, 1), (3, 4), (4, 5)}
V(G2) = {0, 1, 2, 3, 4} E(G2) = {(0, 1), (0, 3), (1, 2), (1, 4), (2, 1), (2, 4), (4, 3)}
V(G3) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} E(G3) = {(0, 1), (0, 5), (1, 2), (1, 3), (1, 5), (2, 4), (4, 3),
(5, 6), (6, 8), (7, 3), (7, 8), (8, 10), (9, 4),
(9, 7), (9, 10)}
Adjacency Matrices
Let G be a graph with n vertices, where n > 0. Let V(G) ¼ {v1, v2, . . ., vn}. The adjacency matrix AG is a two-dimensional n n matrix such that the (i, j)th entry of AG
is 1 if there is an edge from vi to vj ; otherwise, the (i, j)th entry is 0. That is,
Adjacency Lists
Let G be a graph with n vertices, where n > 0. Let V(G) ¼ {v1, v2, . . ., vn}. In the
adjacency list representation, corresponding to each vertex, v, there is a linked list such that each node of the linked list contains the vertex, u, such that (v, u) ? E(G). Because there are n nodes, we use an array, A, of size n, such that A[i] is a reference variable pointing to the first node of the linked list containing the vertices to which vi is adjacent. Clearly, each node has two components, say vertex and link. The component vertex contains the index of the vertex adjacent to vertex i
In an undirected graph, if (vi, vj) ? E(G), then (vj, vi) ? E(G), so AG(i, j) ¼ 1 ¼ AG( j, i).
It follows that the adjacency matrix of an undirected graph is symmetric.
Operations on Graphs
Now that you know how to represent graphs in computer memory, the next obvious
step is to learn the basic operations on a graph. The operations commonly performed on a
graph are as follows:
1. Create the graph. That is, store the graph in computer memory using a
particular graph representation.
2. Clear the graph. This operation makes the graph empty.
3. Determine whether the graph is empty.
4. Traverse the graph.
5. Print the graph.
We will add more operations on a graph when we discuss a specific application or a
particular graph later in this chapter.
How a graph is represented in computer memory depends on the specific application. For
illustration purposes, we use the adjacency list (linked list) representation of graphs. Therefore,
for each vertex v the vertices adjacent to v (in a directed grap.
Using these conventions, the definition of the function createGraph is as follows:
void graphType::createGraph()
{
ifstream infile;
char fileName[50];
int vertex;
int adjacentVertex;
if (gSize != 0) //if the graph is not empty, make it empty
clearGraph();
cout << “Enter input file name: “;
cin >> fileName;
cout << endl;
infile.open(fileName);
if (!infile)
{
cout << “Cannot open input file.” << endl;
return;
}
infile >> gSize; //get the number of vertices
for (int index = 0; index < gSize; index++)
{
infile >> vertex;
infile >> adjacentVertex;
while (adjacentVertex != -999)
{
graph[vertex].insertLast(adjacentVertex);
infile >> adjacentVertex;
} //end while
} // end for
infile.close();
} //end createGraph
IMPORTANT POINTS IF GRAPH:
1. A graph G is a pair, G ¼ (V, E), where V is a finite nonempty set, called the
set of vertices of G and E V V , called the set of edges.
2. In an undirected graph G ¼ (V, E), the elements of E are unordered pairs.
3. In a directed graph G ¼ (V, E), the elements of E are ordered pairs.
4. Let G be a graph. A graph H is called a subgraph of G if every vertex of H is
a vertex of G and every edge in H is an edge in G.
5. Two vertices u and v in an undirected graph are called adjacent if there is an
edge from one to the other.
6. An edge incident on a single vertex is called a loop.
7. In an undirected graph, if two edges e1 and e2 are associated with the same
pair of vertices {u, v}, then e1 and e2 are called parallel edges.
8. A graph is called a simple graph if it has no loops and no parallel edges.
9. Let e ¼ (u, v) be an edge in an undirected graph G. The edge e is said to be
incident on the vertices u and v.
10. A path from a vertex u to a vertex v is a sequence of vertices u1, u2, . . ., un
such that u ¼ u1, un ¼ v, and (ui
, ui+ 1) is an edge for all i ¼ 1, 2, . . ., n – 1.
11. The vertices u and v are called connected if there is a path from u to v.
12. A simple path is a path in which all the vertices, except possibly the first and
last vertices, are distinct.
13. A cycle in G is a simple path in which the first and last vertices are the same.
14. An undirected graph G is called connected if there is a path from any vertex
to any other vertex.
15. A maximal subset of connected vertices is called a component of G.
16. Suppose that u and v are vertices in a directed graph G. If there is an edge
from u to v, that is, (u, v) ? E, we say that u is adjacent to v and v is adjacent
from u.
17. A directed graph G is called strongly connected if any two vertices in G are
connected.
18. Let G be a graph with n vertices, where n > 0. Let V(G) ¼ {v1, v2, . . ., vn}.
The adjacency matrix AG is a two-dimensional n n matrix such that the
(i, j)th entry of AG is 1 if there is an edge from vi to vj
; otherwise, the (i, j)th
entry is 0.
19. In an adjacency list representation, corresponding to each vertex v is a
linked list such that each node of the linked list contains the vertex u and
(v, u) ? E(G).
20. The depth-first traversal of a graph is similar to the preorder traversal of a
binary tree.
21. The breadth-first traversal of a graph is similar to the level-by-level traversal
of a binary tree.
22. The shortest path algorithm gives the shortest distance for a given node to
every other node in the graph.
23. In a weighted graph, every edge has a nonnegative weight.
24. The weight of the path P is the sum of the weights of all the edges on the
path P, which is also called the weight of v from u via P.
25. A (free) tree T is a simple graph such that if u and v are two vertices in T,
there is a unique path from u to v.
26. A tree in which a particular vertex is designated as a root is called a rooted
tree.
27. Suppose T is a tree. If a weight is assigned to the edges in T, T is called a
weighted tree.
28. If T is a weighted tree, the weight of T, denoted by W(T), is the sum of the
weights of all the edges in T.
29. A tree T is called a spanning tree of graph G if T is a subgraph of G such
that V(T) ¼ V(G)—that is, if all the vertices of G are in T.
30. Let G be a graph and V(G) ¼ {v1, v2, . . ., vn}, where n ‡ 0. A topological
ordering of V(G) is a linear ordering vi1, vi2, . . ., vin of the vertices such that
if vij is a predecessor of vik, j 6¼ k, 1 j, k n, then vij precedes vik, that is,
j < k in this linear ordering.
31. A circuit is a path of nonzero length from a vertex u to u with no repeated
edges.
32. A circuit in a graph that includes all the edges of the graph is called an Euler
circuit.
33. A graph G is said to be Eulerian if either G is a trivial graph or G has an
Euler circuit.
