Category: graph Theory

Graph Theory – Traversability ”; Previous Next A graph is traversable if you can draw a path between all the vertices without retracing the same path. Based on this path, there are some categories like Euler’s path and Euler’s circuit which are described in this chapter. Euler’s Path An Euler’s path contains each edge of ‘G’ exactly once and each vertex of ‘G’ at least once. A connected graph G is said to be traversable if it contains an Euler’s path. Example Euler’s Path = d-c-a-b-d-e. Euler’s Circuit In a Euler’s path, if the starting vertex is same as its ending vertex, then it is called an Euler’s circuit. Example Euler’s Path = a-b-c-d-a-g-f-e-c-a. Euler’s Circuit Theorem A connected graph ‘G’ is traversable if and only if the number of vertices with odd degree in G is exactly 2 or 0. A connected graph G can contain an Euler’s path, but not an Euler’s circuit, if it has exactly two vertices with an odd degree. Note − This Euler path begins with a vertex of odd degree and ends with the other vertex of odd degree. Example Euler’s Path − b-e-a-b-d-c-a is not an Euler’s circuit, but it is an Euler’s path. Clearly it has exactly 2 odd degree vertices. Note − In a connected graph G, if the number of vertices with odd degree = 0, then Euler’s circuit exists. Hamiltonian Graph A connected graph G is said to be a Hamiltonian graph, if there exists a cycle which contains all the vertices of G. Every cycle is a circuit but a circuit may contain multiple cycles. Such a cycle is called a Hamiltonian cycle of G. Hamiltonian Path A connected graph is said to be Hamiltonian if it contains each vertex of G exactly once. Such a path is called a Hamiltonian path. Example Hamiltonian Path− e-d-b-a-c. Note Euler’s circuit contains each edge of the graph exactly once. In a Hamiltonian cycle, some edges of the graph can be skipped. Example Take a look at the following graph − For the graph shown above − Euler path exists – false Euler circuit exists – false Hamiltonian cycle exists – true Hamiltonian path exists – true G has four vertices with odd degree, hence it is not traversable. By skipping the internal edges, the graph has a Hamiltonian cycle passing through all the vertices. Print Page Previous Next Advertisements ”;

Graph Theory – Isomorphism ”; Previous Next A graph can exist in different forms having the same number of vertices, edges, and also the same edge connectivity. Such graphs are called isomorphic graphs. Note that we label the graphs in this chapter mainly for the purpose of referring to them and recognizing them from one another. Isomorphic Graphs Two graphs G1 and G2 are said to be isomorphic if − Their number of components (vertices and edges) are same. Their edge connectivity is retained. Note − In short, out of the two isomorphic graphs, one is a tweaked version of the other. An unlabelled graph also can be thought of as an isomorphic graph. There exists a function ‘f’ from vertices of G1 to vertices of G2 [f: V(G1) ⇒ V(G2)], such that Case (i): f is a bijection (both one-one and onto) Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the edge {f(U), f(V)} ∈ G2, then G1 ≡ G2. Note If G1 ≡ G2 then − |V(G1)| = |V(G2)| |E(G1)| = |E(G2)| Degree sequences of G1 and G2 are same. If the vertices {V1, V2, .. Vk} form a cycle of length K in G1, then the vertices {f(V1), f(V2),… f(Vk)} should form a cycle of length K in G2. All the above conditions are necessary for the graphs G1 and G2 to be isomorphic, but not sufficient to prove that the graphs are isomorphic. (G1 ≡ G2) if and only if (G1− ≡ G2−) where G1 and G2 are simple graphs. (G1 ≡ G2) if the adjacency matrices of G1 and G2 are same. (G1 ≡ G2) if and only if the corresponding subgraphs of G1 and G2 (obtained by deleting some vertices in G1 and their images in graph G2) are isomorphic. Example Which of the following graphs are isomorphic? In the graph G3, vertex ‘w’ has only degree 3, whereas all the other graph vertices has degree 2. Hence G3 not isomorphic to G1 or G2. Taking complements of G1 and G2, you have − Here, (G1− ≡ G2−), hence (G1 ≡ G2). Planar Graphs A graph ‘G’ is said to be planar if it can be drawn on a plane or a sphere so that no two edges cross each other at a non-vertex point. Example Regions Every planar graph divides the plane into connected areas called regions. Example Degree of a bounded region r = deg(r) = Number of edges enclosing the regions r. deg(1) = 3 deg(2) = 4 deg(3) = 4 deg(4) = 3 deg(5) = 8 Degree of an unbounded region r = deg(r) = Number of edges enclosing the regions r. deg(R1) = 4 deg(R2) = 6 In planar graphs, the following properties hold good − In a planar graph with ‘n’ vertices, sum of degrees of all the vertices is − n Σ i=1 deg(Vi) = 2|E| According to Sum of Degrees of Regions/ Theorem, in a planar graph with ‘n’ regions, Sum of degrees of regions is − n Σ i=1 deg(ri) = 2|E| Based on the above theorem, you can draw the following conclusions − In a planar graph, If degree of each region is K, then the sum of degrees of regions is − K|R| = 2|E| If the degree of each region is at least K(≥ K), then K|R| ≤ 2|E| If the degree of each region is at most K(≤ K), then K|R| ≥ 2|E| Note − Assume that all the regions have same degree. According to Euler’s Formulae on planar graphs, If a graph ‘G’ is a connected planar, then |V| + |R| = |E| + 2 If a planar graph with ‘K’ components, then |V| + |R|=|E| + (K+1) Where, |V| is the number of vertices, |E| is the number of edges, and |R| is the number of regions. Edge Vertex Inequality If ‘G’ is a connected planar graph with degree of each region at least ‘K’ then, |E| ≤ k / (k-2) {|v| – 2} You know, |V| + |R| = |E| + 2 K.|R| ≤ 2|E| K(|E| – |V| + 2) ≤ 2|E| (K – 2)|E| ≤ K(|V| – 2) |E| ≤ k / (k-2) {|v| – 2} If ‘G’ is a simple connected planar graph, then |E| ≤ 3|V| − 6 |R| ≤ 2|V| − 4 There exists at least one vertex V •∈ G, such that deg(V) ≤ 5. If ‘G’ is a simple connected planar graph (with at least 2 edges) and no triangles, then |E| ≤ {2|V| – 4} Kuratowski’s Theorem A graph ‘G’ is non-planar if and only if ‘G’ has a subgraph which is homeomorphic to K5 or K3,3. Homomorphism Two graphs G1 and G2 are said to be homomorphic, if each of these graphs can be obtained from the same graph ‘G’ by dividing some edges of G with more vertices. Take a look at the following example − Divide the edge ‘rs’ into two edges by adding one vertex. The graphs shown below are homomorphic to the first graph. If G1 is isomorphic to G2, then G is homeomorphic to G2 but the converse need not be true. Any graph with 4 or less vertices is planar. Any graph with 8 or less edges is planar. A complete graph Kn is planar if and only if n ≤ 4. The complete bipartite graph Km, n is planar if and only if m ≤ 2 or n ≤ 2. A simple non-planar graph with minimum number of vertices is the complete graph K5. The simple non-planar graph with minimum number of edges is K3, 3. Polyhedral graph A simple connected planar graph is called a polyhedral graph if the degree of each vertex is ≥ 3, i.e., deg(V) ≥ 3 ∀ V ∈ G. 3|V| ≤ 2|E| 3|R| ≤ 2|E| Print Page Previous Next

