Representation and applications

Introduction

Graph

A graph G=(V,E) consists of V, a non-empty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.

Here,

V = {a,b,c,d,e}

E = {(a,b), (a,c), (a,d), (b,e), (c,d), (c,e), (d,e)}

• Infinite Graph: A graph with an infinite vertex set or an infinite number of edges is called an infinite graph.

• Finite Graph: A graph with a finite vertex set and a finite edge set is called a finite graph.

• Simple Graph: A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices is called a simple graph.

• Multigraph: Graphs that may have multiple edges connecting the same vertices are called multigraphs. For example, the edges e1 and e2 have the same set of vertices.

• Loops: An edge in a graph that connects a vertex to itself is called a loop.

• Pseudographs: A graph that may include loops, and possibly multiple edges connecting the same pair of vertices or a vertex to itself, is sometimes called a Pseudograph.

Fig: Multi Graph

• Directed Graph(Digraph): A directed graph (V,E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of objects. The directed edge associated with the ordered pair (u,v) is said to start with u and end at v. Representation example: G(V,E), V = {u,v,w}, E={(u,v), (v,w), (w,u)}.

• Undirected Graph: A graph in which the direction of connection or communication is not specified or defined is called undirected graph.

• Simple Directed Graph: A directed graph which has no loops and no two ordered pair of vertices connected by more than one edge is called a simple directed graph.

• Directed Multigraph: A graph that may have multiple directed edges from a vertex to a second vertex are called directed multigraphs. When there are m directed edges, each associated to an ordered pair of vertices (u,v), then (u,v) is an edge of multiplicity m.

• Mixed graph: A graph with both directed and undirected edges is called a mixed graph.

• Connected Graph: An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph.

• Non-connected Graph: An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph.

Graph Terminology

• Adjacent Vertices: Two vertices u and v in an undirected graph G are called adjacent in G if u and v are endpoints of an edge G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v.
• Degree of Vertex: The degree of a vertex in an undirected graph is the number of edges incident with it.
  • A loop at a vertex contributes twice to the degree of that vertex.
  • The degree of the vertex v is denoted by deg(v).
  • A vertex of degree zero is called isolated.
  • A vertex with degree one is called pendant.
  • Eg: In the figure below, deg(a)=4, deg(b)=deg(e)=6, deg(c)=1 and deg(d)=5.

Degree of Vertex for a Directed Graph

• When (u,v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u. The vertex u is called the initial vertex of (u,v) and v is called the terminal or end vertex. The initial vertex and the terminal vertex of a loop are the same.
• In-degree: The in-degree of a vertex v is the number of edges that are incoming towards v(head of an edge). It is denoted by deg^-(u).
• Out-degree: The out-degree of a vertex v is the number of edges that are outgoing from v (tail of edge). It is denoted by deg⁺(u).
• In the example below, deg^-(u) = 0, deg⁺(u)=2, and deg^-(w)=2, deg⁺(w)=0.

Graph Representations

It is the technique to represent the graph.

Adjacency Lists

• Adjacency list specifies vertices that are adjacent to a vertex.
• This list contains adjacency entries for all vertices for an undirected graph. So, it is possible and very easy to dray the graph if the adjacency list is known.
• The adjacency list for simple undirected graph is shown below:

• For directed graphs, the entries of each vertex, u in the adjacency list contain list of vertices that are incident to u or vertices at which directed edges from u terminates.
• The adjacency list for a simple directed graph is shown below:

Adjacency Matrix

• Let G=(V,E) be a simple graph with |V|=n. Suppose that the vertices of G are listed in arbitrary order as v1, v2, ..., vn. The adjacency matrix A (or A_G) of G, with respect to this listing of the vertices, is the n*n zero-one matrix with 1 as its (i,j)^thentry when v_iand v_jare adjacent, and 0 otherwise.
• In other words, for an adjacency matrix A = [a_ij],
  • a_ij= 1 if {v_i , v_j} is an edge of G,
  • a_ij = 0 otherwise
• An example ofadjacency matrix for undirected graph is given below:

• Adjacency matrices of undirected graphs are always symmetric, that is a_ij =a_ji , because both of these entries are 1 when v_i and v_j are adjacent, and both are 0 otherwise.
• The matrix for a directed graph G=(V,E) has a 1 in its (i,j)th position if there is an edge from v_i to v_j where, v₁, v_2,. . ., v_nis an arbitrary listing of the vertices of the directed graph.
• In other words, if A=[a_ij] is the adjacency matrix for the directed graph with respect to this listing of the vertices then

a_ij = 1 of (v_i, v_j) is an edge of G,

= 0 otherwise

• The adjacency matrix for a directed graph does not have to be symmetric because there may not be an edge from v_j to v_iwhen there is an edge from v_ito v_j.
• For multigraph, when multiple edges connecting the same pair of vertices v_i and v_j, or multiple loops at the same vertex, the adjacency matrix is the (i,j)th entry of this matrix equals the number of edges that are associated to {v_i, v_j}.
• All undirected graphs, including multigraphs and pseudographs, have symmetric adjacency matrices.

• The adjacency matrix for a directed multigraph, a_ijequals the number of edges that are associated to (v_i,v_j).

Incidence Matrices

• Let G=(V,E) be an undirected graph. Suppose that v1, v2, ..., vn are the vertices and e1,e2, ... em are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the n*m matrix M = [m_ij], where

m_ij = 1 when edge e_jis incident with v_i,

= 0 otherwise

• Multiple edges are represented in the incidence matrix using columns with identical entries because these edges are incident with the same pair of vertices. Loops are represented using a column with exactly one entry equal to 1, corresponding to the vertex that is incident with this loop.
• The incidence matrix for a pseudograph is given below:

• Strongly Connected: A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph.
• Weakly Connected: A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph. That is, a directed graph is weakly connected if and only if always a path between two vertices when the directions of the edges are disregarded.
• In the example below, G is strongly connected because there is a path between any two vertices in this directed graph. H is weakly connected because there is a path between any two vertices in the underlying undirected graph of H.

Applications of Graph

• To check the reachability of a node

• To design the electronic circuits

• Finding the shortest path between two location for roads, traffic, communication networks and flights

• Euler paths and circuits can be used to solve the practical problem such as applications asking for a path or a circuit that traverses each street in a neighborhood, each road in a transportation network, each connection in a utility grid, or each link in a communication network exactly once

• Hamilton paths and circuits can be used to solve practical applications such as for a path or a circuit that visits each road intersection in a city, each place pipelines intersect in a utility grid, or each node in a communication network exactly once

• Applications of planar graphs: Planarity of graphs plays an important role in the design of electronic circuits. We can model a circuit with a graph by representing components of the circuit by vertices and connections between them by edges. We can print a circuit on a single board with no connections crossing if the graph representing the circuit is planar

References:

1. Karumanchi, N. "Data Structures and Algorithms Made Easy"

2. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

3. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”