Copyright HébergementWebs.com - License GPL

Graph Theory - Types of Graphs

Graph theory tutorial   2020-11-18 03:48:58

Graph Theory - Types of Graphs There are different types of graphs depending on the number of vertices, number of edges, interconnectivity and their structure overall. We will only discuss a few important types of graphs in this chapter. Null Graph An edgeless graph is called a Null Graph. Example In the graphic above, there are three vertices named "a ", "b " and "c ", but there are no edges among them. It is therefore a zero graph. Trivial graph A graph with only one vertex is called a trivial graph. Example In the graphic above, there is only one vertex "a " with no other edges. It is therefore a trivial graph. G undirected An undirected graph contains edges but the edges are not directed. Example In this graphic, "a ", "b ", "c ", "d ", "e " , "F ", "g " are the vertices, and "ab ", "bc ", "cd ", "da ", "ag ", "gf ", "ef " are the edges of the graph. Since this is an undirected graph, the edges "ab" and "ba" are the same. Likewise, other edges are also considered in the same way. Directed graph In a directed graph, each edge has a direction. Example In the above graph, we have seven vertices "a ", " b ", " c ", " d ", " e ", " f "and " g ", and eight edges " ab ", " cb " , "dc ", "ad ", "ec ", "fe ", "gf " and "ga ". Since this is a directed graph, each edge has an arrow indicating its direction. Note that in a directed graph, "ab" is different from "ba ". Simple graph A graph without loops and without parallel edges is called a simple graph. The maximum number of possible edges in a single graph with "n " vertices is n C 2 where n C 2 = n (n - 1) / 2. The number of simple graphs possible with "n " vertices = 2 n c 2 = 2 n (n-1) / 2 . Example In the following graphic, there are 3 vertices with 3 edges which is maximum excluding parallel edges and loops. This can be proven using the formulas above. The maximum number of edges with n = 3 vertices - n C 2 = n (n - 1) / 2 = 3 (3–1) / 2 = 6/2 = 3 edges The maximum number of simple graphs with n = 3 vertices - 2 n C 2 = 2 n (n -1) / 2 = 2 3 (3-1) / 2 = 2 3 8 These 8 graphics are as shown below - Connected graph A graph G is sa id to be connected if there is a path between each pair of vertices . There must be at least one edge for each vertex in the graph. So that we can tell that it is connected to another vertex on the other side of the edge. Example In the following graph, each vertex has its own edge connected to the other edge, so it is a connected graph. Graphic offline A graph G is disconnected, if it does not contain at least two connected vertices. Example 1 The following graph is an example of a disconnected graph, where there are two components, l "one with " a ", " b ", " c ", " vertices and anothere with vertices "e ", "f ", "g ", "h ". Both components are independent and not connected to each other, so it is called disconnected graph. Example 2 In this For example, there are two independent components, abfe and cd, which are not connected to each other, so it is a disconnected graph. Regular graph A graph G is sa id to be regular, if all its vertices have the same degree . In a graph, if the degree of each vertex is "k", then the graph is called a "k -regular graph ". Example In the following graphs, all vertices have the same degree. So these graphs are called regular graphs. In both graphs, all vertices have degree 2. They are called 2-regular graphs. Full graph A simple graph with "n " mutual vertices is called a full graph and it is denoted by "K n ". In the graph, a vertex should have edges with all other vertices , so it called a full graph. In other words, if a vertex is connected to all the other vertices of a graph, then it is called a complete graph. Example In the following graphs, each vertex of the graph is connected with all remaining vertices of the graph except by itself. Jen graph I, a b c a Not connected Connected Connected b Connected Not connected Connected c ConnectedConnected Not connected In Chart II, p q r s p Not logged in Logged in Logged in Logged in q Connected Not connected Connected Connected r Connected Connected Not connected Connected s Connected Connected Connected Not connected Cycle graph A simple graph with "n " vertices (p> = 3) and "n " edges is called a cyclic graph if all its edges form a cycle of length "n ". If the degree of each vertex in the graph is two, then we call it a Cycle Graph. Notation - C n Example Take a look at the following graphics - Graph I has 3 vertices with 3 edges which form an "ab-bc-ca " cycle. Graph II has 4 vertices with 4 edges which form a "pq-qs-sr-rp " cycle. Graph III has 5 vertices with 5 edges which form a "ik-km-ml-lj-ji " cycle. All given graphs are therefore cycle graphs. Wheel graph A wheel graph is obtained from a cycle graph C n-1 by adding a new vertex. This new vertex is called a Hub which is connected to all vertices in C n . Notation - W n No. of edges in W n = Number of edges in hub at all the other vertices + Number of edges of all the other nodes of the cyclic graph without a hub. = (n - 1) + (n - 1) = 2 (n - 1) Example Take a look at the following graphics. These are all wheel graphics. In graph I, it is obtained from C 3 by adding a vertex in the middle named" d ". It is noted W 4 . Number of edges in W4 = 2 (n-1) = 2 (3) = 6 In graph II, it is obtained from C4 by adding a vertex in the middle named "t ". It is noted W 5 . Number of edges in W5 = 2 (n-1) = 2 (4) = 8 In graph III, it is obtained from C 6 by adding a vertex in the middle named "o". It is noted W 7 . Number of edges in W4 = 2 (n-1) = 2 (6) = 12 Cycle graph A graph with at least one cycle is called a cycle graph. Example In the example graphice above we have two cycles abcda and cfgec. This is why it is called a cycle graph. Acyclic graph A cycleless graph is called an acyclic graph. Example In the example of graph above, we have no cycle, so it is a non-cyclic graph. Bipartite graph A simple graph G = (V, E) with a partition of vertices V = {V 1 , V 2 } is called a bipartite graph if each edge of E joins a vertex of V1 to a vertex of V 2 . In general, a Bipertite graph has two sets of vertices, say V1 and V2, and if an edge is drawn, it should connect n " any vertex in set V 1 to any vertex in set V 2 . Example In this graphic, yous can observe two sets of vertices - V 1 and V 2 . Here, two edges named "ae " and "bd " connect the vertices of two sets V 1 and V 2 . Complete bipartite graph A bipartite graph "G ", G = (V, E) with the partition V = {V 1 , V 2 } is sa id to be a complete bipartite graph if every vertex of V 1 is connected to every vertex of V 2 . In general, a complete bipartite graph connects each vertex of the set V 1 to each vertex of the set V 2 . Example The following graph is a complete bipartite graph because it has edges connecting each vertex of the set V 1 to each vertex of l "set V 2 . If | V 1 | = m and | V 2 | = n, then the complete bipartite graph is denoted by K m, n . K m, n has (m + n) vertices and (mn) edges. K m, n is a regular graph if m = n. In general, a full bipartite graph is not a full graph . K m, n is a complete graph if m = n = 1. The maximum number of edges in a bipartite graph with n vertices is - [n 2 / 4] If n = 10, k5, 5 = [n2 / 4] = [10 2 / 4] = 25. Likewise, K6, 4 = 24 K7, 3 = 21 K8, 2 = 16 K9, 1 = 9 If n = 9, k5, 4 = [n2 / 4] = [92/4] = 20 Similarly, K6, 3 = 18 K7, 2 = 14 K8, 1 = 8 "G " is a bipartite graph if "G " has no cycles of odd length. A special case of a bipartite graph is a star graph. A star graph A complete bipartite graph of the form K1, n-1 is a star graph with n-vertices. A star graph is a bipartite graph cComplete if only one vertex belongs to it set and all remaining vertices belong to the other set. Example In the above graphics, on "n " vertices, all vertices "n - 1 " are connected to a single vertex. is therefore in the form of K 1 , n-1 which are star graphs. Complement of a graph Let "G− " be a simple graph with a few vertices like that of "G " and an edge {U, V} is present in "G− ", if the edge n "is not present in G. This means, two vertices are adjacent in " G− "if the two vertices are not adjacent in G. If the edges which exist in the graph I are absent in another graph II, and if both graph I and graph II are combined to form a complete graph, then graph I and graph II are called complements of each other. Example In the following example, the graph I has two edges "cd " and "bd ". Its complement graph-II has four edges. Note that the edges of the graph -I am not present in the graph II and vice versa. Therefore, the combination of the two graphs gives a complete graph of "n" vertices. Note - A combination of two complementary graphs results in a complete graph. If "G " is a simple graph, then | E (G) | + | E ( "G - ") | = | E (Kn) |, where n = number of vertices in the graph. Example Let "G " be a simple graph with nine vertices and twelve edges, find the number of edges in "G- ". You have, | E (G) | + | E ( "G - ") | = | E (Kn) | 12 + | E ( "G - ") | = 9 (9-1) / 2 = 9 C 2 12 + | E ( "G - ") | = 36 | E ( "G - ") | = 24 "G " is a simple graph with 40edges and its complement "G− " has 38 edges. Find the number of vertices in the graph G or "G− ". Let the number of vertices in the graph be "n". We have, | E (G) | + | E ( "G - ") | = | E (Kn) | 40 + 38 = n (n-1) / 2 156 = n (n-1) 13 (12) = n (n- 1) n = 13