Graph Theory – Quick Guide ”; Previous Next Graph Theory – Introduction In the domain of mathematics and computer science, graph theory is the study of graphs that concerns with the relationship among edges and vertices. It is a popular subject having its applications in computer science, information technology, biosciences, mathematics, and linguistics to name a few. Without further ado, let us start with defining a graph. What is a Graph? A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges. Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices. Take a look at the following graph − In the above graph, V = {a, b, c, d, e} E = {ab, ac, bd, cd, de} Applications of Graph Theory Graph theory has its applications in diverse fields of engineering − Electrical Engineering − The concepts of graph theory is used extensively in designing circuit connections. The types or organization of connections are named as topologies. Some examples for topologies are star, bridge, series, and parallel topologies. Computer Science − Graph theory is used for the study of algorithms. For example, Kruskal”s Algorithm Prim”s Algorithm Dijkstra”s Algorithm Computer Network − The relationships among interconnected computers in the network follows the principles of graph theory. Science − The molecular structure and chemical structure of a substance, the DNA structure of an organism, etc., are represented by graphs. Linguistics − The parsing tree of a language and grammar of a language uses graphs. General − Routes between the cities can be represented using graphs. Depicting hierarchical ordered information such as family tree can be used as a special type of graph called tree. Graph Theory – Fundamentals A graph is a diagram of points and lines connected to the points. It has at least one line joining a set of two vertices with no vertex connecting itself. The concept of graphs in graph theory stands up on some basic terms such as point, line, vertex, edge, degree of vertices, properties of graphs, etc. Here, in this chapter, we will cover these fundamentals of graph theory. Point A point is a particular position in a one-dimensional, two-dimensional, or three-dimensional space. For better understanding, a point can be denoted by an alphabet. It can be represented with a dot. Example Here, the dot is a point named ‘a’. Line A Line is a connection between two points. It can be represented with a solid line. Example Here, ‘a’ and ‘b’ are the points. The link between these two points is called a line. Vertex A vertex is a point where multiple lines meet. It is also called a node. Similar to points, a vertex is also denoted by an alphabet. Example Here, the vertex is named with an alphabet ‘a’. Edge An edge is the mathematical term for a line that connects two vertices. Many edges can be formed from a single vertex. Without a vertex, an edge cannot be formed. There must be a starting vertex and an ending vertex for an edge. Example Here, ‘a’ and ‘b’ are the two vertices and the link between them is called an edge. Graph A graph ‘G’ is defined as G = (V, E) Where V is a set of all vertices and E is a set of all edges in the graph. Example 1 In the above example, ab, ac, cd, and bd are the edges of the graph. Similarly, a, b, c, and d are the vertices of the graph. Example 2 In this graph, there are four vertices a, b, c, and d, and four edges ab, ac, ad, and cd. Loop In a graph, if an edge is drawn from vertex to itself, it is called a loop. Example 1 In the above graph, V is a vertex for which it has an edge (V, V) forming a loop. Example 2 In this graph, there are two loops which are formed at vertex a, and vertex b. Degree of Vertex It is the number of vertices adjacent to a vertex V. Notation − deg(V). In a simple graph with n number of vertices, the degree of any vertices is − deg(v) ≤ n – 1 ∀ v ∈ G A vertex can form an edge with all other vertices except by itself. So the degree of a vertex will be up to the number of vertices in the graph minus 1. This 1 is for the self-vertex as it cannot form a loop by itself. If there is a loop at any of the vertices, then it is not a Simple Graph. Degree of vertex can be considered under two cases of graphs − Undirected Graph Directed Graph Degree of Vertex in an Undirected Graph An undirected graph has no directed edges. Consider the following examples. Example 1 Take a look at the following graph − In the above Undirected Graph, deg(a) = 2, as there are 2 edges meeting at vertex ‘a’. deg(b) = 3, as there are 3 edges meeting at vertex ‘b’. deg(c) = 1, as there is 1 edge formed at vertex ‘c’ So ‘c’ is a pendent vertex. deg(d) = 2, as there are 2 edges meeting at vertex ‘d’. deg(e) = 0, as there are 0 edges formed at vertex ‘e’. So ‘e’ is an isolated vertex. Example 2 Take a look at the following graph − In the above graph, deg(a) = 2, deg(b) = 2, deg(c) = 2, deg(d) = 2, and deg(e) = 0. The vertex ‘e’ is an isolated vertex. The graph does not have any pendent vertex. Degree of Vertex in a Directed Graph In a directed graph, each vertex has an indegree and an outdegree.

