**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.