Basic Definitions and Terminology

A graph is a structure made of two components : a set of vertices V, and a set of edges E. Therefore, a graph is G = (V,E), where G is a graph. The graph may be directed or undirected. In a directed graph , every edge of the graph is an ordered pair of vertices connected by the edge, whereas in an undirected graph , every edge is an unordered pair of vertices connected by the edge. Figure 22.1 shows an undirected and a directed graph.

Figure 22.1: Graphs.

Incident edge: (v _i ,v _j ) is an edge, then edge(v _i ,v _j ) is said to be incident to vertices v _i and v _j . For example, in graph G ₁ shown in Figure 22.1, the edges incident on vertex 1 are (1,2), (1,4), and (1,3), whereas in G ₂ , the edges incident on vertex 1 are (1,2).

Degree of vertex: The number of edges incident onto the vertex. For example, in graph G ₁ , the degree of vertex 1 is 3, because 3 edges are incident onto it. For a directed graph, we need to define indegree and outdegree. Indegree of a vertex vi is the number of edges incident onto vi, with vi as the head. Outdegree of vertex vi is the number of edges incident onto vi, with vi as the tail. For graph G ₂ , the indegree of vertex 2 is 1, whereas the outdegree of vertex 2 is 2.

Directed edge: A directed edge between the vertices vi and vj is an ordered pair. It is denoted by <vi,vj>.

Undirected edge: An undirected edge between the vertices v _i and v _j is an unordered pair. It is denoted by (v _i ,v _j ).

Path : A path between vertices v _p and v _q is a sequence of vertices v _p , v _i1 , v _i2 , … , v _in ,v _q such that there exists a sequence of edges (v _p , v _i1 ), (v _i1 , v _i2 ), … , ( v _in , v _q ). In case of a directed graph, a path between the vertices v _p and v _q is a sequence of vertices v _p , v _i1 , v _i2 , … , v _in , v _q such that there exists a sequence of edges <v _p , v _i1 >, < v _i1 , v _i2 >, … , <v _in , v _q >. If there exists a path from vertex v _p to v _q in an undirected graph, then there always exists a path from v _q to v _p also. But, in the case of a directed graph, if there exists a path from vertex v _p to v _q , then it does not necessarily imply that there exists a path from v _q to v _p also.

Simple path: A simple path is a path given by a sequence of vertices in which all vertices are distinct except the first and the last vertices. If the first and the last vertices are same, the path will be a cycle.

Maximum number of edges: The maximum number of edges in an undirected graph with n vertices is n ( n − 1)/2. In a directed graph, it is n ( n − 1).

Subgraph : A subgraph of a graph G = (V,E) is a graph G where V(G) is a subset of V(G). E(G) consists of edges (v1,v2) in E(G), such that both v1 and v2 are in V(G). [Note: If G = (V,E) is a graph, then V(G) is a set of vertices of G and E(G) is a set of edges of G.]

If E(G) consists of all edges (v1,v2) in E(G), such that both v1 and v2 are in V(G), then G is called an induced subgraph of G. For example, the graph shown in Figure 22.2 is a subgraph of the graph G2.

Figure 22.2: The subgraph of graph G2.

For the graph shown in Figure 22.3, one of the induced subgraphs is shown in Figure 22.4.

Figure 22.3: Graph G.

Figure 22.4: Induced subgraph of Graph G of Figure 22.3.

In the undirected graph G, the two vertices v ₁ and v ₂ are said to be connected if there exists a path in G from v ₁ to v ₂ (being an undirected graph, there exists a path from v ₂ to v ₁ also).

Connected graph: A graph G is said to be connected if for every pair of distinct vertices (v _i ,v _j ), there is a path from v _i to v _j . A connected graph is shown in Figure 22.5.

Figure 22.5: A connected graph.