Graphs - Data Structures and Algorithms - PDF

Okay, here's the conversion of the provided text and image into a structured markdown format: # 8 Graphs ## 8.1 INTRODUCTION A graph is another important non-linear data structure. In Chapter 7, we discussed the tree structure, which is in fact a special kind of graph structure. In tree structure...

Okay, here's the conversion of the provided text and image into a structured markdown format: # 8 Graphs ## 8.1 INTRODUCTION A graph is another important non-linear data structure. In Chapter 7, we discussed the tree structure, which is in fact a special kind of graph structure. In tree structure, there is a hierarchical relationship between parent and children, that is, one parent and many children. On the other hand, in graph, the relationship is less restricted. Here, the relationship is from many parents to many children. Figure 8.1 represents the two non-linear data structures. **Figure 8.1:** Two non-linear data structures: tree and graph. *Description of the image:* * *Tree*: A simple tree diagram is shown with nodes branching down in a hierarchical fashion * *Graph*: An example of a node diagram is shown with lines connecting notes in different ways Graph structures can be seen everywhere in the real world. Some examples are given below so as to understand this structure better. ## Airlines Cities are connected through airlines. This can be represented through a graph structure which is shown in Figure 8.2(a). Here, airports are represented by solid dots and airlines by lines between the dots. ## Source-Destination Network Figure 8.2(b) represents a network connection of three commodities: electricity, gas, and water among three distant destinations D1, D2 and D3. ## Konigsberg's Bridges In Eastern Prussia, there is a city named Konigsberg. This city is surrounded by four lands A, B, C and D which are divided by the river Pregal. Seven bridges connect the four lands. This geographical description can be easily represented through a graph structure which is shown in Figure 8.2(c). A classical problem is related to these Konigsberg's bridges: to determine whether it is possible to cross all the bridges exactly once and return to the starting land area. This problem is known as the Konigsberg's bridge problem. ## Flowchart of a Program The flowchart of a program is in fact the graphical representation of an algorithm of a problem. Figure 8.2(d) represents a flowchart. Similarly, graph structures exist in almost all application areas. **Figure 8.2** Continued *Description of the Image:* * The image of a graph represents a graphical representation of airlines in East Asia, showing cities like Karachi, Lahore, Delhi, Guwahati, Kolkata, Mumbai, Hyderabad, Pune, Chennai, Hong Kong, Bangalore and Colombo connected by lines. * The second image represents graphical representation of 3 commodities in 3 destinations, labelled Gas, Water and Electricity. * The third image demonstrates Konigsberg's bridges and their graphical representation. * The fourth image showcases a flow chart, representing a graphical representation of a program. ## 8.2 GRAPH TERMINOLOGIES In this section, we shall discuss the important terminologies associated with the theory of graphs. In fact, there are no standard terminologies in graph theory. Readers may follow the terminologies mentioned in this section for subsequent discussions. Various terminologies discussed in this section are illustrated in Figure 8.3. **Figure 8.3** Diagrams of various examples for explaining graph terminology. In the diagrams, there are examples of G1, G2, G3, G4, G5, G6 and G8. Here is the continuation of the topics in graph terminology *Graph*: A graph $G$ consists of two sets: * A set $V$, called the set of all vertices (or nodes) * A set $E$, called the set of all edges (or arcs). This set $E$ is the set of all pairs of elements from $V$. For example, let us consider the graph $G1$ in Figure 8.3. Here $V = \{v_1, v_2, v_3, v_4\}$ $E = \{(v_1, v_2), (v_1, v_3), (v_1, v_4), (v_2, v_3), (v_3, v_4)\}$ *Digraph*: A digraph is also called a "directed graph." It is a graph $G$, such that, $G=<V,E>$, where $V$ is the set of all vertices and $E$ is the set of ordered pairs of elements from $V$. For example, graph $G2$ is a digraph, where $V = \{v_1, v_2, v_3, v_4\}$ $E = \{(v_1, v_2), (v_1, v_3), (v_2, v_3), (v_3, v_4), (v_4, v_1)\}$ Here, if an order pair (vᵢ, vⱼ) is in $E$ then there is an edge directed from vᵢ to vⱼ (indicated by the arrowhead). *Note that*, in the case of an undirected graph (simple graph), the pair (vᵢ, vⱼ) is unordered, that is, (vᵢ, vⱼ) and (vⱼ, vᵢ) are the same edges, but in case of digraph they correspond to two different edges. Various illustrations for different terminologies, which includes various graphs such as, G7, G9, G10, G11 and G12.&#x20; Here is the continuation of graph terminologies: In our subsequent discussion, an undirected graph will be simply termed as a graph and a directed graph will be termed a digraph. *Weighted Graph*: A graph (or digraph) is termed a weighted graph if all the edges in it are labelled with some weights. For example, $G3$ and $G4$ are two weighted graphs in Figure 8.3. *Adjacent Vertices*: A vertex $v_i$ is *adjacent to* (or a neighbour of) another vertex, say, $v_j$, if there is an edge from $v_i$ to $v_j$. For example, in G11 (Figure 8.3), $v_2$ is adjacent to $v_3$ and $v_4$, $v_1$ is not adjacent to $v_4$ but to $v_2$. Similarly the neighbours of $v_3$ in graph $G2$ are $v_1$ and $v_2$ (but not $v_4$). *Self Loop*: If there is an edge whose starting and end vertices are the same, that is, $(v_i, v_i)$ is an edge, then it is called a *self loop* (or simply, a loop). For example, the graph $G5$ (in Figure 8.3) has a self-loop at vertex $v_4$. *Parallel Edges*: If there is more than one edge between the same pair of vertices, then they are known as *parallel edges*. For example, there are two parallel edges between $v_1$ and $v_6$ in graph $G5$ of Figure 8.3. A graph which has either self-loop or parallel edges or both, is called a *multigraph*. In Figure 8.3, $G5$ is thus a multigraph. *Simple Graph (Digraph)*: A graph (digraph) if it does not have any self-loop or parallel edges is called a *simple graph* (digraph). In Figure 8.3, all graphs (digraphs) except $G5$ and $G10$ are simple. *Complete Graph*: A graph (digraph) $G$ is said to be *complete* if each vertex $v_i$ is adjacent to every other vertex $v_j$ in $G$. In other words, there are edges from any vertex to all other vertices. For examples, $G6$ and $G9$ are two complete graphs. *Acyclic Graph*: If there is a path containing one or more edges which starts from a vertex $v_i$ and terminates into the same vertex then the path is known as a cycle. For example, there is a cycle in both $G1$ and $G2$ (Figure 8.3). If a graph (digraph) does not have any cycle then it is called *acyclic graph*. For example, in Figure 8.3, $G4$, $G7$ are two acyclic graphs. *Isolated Vertex*: A vertex is *isolated* if there is no edge connected from any other vertex to the vertex. For example, in $G8$ (Figure 8.3) the vertex *u* is an isolated vertex. *Degree of Vertex*: The number of edges connected with vertex $v_i$