Graph Theory – Basic Properties ”; Previous Next Graphs come with various properties which are used for characterization of graphs depending on their structures. These properties are defined in specific terms pertaining to the domain of graph theory. In this chapter, we will discuss a few basic properties that are common in all graphs. Distance between Two Vertices It is number of edges in a shortest path between Vertex U and Vertex V. If there are multiple paths connecting two vertices, then the shortest path is considered as the distance between the two vertices. Notation − d(U,V) There can be any number of paths present from one vertex to other. Among those, you need to choose only the shortest one. Example Take a look at the following graph − Here, the distance from vertex ‘d’ to vertex ‘e’ or simply ‘de’ is 1 as there is one edge between them. There are many paths from vertex ‘d’ to vertex ‘e’ − da, ab, be df, fg, ge de (It is considered for distance between the vertices) df, fc, ca, ab, be da, ac, cf, fg, ge Eccentricity of a Vertex The maximum distance between a vertex to all other vertices is considered as the eccentricity of vertex. Notation − e(V) The distance from a particular vertex to all other vertices in the graph is taken and among those distances, the eccentricity is the highest of distances. Example In the above graph, the eccentricity of ‘a’ is 3. The distance from ‘a’ to ‘b’ is 1 (‘ab’), from ‘a’ to ‘c’ is 1 (‘ac’), from ‘a’ to ‘d’ is 1 (‘ad’), from ‘a’ to ‘e’ is 2 (‘ab’-‘be’) or (‘ad’-‘de’), from ‘a’ to ‘f’ is 2 (‘ac’-‘cf’) or (‘ad’-‘df’), from ‘a’ to ‘g’ is 3 (‘ac’-‘cf’-‘fg’) or (‘ad’-‘df’-‘fg’). So the eccentricity is 3, which is a maximum from vertex ‘a’ from the distance between ‘ag’ which is maximum. In other words, e(b) = 3 e(c) = 3 e(d) = 2 e(e) = 3 e(f) = 3 e(g) = 3 Radius of a Connected Graph The minimum eccentricity from all the vertices is considered as the radius of the Graph G. The minimum among all the maximum distances between a vertex to all other vertices is considered as the radius of the Graph G. Notation − r(G) From all the eccentricities of the vertices in a graph, the radius of the connected graph is the minimum of all those eccentricities. Example In the above graph r(G) = 2, which is the minimum eccentricity for ‘d’. Diameter of a Graph The maximum eccentricity from all the vertices is considered as the diameter of the Graph G. The maximum among all the distances between a vertex to all other vertices is considered as the diameter of the Graph G. Notation − d(G) − From all the eccentricities of the vertices in a graph, the diameter of the connected graph is the maximum of all those eccentricities. Example In the above graph, d(G) = 3; which is the maximum eccentricity. Central Point If the eccentricity of a graph is equal to its radius, then it is known as the central point of the graph. If e(V) = r(V), then ‘V’ is the central point of the Graph ’G’. Example In the example graph, ‘d’ is the central point of the graph. e(d) = r(d) = 2 Centre The set of all central points of ‘G’ is called the centre of the Graph. Example In the example graph, {‘d’} is the centre of the Graph. Circumference The number of edges in the longest cycle of ‘G’ is called as the circumference of ‘G’. Example In the example graph, the circumference is 6, which we derived from the longest cycle a-c-f-g-e-b-a or a-c-f-d-e-b-a. Girth The number of edges in the shortest cycle of ‘G’ is called its Girth. Notation: g(G). Example − In the example graph, the Girth of the graph is 4, which we derived from the shortest cycle a-c-f-d-a or d-f-g-e-d or a-b-e-d-a. Sum of Degrees of Vertices Theorem If G = (V, E) be a non-directed graph with vertices V = {V1, V2,…Vn} then n Σ i=1 deg(Vi) = 2|E| Corollary 1 If G = (V, E) be a directed graph with vertices V = {V1, V2,…Vn}, then n Σ i=1 deg+(Vi) = |E| = n Σ i=1 deg−(Vi) Corollary 2 In any non-directed graph, the number of vertices with Odd degree is Even. Corollary 3 In a non-directed graph, if the degree of each vertex is k, then k|V| = 2|E| Corollary 4 In a non-directed graph, if the degree of each vertex is at least k, then k|V| ≤ 2|E| | Corollary 5 In a non-directed graph, if the degree of each vertex is at most k, then k|V| ≥ 2|E| Print Page Previous Next Advertisements ”;

