Bipartite GraphĪ simple graph G = (V, E) with vertex partition V = is present in ' G −', if the edge is not present in G. In the above example graph, we do not have any cycles. Acyclic GraphĪ graph with no cycles is called an acyclic graph. In the above example graph, we have two cycles a-b-c-d-a and c-f-g-e-c. Number of edges in W 4 = 2(n-1) = 2(6) = 12Ī graph with at least one cycle is called a cyclic graph. In graph III, it is obtained from C 6 by adding a vertex at the middle named as ‘o’. In graph II, it is obtained from C 4 by adding a vertex at the middle named as ‘t’. In graph I, it is obtained from C 3 by adding an vertex at the middle named as ‘d’. of edges from all other nodes in cycle graph without a hub. of edges from hub to all other vertices + That new vertex is called a Hub which is connected to all the vertices of C n. Wheel GraphĪ wheel graph is obtained from a cycle graph C n-1 by adding a new vertex. Hence all the given graphs are cycle graphs. Graph III has 5 vertices with 5 edges which is forming a cycle ‘ik-km-ml-lj-ji’. Graph II has 4 vertices with 4 edges which is forming a cycle ‘pq-qs-sr-rp’. Graph I has 3 vertices with 3 edges which is forming a cycle ‘ab-bc-ca’. If the degree of each vertex in the graph is two, then it is called a Cycle Graph. In the following graphs, each vertex in the graph is connected with all the remaining vertices in the graph except by itself.Ī simple graph with ‘n’ vertices (n >= 3) and ‘n’ edges is called a cycle graph if all its edges form a cycle of length ‘n’. In other words, if a vertex is connected to all other vertices in a graph, then it is called a complete graph. In the graph, a vertex should have edges with all other vertices, then it called a complete graph. Complete GraphĪ simple graph with ‘n’ mutual vertices is called a complete graph and it is denoted by ‘K n’. In both the graphs, all the vertices have degree 2. So these graphs are called regular graphs. In the following graphs, all the 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’. Regular GraphĪ graph G is said to be regular, if all its vertices have the same degree. In this example, there are two independent components, a-b-f-e and c-d, which are not connected to each other. The two components are independent and not connected to each other. The following graph is an example of a Disconnected Graph, where there are two components, one with ‘a’, ‘b’, ‘c’, ‘d’ vertices and another with ‘e’, ’f’, ‘g’, ‘h’ vertices. Disconnected GraphĪ graph G is disconnected, if it does not contain at least two connected vertices. In the following graph, each vertex has its own edge connected to other edge. So that we can say that it is connected to some other vertex at the other side of the edge. There should be at least one edge for every vertex in the graph. These 8 graphs are as shown below − Connected GraphĪ graph G is said to be connected if there exists a path between every pair of vertices. The maximum number of simple graphs with n=3 vertices − The maximum number of edges with n=3 vertices − nC 2 = n(n–1)/2 This can be proved by using the above formulae. In the following graph, there are 3 vertices with 3 edges which is maximum excluding the parallel edges and loops. The number of simple graphs possible with ‘n’ vertices = 2 nc 2 = 2 n(n-1)/2. The maximum number of edges possible in a single graph with ‘n’ vertices is nC 2 where nC 2 = n(n – 1)/2. Simple GraphĪ graph with no loops and no parallel edges is called a simple graph. Note that in a directed graph, ‘ab’ is different from ‘ba’. As it is a directed graph, each edge bears an arrow mark that shows its direction. In a directed graph, each edge has a direction. Similarly other edges also considered in the same way. Since it is a non-directed graph, the edges ‘ab’ and ‘ba’ are same. Non-Directed GraphĪ non-directed graph contains edges but the edges are not directed ones. In the above shown graph, there is only one vertex ‘a’ with no other edges. Trivial GraphĪ graph with only one vertex is called a Trivial Graph. In the above graph, there are three vertices named ‘a’, ‘b’, and ‘c’, but there are no edges among them. Null GraphĪ graph having no edges is called a Null Graph. We will discuss only a certain few important types of graphs in this chapter. There are various types of graphs depending upon the number of vertices, number of edges, interconnectivity, and their overall structure.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |