DSA Unit 3 PDF - Graphs, Data Structures

Here is the transcription of the image and the corresponding formats. ### 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 a tree structure, there is a hie...

Here is the transcription of the image and the corresponding formats. ### 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 a tree structure, there is a hierarchical relationship between parent and children, that is, one parent and many children. On the other hand, in a 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 | | | | :------------- | :------ | | Tree | Graph | | Figure 8.1 | Two non-linear data structures: tree and graph | Graph structures can be seen everywhere in the real world. Some examples are given below so as to understand this structure better. _416_ ##### Airlines Cities are connected through airlines. This can be represented through a graph structure which is showing 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 Konigsberg. This city is surrounded by 4 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 the 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. | | | | :------ | :------ | | Karachi | | | Lahore | Guwahati | | Delhi | Kolkata | | Mumbai | Hyderabad | | Pune | Chennai | | | Hong Kong | | **Figure 8.2** | Colombo | #### 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. _419_ ##### Graph A graph G consists of two sets: (i) A set V, called the sets of all vertices (or nodes) (ii) 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 = {V1, V2, V3, V4}$ $E = {(V1, V2), (V1, V3), (V1, V4), (V2, V3), (V3, V4)}$ ##### 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 vertice and E is the set of ordered pairs of elements from V. For example, graph G2 is a digraph, where: $V = {V1, V2, V3, V4) $ $E = {(V1, V2), (V1, V3), (V2, V3), (V3, V4), (V4, V₁)}$ Here, if an order pair (v₁, vj) is in E then there is an edge directed from v₁ to vj ( indicated by the arrowhead). Note that, in the case of an undirected graph (simple graph), the pair (vi, vj) is unordered, that is, (v₁, v;) and (vj, vi) the same edges, but in case of digraph they correspond to two different edges. | | | | :--- | :--- | | V1 | V1 | | | | | | | | | | | V2 | V2 | | V3 | V3 | | G1 | G2 | _420_ In our subsequent discussion, an undirected graph is simply termed as graph, and a directed graph will be termed digraph. ##### Weighted graph A graph (or digraph) is termed a weighted graph if all the edges in it are labeled with some weights. For example, G3 and G4 are two weighted graphs in Figure 8.3. ##### Adjacent vertices A vertex Vi is adjacent to (or neighbor of) another vertex, say, $Vj$, if there is an edge from $Vi$ to $Vj$. For example, in G11 (Figure 8.3), $V2$ is adjacent to $V3$ and $V4$, $V1$ is not adjacent to $V4$ but to $V2$. Similarly, the neighbours of $V3$ in graph G2 are $V1$ and $V2$ (but not $V4$). ##### Self loop If there is an edge whose starting and end vertices are the same, that is, $(Vi, Vi)$ 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 the vertex $V4$. ##### 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 $V1$ and $V2$ in graph G5 of Figure 8.3. A graph which has either a self loop or parallel edges, or both, is called a multigraph. In Figure 8.3, G.5 is thus a multigraph. ##### Simple graph (digraph) A graph (digraph) is it does not have any self loop or parallel edges it is called a simple graph (digraph). In Figure 8.3 all graphs except G5, G11 and G10 are simple. ##### Complete graph A graph (digraph) G said to be complete if each vertex Vi is adjacent to every other vertex Vj in G. In other words, there are edges from any vertex to all other vertices two complete graphs. _421_ ##### Acyclic graph If there is a path containing one or more edges that start from vertex $Vi$ and terminates into the same vertex then path cycle. For example. , both G1 and G2 (Figure 8.3). If a graph digraph() the has any cycle then it is called acyclic graph. In Figure acyclic graphs. ##### Isolate vertex A vertex is isolated if a other vertex to Example in to other to connected an vertex. For example, *G8* (Figure 8.3) the vertex u is a vertex. ##### degree of vertex The number of edges connected with vertex $V$ is vertex $∀ V ∈ *G6* degree For example, degree is denoted by *degree* $(v;) == 3$ (Figure 8.3). ##### Pendant vertex A vertex $v$ is of and For example, *G8* in a is pendant vertex. *G7* is four pendant vertices. ##### Connected Graphs In a graph (not digraph), two vertices $Vi$ and $Vj$ are are said to be in *G* from *V* to *V* (ot *V*, to $V$.). graph A is pair, distinct vertices $Vi, Vj$ in every then each there For example, *G1, G3, G6* in the *G8*. are connected are (Figure 8.3). A digraph *G* is every be if from that. G vertex distinct In example both then is strongly for A digraph vertex. The to but connected to graph G connected but the there vertices underlying graph G connected and be said is connected be. We to will discussion the of graph the theory The theory and associated only different discuss will the varieties, directed. We the ##### 8.1 Assignment (a) a with vertices (b) Count the you edges number (c) simple prove complete with the (d) vertices there *n* -*n (1)/2* edges. 1. two Compute (Figure 8.4). this them all 2. For or *G2, G3, G4* (8.4), with whether strongly or the given. 3. two of in it it 4. two so vertex two direction that at The at *G4*, <!--stackedit_data: eyJoaXN0b3J5IjpbNzMyMTQ4NTI0LC02OTEwND -->