Graph Theory – Trees ”; Previous Next Trees are graphs that do not contain even a single cycle. They represent hierarchical structure in a graphical form. Trees belong to the simplest class of graphs. Despite their simplicity, they have a rich structure. Trees provide a range of useful applications as simple as a family tree to as complex as trees in data structures of computer science. Tree A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree. The edges of a tree are known as branches. Elements of trees are called their nodes. The nodes without child nodes are called leaf nodes. A tree with ‘n’ vertices has ‘n-1’ edges. If it has one more edge extra than ‘n-1’, then the extra edge should obviously has to pair up with two vertices which leads to form a cycle. Then, it becomes a cyclic graph which is a violation for the tree graph. Example 1 The graph shown here is a tree because it has no cycles and it is connected. It has four vertices and three edges, i.e., for ‘n’ vertices ‘n-1’ edges as mentioned in the definition. Note − Every tree has at least two vertices of degree one. Example 2 In the above example, the vertices ‘a’ and ‘d’ has degree one. And the other two vertices ‘b’ and ‘c’ has degree two. This is possible because for not forming a cycle, there should be at least two single edges anywhere in the graph. It is nothing but two edges with a degree of one. Forest A disconnected acyclic graph is called a forest. In other words, a disjoint collection of trees is called a forest. Example The following graph looks like two sub-graphs; but it is a single disconnected graph. There are no cycles in this graph. Hence, clearly it is a forest. Spanning Trees Let G be a connected graph, then the sub-graph H of G is called a spanning tree of G if − H is a tree H contains all vertices of G. A spanning tree T of an undirected graph G is a subgraph that includes all of the vertices of G. Example In the above example, G is a connected graph and H is a sub-graph of G. Clearly, the graph H has no cycles, it is a tree with six edges which is one less than the total number of vertices. Hence H is the Spanning tree of G. Circuit Rank Let ‘G’ be a connected graph with ‘n’ vertices and ‘m’ edges. A spanning tree ‘T’ of G contains (n-1) edges. Therefore, the number of edges you need to delete from ‘G’ in order to get a spanning tree = m-(n-1), which is called the circuit rank of G. This formula is true, because in a spanning tree you need to have ‘n-1’ edges. Out of ‘m’ edges, you need to keep ‘n–1’ edges in the graph. Hence, deleting ‘n–1’ edges from ‘m’ gives the edges to be removed from the graph in order to get a spanning tree, which should not form a cycle. Example Take a look at the following graph − For the graph given in the above example, you have m=7 edges and n=5 vertices. Then the circuit rank is − G = m – (n – 1) = 7 – (5 – 1) = 3 Example Let ‘G’ be a connected graph with six vertices and the degree of each vertex is three. Find the circuit rank of ‘G’. By the sum of degree of vertices theorem, n Σ i=1 deg(Vi) = 2|E| 6 × 3 = 2|E| |E| = 9 Circuit rank = |E| – (|V| – 1) = 9 – (6 – 1) = 4 Kirchoff’s Theorem Kirchoff’s theorem is useful in finding the number of spanning trees that can be formed from a connected graph. Example The matrix ‘A’ be filled as, if there is an edge between two vertices, then it should be given as ‘1’, else ‘0’. $$A=begin{vmatrix}0 & a & b & c & d\a & 0 & 1 & 1 & 1 \b & 1 & 0 & 0 & 1\c & 1 & 0 & 0 & 1\d & 1 & 1 & 1 & 0 end{vmatrix} = begin{vmatrix} 0 & 1 & 1 & 1\1 & 0 & 0 & 1\1 & 0 & 0 & 1\1 & 1 & 1 & 0end{vmatrix}$$ By using kirchoff”s theorem, it should be changed as replacing the principle diagonal values with the degree of vertices and all other elements with -1.A $$=begin{vmatrix} 3 & -1 & -1 & -1\-1 & 2 & 0 & -1\-1 & 0 & 2 & -1\-1 & -1 & -1 & 3 end{vmatrix}=M$$ $$M=begin{vmatrix}3 & -1 & -1 & -1\-1 & 2 & 0 & -1\-1 & 0 & 2 & -1\-1 & -1 & -1 & 3 end{vmatrix} =8$$ $$Co::factor::of::m1::= begin{vmatrix} 2 & 0 & -1\0 & 2 & -1\-1 & -1 & 3end{vmatrix}$$ Thus, the number of spanning trees = 8. Print Page Previous Next Advertisements ”;

