{"id":475,"date":"2018-07-19T08:42:08","date_gmt":"2018-07-19T08:42:08","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=475"},"modified":"2018-12-12T12:10:47","modified_gmt":"2018-12-12T12:10:47","slug":"introduction-to-graphs","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/introduction-to-graphs\/","title":{"rendered":"Introduction to Graphs"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will discuss the fundamentals of another important data structure \u2013the graphs.<\/p>\r\n \r\n

Learning Objectives<\/strong><\/p>\r\n \r\n

The learning objectives of the module are as follows:<\/p>\r\n \r\n

\u2022 To understand the components of Graphs<\/p>\r\n

\u2022 To describe the Graph ADT<\/p>\r\n

\u2022 To discuss the different representations of Graphs<\/p>\r\n

\u2022 To analyse the different representations of Graphs<\/p>\r\n \r\n

32.1\u00a0 Introduction<\/strong><\/p>\r\n \r\n

Graph is a data structure that consists of a set of vertices (nodes) and a set of edges between the vertices. The set of edges describes relationships among vertices. Graphs are similar to trees except they do not have as many restrictions.<\/p>\r\n \r\n

\u2022 Graphs represent relationships among data items.<\/p>\r\n

\u2022 A graph G= (V, E)<\/strong> consists a set of vertices<\/strong>, V, and a set of edges<\/strong>, E.<\/p>\r\n

\u2022 Each edge is a pair of vertices (v, w)<\/em>, where both v, w belong to V<\/p>\r\n

\u2022 A sub graph consists of a non-empty subset of a graph\u2019s vertices V and a subset of (possibly empty) of its edges<\/em><\/strong> E where each edge is between vertices that form a subset of V<\/em> with cardinality 2 (an unordered pair).<\/p>\r\n \r\n

A graph with six vertices and seven edges is shown in Figure 32.1.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\n32.2 Terminology<\/strong>\r\n\r\n \r\n

A graph is called a dense<\/strong> graph when |E| \u00bb |V| 2<\/sup> and a sparse<\/strong> graph when |E| \u00bb |V|. An undirected graph<\/em><\/strong> is a graph where the pair of vertices are unordered and any Edge (u,v) = Edge (v,u). A graph is called a directed<\/em><\/strong> graph<\/strong> when each edge connects two vertices, called the source (u) and destination (v); the edge connects the source to the destination (the order is significant). A directed edge (u,v) goes from vertex u to vertex v, notated u\u00aev. A weighted graph<\/em><\/strong> associates weights with either the edges or the vertices. The complete graph<\/strong> is a graph in which every vertex is directly connected to every other vertex. A complete directed graph is shown in Fig 32.2. The number of edges in a complete directed graph with N vertices is given by N * (N-1) is of the order of O(N<\/em>2<\/em>)<\/em> (Figure 32.2). A path is a sequence of vertices that connect two nodes in a graph. The length of a<\/strong> path <\/strong>is the number of edges on it. A Path is called simple <\/strong>if vertices in the sequence are distinct.<\/p>\r\n \r\n\r\n\"\"\r\n

Two nodes of an undirected graph are called adjacent nodes<\/strong> if they are connected by an edge. If (v0, v1) is an edge in an undirected graph, then vertices v0 and v1 are said to be adjacent. The edge (v0, v1) is incident on vertices v0 and v1. If <v0, v1> is an edge in a directed graph where v0 is the source node and v1 is the destination node then v0 is said to be adjacent to v1<\/strong>, and v1 is said to be adjacent from v0<\/strong>. The edge <v0, v1> is incident on v0 and v1. A<\/strong> forest<\/em><\/strong> is an acyclic graph, and a tree<\/em> is a connected acyclic graph. A subgraph<\/strong> of G is a graph G\u2019 such that vertices V(G\u2019) is a subset of veritices V(G) and edges E(G\u2019) is a subset of edges E(G) between vertices that are from the subset V(G\u2019). In other words a subgraph of G<\/em> is a graph G<\/em>\u2019 such that V(G<\/em>\u2019) \u00cd V(G<\/em>) and E(G<\/em>\u2019) \u00cd E(G<\/em>).<\/p>\r\n \r\n\r\nExamples of subgraphs are shown in Fig 32.3\r\n\r\n \r\n\r\n\"\"\r\n\r\n32.2.1 Connected Component<\/strong>\r\n\r\n \r\n\r\nIn an undirected graph G, two vertices, <\/span>v<\/em>0 and <\/span>v<\/em>1, are connected if there is a path in <\/span>G <\/em>from<\/span> v<\/em>0 to<\/span> v<\/em>1. An undirected graph is connected if, for every pair of distinct vertices<\/span> v<\/em>i,<\/span> v<\/em>j, there is a path from<\/span> v<\/em>i to<\/span> v<\/em>j A connected component of an undirected graph is a maximal sub-graph that is connected . A completely connected graph has exactly 1 component. Example of connected components and not a component are shown in Fig 32.4.<\/span>\r\n\r\n \r\n\r\nA directed graph is strongly connected if there is a directed path from <\/span>vi<\/em> to <\/span>vj<\/em> and also from <\/span>vj<\/em> to <\/span>vi.<\/em> A strongly connected component is a maximal subgraph that is strongly connected.<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n32.2.2 Degree<\/strong>\r\n\r\n \r\n

The degree of a vertex in an undirected graph is the number of edges incident to that vertex. If d<\/em>i<\/em> is the degree of a vertex i<\/em> in an undirected graph G<\/em> with n<\/em> vertices and e<\/em> edges, the number of edges is<\/p>\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n

For a directed graph, the in-degree of a vertex v<\/em> is the number of incoming edges that have v<\/em> as the head and the out-degree of a vertex v<\/em> is the number of outgoing edges that have v<\/em> as the tail. For a complete directed graph the number of edges = n(n-1) edges<\/p>\r\n \r\n\r\n32.3 Trees as Graphs<\/strong>\r\n\r\n \r\n

Every tree is a connected acyclic graph that is a graph with some restrictions as shown in Fig 32.6. The restrictions are that the tree is rooted, directed,<\/em> there are no<\/em> cycles <\/em>and there is a directed path from the <\/em>root to every node.<\/em><\/p>\r\n\"\"\r\n\r\n \r\n

Each of the red areas breaks one of these constraints. In the tree the direction of the edge is assumed to be from a node to another node that is at a lower level though the direction is not explicitly shown. In the figure 32.6, 1 shows the direction is from lower level node to higher level and is not allowed in a tree. 2 shows the presence of a cycle while 3 violates the condition that there must be a directed path from the root to every node.<\/p>\r\n \r\n\r\n32.4\u00a0 Why Use Graphs?<\/strong>\r\n\r\n \r\n

Graphs can be used to model a wide range of applications. When we design the model we need to decide on what components of the application represent the vertices and what connections between these components represent the edges. Examples of such applications include the following:<\/p>\r\n \r\n\r\n\u2022 Intersections and streets within a city\r\n\r\n\u2022 Roads\/trains\/airline routes connecting cities\/countries\r\n\r\n\u2022 Computer networks\r\n\r\n\u2022 Electronic circuits\r\n\r\n\u2022 A layout of an adventure game world\r\n\r\n\u2022 A schematic of the computers and connections that make up the Internet\r\n\r\n\u2022 The links between pages on the Web\r\n\r\n\u2022 The relationship between students and courses\r\n\r\n\u2022\u00a0 A diagram of the flow capacities in a communications or transportation network\r\n\r\n<\/div>\r\n \r\n\r\n32.4.1 Application1 \u2013Air Flight System (Fig 32.8)<\/strong>\r\n

\r\n\r\n \r\n

In this application, each vertex of the graph represents a city and each edge represents a direct flight between two cities. In this case a query on direct flights is equivalent to a query on whether an edge exists. A query on how to get to a location is equivalent to finding whether a path exists from A to B. We can even associate costs to edges (weighted graphs), then ask \u201cwhat is the cheapest path from A to B\u201d .<\/p>\r\n \r\n\r\n\"\"\r\n

This application can be represented by a weighted complete graph (every two vertices are connected by an edge) (Figure32.9). Each path represents the Euclidean distance between two stations . Each station uses a certain power i to transmit messages. Given this power i, only a few nodes can be reached (bold edges). A station reachable by i then uses its own power to relay the message to other stations not reachable by i. A typical wireless communication problem is: how to broadcast between all<\/em> stations such that they are all connected and the power consumption is minimized. This is essentially the shortest path finding problem.<\/p>\r\n \r\n\r\n32.5<\/strong>\u00a0Representation of Graphs<\/strong>\r\n\r\n \r\n

Three popular computer representations of a graph represent the vertex set and the edge set, but in different ways.<\/p>\r\n \r\n

32.5.1 Adjacency Matrix<\/strong><\/p>\r\n \r\n

This representation uses a 2D matrix to represent the graph. That is it is represented as a square grid of Boolean values. Therefore if the graph contains N vertices, then the grid contains N rows and N columns. For two vertices numbered I and J, the element at row I and column J is true if there is an edge from I to J, otherwise it is false.<\/span><\/p>\r\n \r\n

The Matrix of will be of size |V| x |V|<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n