Graph Theory – Types of Graphs ”; Previous Next There are various types of graphs depending upon the number of vertices, number of edges, interconnectivity, and their overall structure. We will discuss only a certain few important types of graphs in this chapter. Null Graph A graph having no edges is called a Null Graph. Example In the above graph, there are three vertices named ‘a’, ‘b’, and ‘c’, but there are no edges among them. Hence it is a Null Graph. Trivial Graph A graph with only one vertex is called a Trivial Graph. Example In the above shown graph, there is only one vertex ‘a’ with no other edges. Hence it is a Trivial graph. Non-Directed Graph A non-directed graph contains edges but the edges are not directed ones. Example In this graph, ‘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 it is a non-directed graph, the edges ‘ab’ and ‘ba’ are same. Similarly other edges 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’. As it is a directed graph, each edge bears an arrow mark that shows its direction. Note that in a directed graph, ‘ab’ is different from ‘ba’. Simple Graph A graph with no loops and no parallel edges is called a simple graph. The maximum number of edges possible in a single graph with ‘n’ vertices is nC2 where nC2 = n(n – 1)/2. The number of simple graphs possible with ‘n’ vertices = 2nc2 = 2n(n-1)/2. Example In the following graph, there are 3 vertices with 3 edges which is maximum excluding the parallel edges and loops. This can be proved by using the above formulae. The maximum number of edges with n=3 vertices − nC2 = n(n–1)/2 = 3(3–1)/2 = 6/2 = 3 edges The maximum number of simple graphs with n=3 vertices − 2nC2 = 2n(n-1)/2 = 23(3-1)/2 = 23 8 These 8 graphs are as shown below − Connected Graph A graph G is said to be connected if there exists a path between every pair of vertices. There should be at least one edge for every vertex in the graph. So that we can say that it is connected to some other vertex at the other side of the edge. Example In the following graph, each vertex has its own edge connected to other edge. Hence it is a connected graph. Disconnected Graph 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, one with ‘a’, ‘b’, ‘c’, ‘d’ vertices and another with ‘e’, ’f’, ‘g’, ‘h’ vertices. The two components are independent and not connected to each other. Hence it is called disconnected graph. Example 2 In this example, there are two independent components, a-b-f-e and c-d, which are not connected to each other. Hence this is a disconnected graph. Regular Graph A graph G is said 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 the vertices have the same degree. So these graphs are called regular graphs. In both the graphs, all the vertices have degree 2. They are called 2-Regular Graphs. Complete Graph A simple graph with ‘n’ mutual vertices is called a complete graph and it is denoted by ‘Kn’. In the graph, a vertex should have edges with all other vertices, then it called a complete graph. In other words, if a vertex is connected to all other vertices in a graph, then it is called a complete graph. Example In the following graphs, each vertex in the graph is connected with all the remaining vertices in the graph except by itself. In graph I, a b c a Not Connected Connected Connected b Connected Not Connected Connected c Connected Connected Not Connected In graph II, p q r s p Not Connected Connected Connected Connected 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 (n >= 3) and ‘n’ edges is called a cycle graph if all its edges form a cycle of length ‘n’. If the degree of each vertex in the graph is two, then it is called a Cycle Graph. Notation − Cn Example Take a look at the following graphs − Graph I has 3 vertices with 3 edges which is forming a cycle ‘ab-bc-ca’. Graph II has 4 vertices with 4 edges which is forming a cycle ‘pq-qs-sr-rp’. Graph III has 5 vertices with 5 edges which is forming a cycle ‘ik-km-ml-lj-ji’. Hence all the given graphs are cycle graphs. Wheel Graph A wheel graph is obtained from a cycle graph Cn-1 by adding a new vertex. That new vertex is called a Hub which is connected to all the vertices of Cn. Notation − Wn No. of edges in Wn = No. of edges from hub to all other vertices + No. of edges from all other nodes in cycle graph without a hub. = (n–1) + (n–1) = 2(n–1) Example Take a look at the following graphs. They are all wheel graphs. In graph I, it is obtained from C3 by adding an vertex at the middle named as ‘d’. It is denoted as W4. Number of edges in W4 = 2(n-1) = 2(3) = 6 In graph II, it is obtained from C4 by adding a vertex at the middle named as ‘t’. It is denoted as W5. Number

Graph Theory – Connectivity ”; Previous Next Whether it is possible to traverse a graph from one vertex to another is determined by how a graph is connected. Connectivity is a basic concept in Graph Theory. Connectivity defines whether a graph is connected or disconnected. It has subtopics based on edge and vertex, known as edge connectivity and vertex connectivity. Let us discuss them in detail. Connectivity A graph is said to be connected if there is a path between every pair of vertex. From every vertex to any other vertex, there should be some path to traverse. That is called the connectivity of a graph. A graph with multiple disconnected vertices and edges is said to be disconnected. Example 1 In the following graph, it is possible to travel from one vertex to any other vertex. For example, one can traverse from vertex ‘a’ to vertex ‘e’ using the path ‘a-b-e’. Example 2 In the following example, traversing from vertex ‘a’ to vertex ‘f’ is not possible because there is no path between them directly or indirectly. Hence it is a disconnected graph. Cut Vertex Let ‘G’ be a connected graph. A vertex V ∈ G is called a cut vertex of ‘G’, if ‘G-V’ (Delete ‘V’ from ‘G’) results in a disconnected graph. Removing a cut vertex from a graph breaks it in to two or more graphs. Note − Removing a cut vertex may render a graph disconnected. A connected graph ‘G’ may have at most (n–2) cut vertices. Example In the following graph, vertices ‘e’ and ‘c’ are the cut vertices. By removing ‘e’ or ‘c’, the graph will become a disconnected graph. Without ‘g’, there is no path between vertex ‘c’ and vertex ‘h’ and many other. Hence it is a disconnected graph with cut vertex as ‘e’. Similarly, ‘c’ is also a cut vertex for the above graph. Cut Edge (Bridge) Let ‘G’ be a connected graph. An edge ‘e’ ∈ G is called a cut edge if ‘G-e’ results in a disconnected graph. If removing an edge in a graph results in to two or more graphs, then that edge is called a Cut Edge. Example In the following graph, the cut edge is [(c, e)]. By removing the edge (c, e) from the graph, it becomes a disconnected graph. In the above graph, removing the edge (c, e) breaks the graph into two which is nothing but a disconnected graph. Hence, the edge (c, e) is a cut edge of the graph. Note − Let ‘G’ be a connected graph with ‘n’ vertices, then a cut edge e ∈ G if and only if the edge ‘e’ is not a part of any cycle in G. the maximum number of cut edges possible is ‘n-1’. whenever cut edges exist, cut vertices also exist because at least one vertex of a cut edge is a cut vertex. if a cut vertex exists, then a cut edge may or may not exist. Cut Set of a Graph Let ‘G’= (V, E) be a connected graph. A subset E’ of E is called a cut set of G if deletion of all the edges of E’ from G makes G disconnect. If deleting a certain number of edges from a graph makes it disconnected, then those deleted edges are called the cut set of the graph. Example Take a look at the following graph. Its cut set is E1 = {e1, e3, e5, e8}. After removing the cut set E1 from the graph, it would appear as follows − Similarly, there are other cut sets that can disconnect the graph − E3 = {e9} – Smallest cut set of the graph. E4 = {e3, e4, e5} Edge Connectivity Let ‘G’ be a connected graph. The minimum number of edges whose removal makes ‘G’ disconnected is called edge connectivity of G. Notation − λ(G) In other words, the number of edges in a smallest cut set of G is called the edge connectivity of G. If ‘G’ has a cut edge, then λ(G) is 1. (edge connectivity of G.) Example Take a look at the following graph. By removing two minimum edges, the connected graph becomes disconnected. Hence, its edge connectivity (λ(G)) is 2. Here are the four ways to disconnect the graph by removing two edges − Vertex Connectivity Let ‘G’ be a connected graph. The minimum number of vertices whose removal makes ‘G’ either disconnected or reduces ‘G’ in to a trivial graph is called its vertex connectivity. Notation − K(G) Example In the above graph, removing the vertices ‘e’ and ‘i’ makes the graph disconnected. If G has a cut vertex, then K(G) = 1. Notation − For any connected graph G, K(G) ≤ λ(G) ≤ δ(G) Vertex connectivity (K(G)), edge connectivity (λ(G)), minimum number of degrees of G(δ(G)). Example Calculate λ(G) and K(G) for the following graph − Solution From the graph, δ(G) = 3 K(G) ≤ λ(G) ≤ δ(G) = 3 (1) K(G) ≥ 2 (2) Deleting the edges {d, e} and {b, h}, we can disconnect G. Therefore, λ(G) = 2 2 ≤ λ(G) ≤ δ(G) = 2 (3) From (2) and (3), vertex connectivity K(G) = 2 Print Page Previous Next Advertisements ”;

Graph Theory – Independent Sets ”; Previous Next Independent sets are represented in sets, in which there should not be any edges adjacent to each other. There should not be any common vertex between any two edges. there should not be any vertices adjacent to each other. There should not be any common edge between any two vertices. Independent Line Set Let ‘G’ = (V, E) be a graph. A subset L of E is called an independent line set of ‘G’ if no two edges in L are adjacent. Such a set is called an independent line set. Example Let us consider the following subsets − L1 = {a,b} L2 = {a,b} {c,e} L3 = {a,d} {b,c} In this example, the subsets L2 and L3 are clearly not the adjacent edges in the given graph. They are independent line sets. However L1 is not an independent line set, as for making an independent line set, there should be at least two edges. Maximal Independent Line Set An independent line set is said to be the maximal independent line set of a graph ‘G’ if no other edge of ‘G’ can be added to ‘L’. Example Let us consider the following subsets − L1 = {a, b} L2 = {{b, e}, {c, f}} L3 = {{a, e}, {b, c}, {d, f}} L4 = {{a, b}, {c, f}} L2 and L3 are maximal independent line sets/maximal matching. As for only these two subsets, there is no chance of adding any other edge which is not an adjacent. Hence these two subsets are considered as the maximal independent line sets. Maximum Independent Line Set A maximum independent line set of ‘G’ with maximum number of edges is called a maximum independent line set of ‘G’. Number of edges in a maximum independent line set of G (β1) = Line independent number of G = Matching number of G Example Let us consider the following subsets − L1 = {a, b} L2 = {{b, e}, {c, f}} L3 = {{a, e}, {b, c}, {d, f}} L4 = {{a, b}, {c, f}} L3 is the maximum independent line set of G with maximum edges which are not the adjacent edges in graph and is denoted by β1 = 3. Note − For any graph G with no isolated vertex, α1 + β1 = number of vertices in a graph = |V| Example Line covering number of Kn/Cn/wn, $$alpha 1 = lceilfrac{n}{2}rceilbegin{cases}frac{n}{2}:if:n:is:even \frac{n+1}{2}:if:n:is:oddend{cases}$$ Line independent number (Matching number) = β1 = [n/2] α1 + β1 = n. Independent Vertex Set Let ‘G’ = (V, E) be a graph. A subset of ‘V’ is called an independent set of ‘G’ if no two vertices in ‘S’ are adjacent. Example Consider the following subsets from the above graphs − S1 = {e} S2 = {e, f} S3 = {a, g, c} S4 = {e, d} Clearly S1 is not an independent vertex set, because for getting an independent vertex set, there should be at least two vertices in the from a graph. But here it is not that case. The subsets S2, S3, and S4 are the independent vertex sets because there is no vertex that is adjacent to any one vertex from the subsets. Maximal Independent Vertex Set Let ‘G’ be a graph, then an independent vertex set of ‘G’ is said to be maximal if no other vertex of ‘G’ can be added to ‘S’. Example Consider the following subsets from the above graphs. S1 = {e} S2 = {e, f} S3 = {a, g, c} S4 = {e, d} S2 and S3 are maximal independent vertex sets of ‘G’. In S1 and S4, we can add other vertices; but in S2 and S3, we cannot add any other vertex. Maximum Independent Vertex Set A maximal independent vertex set of ‘G’ with maximum number of vertices is called as the maximum independent vertex set. Example Consider the following subsets from the above graph − S1 = {e} S2 = {e, f} S3 = {a, g, c} S4 = {e, d} Only S3 is the maximum independent vertex set, as it covers the highest number of vertices. The number of vertices in a maximum independent vertex set of ‘G’ is called the independent vertex number of G (β2). Example For the complete graph Kn, Vertex covering number = α2 = n−1 Vertex independent number = β2 = 1 You have α2 + β2 = n In a complete graph, each vertex is adjacent to its remaining (n − 1) vertices. Therefore, a maximum independent set of Kn contains only one vertex. Therefore, β2=1 and α2=|v| − β2 = n-1 Note − For any graph ‘G’ = (V, E) α2 + β2 = |v| If ‘S’ is an independent vertex set of ‘G’, then (V – S) is a vertex cover of G. Print Page Previous Next Advertisements ”;

Graph Theory – Fundamentals ”; Previous Next A graph is a diagram of points and lines connected to the points. It has at least one line joining a set of two vertices with no vertex connecting itself. The concept of graphs in graph theory stands up on some basic terms such as point, line, vertex, edge, degree of vertices, properties of graphs, etc. Here, in this chapter, we will cover these fundamentals of graph theory. Point A point is a particular position in a one-dimensional, two-dimensional, or three-dimensional space. For better understanding, a point can be denoted by an alphabet. It can be represented with a dot. Example Here, the dot is a point named ‘a’. Line A Line is a connection between two points. It can be represented with a solid line. Example Here, ‘a’ and ‘b’ are the points. The link between these two points is called a line. Vertex A vertex is a point where multiple lines meet. It is also called a node. Similar to points, a vertex is also denoted by an alphabet. Example Here, the vertex is named with an alphabet ‘a’. Edge An edge is the mathematical term for a line that connects two vertices. Many edges can be formed from a single vertex. Without a vertex, an edge cannot be formed. There must be a starting vertex and an ending vertex for an edge. Example Here, ‘a’ and ‘b’ are the two vertices and the link between them is called an edge. Graph A graph ‘G’ is defined as G = (V, E) Where V is a set of all vertices and E is a set of all edges in the graph. Example 1 In the above example, ab, ac, cd, and bd are the edges of the graph. Similarly, a, b, c, and d are the vertices of the graph. Example 2 In this graph, there are four vertices a, b, c, and d, and four edges ab, ac, ad, and cd. Loop In a graph, if an edge is drawn from vertex to itself, it is called a loop. Example 1 In the above graph, V is a vertex for which it has an edge (V, V) forming a loop. Example 2 In this graph, there are two loops which are formed at vertex a, and vertex b. Degree of Vertex It is the number of vertices adjacent to a vertex V. Notation − deg(V). In a simple graph with n number of vertices, the degree of any vertices is − deg(v) ≤ n – 1 ∀ v ∈ G A vertex can form an edge with all other vertices except by itself. So the degree of a vertex will be up to the number of vertices in the graph minus 1. This 1 is for the self-vertex as it cannot form a loop by itself. If there is a loop at any of the vertices, then it is not a Simple Graph. Degree of vertex can be considered under two cases of graphs − Undirected Graph Directed Graph Degree of Vertex in an Undirected Graph An undirected graph has no directed edges. Consider the following examples. Example 1 Take a look at the following graph − In the above Undirected Graph, deg(a) = 2, as there are 2 edges meeting at vertex ‘a’. deg(b) = 3, as there are 3 edges meeting at vertex ‘b’. deg(c) = 1, as there is 1 edge formed at vertex ‘c’ So ‘c’ is a pendent vertex. deg(d) = 2, as there are 2 edges meeting at vertex ‘d’. deg(e) = 0, as there are 0 edges formed at vertex ‘e’. So ‘e’ is an isolated vertex. Example 2 Take a look at the following graph − In the above graph, deg(a) = 2, deg(b) = 2, deg(c) = 2, deg(d) = 2, and deg(e) = 0. The vertex ‘e’ is an isolated vertex. The graph does not have any pendent vertex. Degree of Vertex in a Directed Graph In a directed graph, each vertex has an indegree and an outdegree. Indegree of a Graph Indegree of vertex V is the number of edges which are coming into the vertex V. Notation − deg−(V). Outdegree of a Graph Outdegree of vertex V is the number of edges which are going out from the vertex V. Notation − deg+(V). Consider the following examples. Example 1 Take a look at the following directed graph. Vertex ‘a’ has two edges, ‘ad’ and ‘ab’, which are going outwards. Hence its outdegree is 2. Similarly, there is an edge ‘ga’, coming towards vertex ‘a’. Hence the indegree of ‘a’ is 1. The indegree and outdegree of other vertices are shown in the following table − Vertex Indegree Outdegree a 1 2 b 2 0 c 2 1 d 1 1 e 1 1 f 1 1 g 0 2 Example 2 Take a look at the following directed graph. Vertex ‘a’ has an edge ‘ae’ going outwards from vertex ‘a’. Hence its outdegree is 1. Similarly, the graph has an edge ‘ba’ coming towards vertex ‘a’. Hence the indegree of ‘a’ is 1. The indegree and outdegree of other vertices are shown in the following table − Vertex Indegree Outdegree a 1 1 b 0 2 c 2 0 d 1 1 e 1 1 Pendent Vertex By using degree of a vertex, we have a two special types of vertices. A vertex with degree one is called a pendent vertex. Example Here, in this example, vertex ‘a’ and vertex ‘b’ have a connected edge ‘ab’. So with respect to the vertex ‘a’, there is only one edge towards vertex ‘b’ and similarly with respect to the vertex ‘b’, there is only one edge towards vertex ‘a’. Finally, vertex ‘a’ and vertex ‘b’ has degree as one which are also called as the pendent vertex. Isolated Vertex A vertex with degree zero is called an isolated vertex. Example Here, the vertex ‘a’ and vertex

Graph Theory Tutorial PDF Version Quick Guide Resources Job Search Discussion This tutorial offers a brief introduction to the fundamentals of graph theory. Written in a reader-friendly style, it covers the types of graphs, their properties, trees, graph traversability, and the concepts of coverings, coloring, and matching. Audience This tutorial has been designed for students who want to learn the basics of Graph Theory. Graph Theory has a wide range of applications in engineering and hence, this tutorial will be quite useful for readers who are into Language Processing or Computer Networks, physical sciences and numerous other fields. Prerequisites Before you start with this tutorial, you need to know elementary number theory and basic set operations in Mathematics. It is mandatory to have a basic knowledge of Computer Science as well. Print Page Previous Next Advertisements ”;