1) Unit 1.pdf

Introduction Graph: A graph is a data structure that is defined by two components.  A node or a vertex.  An edge E or ordered pair is a connection between two nodes u, v that is identified by unique pair(u, v). The pair (u, v) is ordered because (u, v) is not same as (v, u) in case of directed...

Introduction Graph: A graph is a data structure that is defined by two components.  A node or a vertex.  An edge E or ordered pair is a connection between two nodes u, v that is identified by unique pair(u, v). The pair (u, v) is ordered because (u, v) is not same as (v, u) in case of directed graph. The edge may have a weight or is set to one in case of unweighted graph. Applications: Graph is a data structure which is used extensively in our real-life.  Social Network: Each user is represented as a node and all their activities,suggestion and friend list are represented as an edge between the nodes.  Google Maps: Various locations are represented as vertices or nodes and the roads are represented as edges and graph theory is used to find shortest path between two nodes.  Recommendations on e-commerce websites: The “Recommendations for you” section on various e-commerce websites uses graph theory to recommend items of similar type to user’s choice.  Graph theory is also used to study molecules in chemistry and physics. Characteristics:  Adjacent node: A node ‘v’ is said to be adjacent node of node ‘u’ if and only if there exists an edge between ‘u’ and ‘v’.  Degree of a node: In an undirected graph the number of nodes incident on a node is the degree of the node. In case of directed graph, Indegree of the node is the number of arriving edges to a node. Outdegree of the node is the number of departing edges to a node. Note: 1. a self-loop is counted twice. 2. the sum of degree of all the vertices in a graph G is even. Types of Graphs:  Null Graph: A null graph is a graph in which there are no edges between its vertices. A null graph is also called empty graph. A null graph with n vertices is denoted by Nn.  Trivial Graph: A trivial graph is the graph which has only one vertex.  Simple Graph: A simple graph is the undirected graph with no parallel edges and no loops.  Undirected Graph: An undirected graph is a graph whose edges are not directed.  Directed Graph: A directed graph is a graph in which the edges are directed by arrows. Directed graph is also known as digraphs.  Complete Graph: A graph in which every pair of vertices is joined by exactly one edge is called complete graph. It contains all possible edges.  Regular Graph: A Regular graph is a graph in which degree of all the vertices is same. If the degree of all the vertices is k, then it is called k-regular graph.  Connected Graph: A connected graph is a graph in which we can visit from any one vertex to any other vertex. In a connected graph, at least one edge or path exists between every pair of vertices.  Disconnected Graph: A disconnected graph is a graph in which any path does not exist between every pair of vertices.  Cyclic Graph: A graph with 'n' vertices (where, n>=3) and 'n' edges forming a cycle of 'n' with all its edges is known as cycle graph. A graph containing at least one cycle in it is known as a cyclic graph. In the cycle graph, degree of each vertex is 2. The cycle graph which has n vertices is denoted by Cn.  Acyclic Graph: A graph which does not contain any cycle in it is called as an acyclic graph.  Bipartite Graph: A bipartite graph is a graph in which the vertex set can be partitioned into two sets such that edges only go between sets, not within them.  Complete Bipartite Graph: A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to each vertex in the second set by exactly one edge. Complete Bipartite graph = Bipartite graph + Complete graph  Weighted Graph: A weighted graph is a graph whose edges have been labeled with some weights or numbers. The length of a path in a weighted graph is the sum of the weights of all the edges in the path.  Multi-graph: A graph in which there are multiple edges between any pair of vertices or there are edges from a vertex to itself (loop) is called a multi - graph.  Planar Graph: A planar graph is a graph that we can draw in a plane in such a way that no two edges of it cross each other except at a vertex to which they are incident. The graph may not seem to be planar because it has edges crossing each other. But we can redraw the above graph. The three plane drawings of the above graph are  Non - Planar Graph: A graph that is not a planar graph is called a non-planar graph. In other words, a graph that cannot be drawn without at least on pair of its crossing edges is known as non-planar graph.  Walk: A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we get a walk. Edge and Vertices both can be repeated. Here, 1->2->3->4->2->1->3 is a walk.  Open walk: A walk is said to be an open walk if the starting and ending vertices are different i.e. the origin vertex and terminal vertex are different.  Closed walk: A walk is said to be a closed walk if the starting and ending vertices are identical i.e. if a walk starts and ends at the same vertex, then it is said to be a closed walk. In the above diagram: 1->2->3->4 is an open walk. 1->2->3->4->2->1 is a closed walk.  Trail: Trail is an open walk in which no edge is repeated. Vertex can be repeated. There is a tail, which is described as follows: Trail = A, C, H, F, C, B  Circuit: A circuit can be described as a closed walk where no edge is allowed to repeat. In the circuit, the vertex can be repeated. A closed trail in the graph theory is also known as a circuit. There is a circuit, which is described as follows: Circuit: A, B, D, C, F, H, C, A  Path: A path is a type of open walk where neither edges nor vertices are allowed to repeat. There is a possibility that only the starting vertex and ending vertex are the same in a path. In an open walk, the length of the walk must be more than 0. There is a path, which is described as follows: Path: F, H, C, A, B, D  Operations on Graphs (Union, Intersection, Ring Sum):  Operations on Graphs (Deletion):  Operations on Graphs (Fusion of vertices):  Operations on Graphs (Complement): The simple graph is indicated as G, and the Complement of this graph is indicated as G`. If G` is the complement of a simple graph G, then it must contain the following things:  The complement graph must contain all the vertices of graph G.  If there are two vertices v and w and the original graph G does not contain any edge between these vertices, in this case, the complement graph must contain an edge between these two vertices v and w. Relation between G and G`: A simple graph G and complement graph G` contains some relations, which are described as follows:  The number of vertices in graph G equals to the number of vertices in its complement graph G1`. The symbolic representation of this relation is described as follows: |V(G)| = |V(G`)|  The sum of total number of edges in both the graphs, i.e., simple graph G and its complement graph G` will equal to the total number of edges in a complete graph. The symbolic representation of this relation is described as follows: |E(G)| +|E(G`)| = C(n, 2) = n(n-1) /2 Here n is used to indicate the total number of vertices in the graph Note: Size of the graph will be equal to the total number of edges in the graph. Same as the Order of graph will be equal to the number of vertices in the graph. Relation between G and G`: A simple graph G and complement graph G` contains some relations, which are described as follows:  The number of vertices in graph G equals to the number of vertices in its complement graph G1`. The symbolic representation of this relation is described as follows: |V(G)| = |V(G`)|  The sum of total number of edges in both the graphs, i.e., simple graph G and its complement graph G` will equal to the total number of edges in a complete graph. The symbolic representation of this relation is described as follows: |E(G)| +|E(G`)| = C(n, 2) = n(n-1) /2 Here n is used to indicate the total number of vertices in the graph Note: Size of the graph will be equal to the total number of vertices in the graph. Same as the Order of graph will be equal to the number of vertices in the graph. Graph Isomorphism:  The isomorphism graph can be described as a graph in which a single graph can have more than one form.  That means two different graphs can have the same number of edges, vertices, and same edges connectivity.  These types of graphs are known as isomorphism graphs. Conditions for graph isomorphism: Any two graphs will be known as isomorphism if they satisfy the following four conditions:  There will be an equal number of vertices in the given graphs.  There will be an equal number of edges in the given graphs.  There will be an equal amount of degree sequence in the given graphs.  If the first graph is forming a cycle of length k with the help of vertices {v1, v2, v3, …. vk}, then another graph must also form the same cycle of the same length k with the help of vertices {v1, v2, v3, …. vk}. Sufficient Conditions for Graph isomorphism:  If the complement graphs of both the graphs are isomorphism, then these graphs will surely be an isomorphism. Example for graph isomorphism: Checking whether the following graphs are isomorphism Condition 1: In graph 1, there is a total 4 number of vertices, i.e., G1 = 4. In graph 2, there is a total 4 number of vertices, i.e., G2 = 4. In graph 3, there is a total 4 number of vertices, i.e., G3 = 4. There are an equal number of vertices in all graphs G1, G2 and G3. So these graphs satisfy condition 1. Now we will check the second condition. Example for graph isomorphism: Condition 2: In graph 1, there is a total 5 number of edges, i.e., G1 = 5. In graph 2, there is a total 5 number of edges, i.e., G2 = 5. In graph 3, there is a total 4 number of edges, i.e., G2 = 4. There are an equal number of edges in both graphs G1 and G2. So these graphs satisfy condition 2. But there does not have an equal number of edges in the graphs (G1, G2) and G3. So the graphs (G1, G2) and G3 do not satisfy condition 2. Example for graph isomorphism: Condition 3: In the graph 1, the degree of sequence s is {2, 2, 3, 3}, i.e., G1 = {2, 2, 3, 3}. In the graph 2, the degree of sequence s is {2, 2, 3, 3}, i.e., G2 = {2, 2, 3, 3}. There are an equal number of degree sequences in both graphs G1 and G2. So these graphs satisfy condition 3. Now we will check the fourth condition. Example for graph isomorphism: Condition 4: Graph G1 forms a cycle of length 3 with the help of vertices {2, 3, 3}. Graph G2 also forms a cycle of length 3 with the help of vertices {2, 3, 3}. It shows that both the graphs contain the same cycle because both graphs G1 and G2 are forming a cycle of length 3 with the help of vertices {2, 3, 3}. So these graphs satisfy condition 4. Thus, The graphs G1 and G2 satisfy all the above four necessary conditions. So G1 and G2 may be an isomorphism. Example for graph isomorphism: Checking Sufficient Conditions: Graphs G1 and G2 are isomorphism. Example for graph isomorphism: Euler Graph: If all the vertices of any connected graph have an even degree, then this type of graph will be known as the Euler graph. In other words, we can say that an Euler graph is a type of connected graph which have the Euler circuit. The above graph is a connected graph, and the vertices of this graph contain the even degree. Hence we can say that this graph is an Euler graph. In other words, we can say that this graph is an Euler graph because it has the Euler circuit as BACEDCB. Euler Path: We can also call the Euler path as Euler walk or Euler Trail. The definition of Euler trail and Euler walk is described as follows:  If there is a connected graph with a trail that has all the edges of the graph, then that type of trail will be known as the Euler trail.  If there is a connected graph, which has a walk that passes through each and every edge of the graph only once, then that type of walk will be known as the Euler walk. Example: Euler path = BCDBAD Example: Euler path = BCDFBEDAB Example: if we begin our path from A, then we can only go to vertex A, C, D or B, C, E. That means this graph cannot visit all the edges only once. So the above graph does not contain an Euler path. Euler Circuit: We can also call the Euler circuit as Euler Tour and Euler Cycle. There are various definitions of the Euler circuit, which are described as follows:  If there is a connected graph with a circuit that has all the edges of the graph, then that type of circuit will be known as the Euler circuit.  If there is a connected graph, which has a walk that passes through each and every edge of the graph only once, then that type of walk will be known as the Euler circuit. In this walk, the starting vertex and ending vertex must be the same, and this walk can contain the repeated vertex, but it is not compulsory.  If an Euler trail contains the same vertex at the start and end of the trail, then that type of trail will be known as the Euler Circuit.  A closed Euler trail will be known as the Euler Circuit. Note: If all the vertices of the graph contain the even degree, then it will coitain the Euler circuit. Euler Circuit: Graph does not contain an Euler circuit. Euler circuit = ABCDFBEDA Semi Euler Circuit: If there is a connected graph that does not have an Euler circuit, but it has an Euler trail, then that type of graph will be known as the semi-Euler graph. Any graph will be known as semi Euler graph if it satisfies two conditions, which are described as follows:  For this, the graph must be connected  This graph must contain an Euler trail Hamiltonian Graph:  The graph will be known as a Hamiltonian graph if there is a closed walk in a connected graph, which passes each and every vertex of the graph exactly once except the root vertex or starting vertex.  The Hamiltonian walk must not repeat any edge.  One more definition of a Hamiltonian graph says a graph will be known as a Hamiltonian graph if there is a connected graph, which contains a Hamiltonian circuit. There is a closed walk ABCDEFA. Hamiltonian Path:  In a connected graph, if there is a walk that passes each and every vertex of a graph only once, this walk will be known as the Hamiltonian path.  In this walk, the edges should not be repeated.  If a connected graph contains a Path with all the vertices of the graph, this type of path will be known as the Hamiltonian path. Example: In the following graph, we have 5 nodes. Now we have to determine whether this graph contains a Hamiltonian path. Hamiltonian path = ABCDE Example: In the following graphs, Now we have to determine whether this graph contains a Hamiltonian path. Hamiltonian path = EABCD Not contain a Hamiltonian path Hamiltonian Circuit:  In a connected graph, if there is a walk that passes each and every vertex of the graph only once and after completing the walk, return to the starting vertex, then this type of walk will be known as a Hamiltonian circuit.  For the Hamiltonian circuit, there must be no repeated edges.  We can also be called Hamiltonian circuit as the Hamiltonian cycle. Note:  If there is a Hamiltonian path that begins and ends at the same vertex, then this type of cycle will be known as a Hamiltonian circuit.  In the connected graph, if there is a cycle with all the vertices of the graph, this type of cycle will be known as a Hamiltonian circuit.  A closed Hamiltonian path will also be known as a Hamiltonian circuit. Example: In the following graphs, we have 5 nodes. Now we have to determine whether this graph contains a Hamiltonian circuit. Hamiltonian circuit = ABCDEA Not contain a Hamiltonian circuit Example: In the following graph, we have 6 nodes. Now we have to determine whether this graph contains a Hamiltonian circuit. Not contain a Hamiltonian circuit Important Points:  If we remove one of the edges of Hamiltonian path, then it will be converted into any Hamiltonian circuit.  If any graph has a Hamiltonian circuit, then it will also have the Hamiltonian path. But the vice versa in this case will not be possible.  A graph can contain more than one Hamiltonian path and Hamiltonian circuit. Example: In the following graphs, Now we have to determine whether this graph is a Hamiltonian graph. Example: In the following graphs, Now we have to determine whether this graph is a Hamiltonian graph. Directed Graph: A directed graph is defined as a type of graph where the edges have a direction associated with them. Characteristics of Directed Graph:  Directed edges: In a directed graph, edges have a direction associated with them, indicating a one-way relationship between vertices.  Indegree and Outdegree: Each vertex in a directed graph has two different degree measures: indegree and outdegree. Indegree is the number of incoming edges to a vertex, while outdegree is the number of outgoing edges from a vertex.  Cycles: A directed graph can contain cycles, which are paths that start and end at the same vertex and contain at least one edge. Cycles can be important for understanding feedback loops or other patterns in the graph.  Paths and reachability: Paths in a directed graph follow the direction of the edges, and can be used to analyze reachability between vertices. Applications of Directed Graph:  Social networks: Social networks are often modeled as directed graphs, where each person is a vertex and relationships such as friendships or following are represented as edges.  Transportation networks: Transportation systems such as roads, airports, or subway systems can be modeled as directed graphs, with vertices representing locations and edges representing connections between them.  Computer networks: Computer networks such as the internet can be represented as directed graphs, with vertices representing devices such as computers or routers and edges representing connections between them.  Project management: Project management can be modeled as a directed graph, with vertices representing tasks and edges representing dependencies between them. Advantages of Directed Graph:  Directed graphs are useful for modeling complex relationships where directionality is important, such as social networks or transportation systems.  Directed graphs allow for analysis of the flow of relationships or information in a system, which can be useful for optimization or understanding of the system’s behavior.  Directed graphs are useful for representing dependencies between entities, such as in project management or recommender systems. Disadvantages of Directed Graph:  Directed graphs can be more complex than undirected graphs, since each edge has a direction associated with it.  Analyzing directed graphs may require more processing power than analyzing undirected graphs, since the directionality of the edges must be taken into account.  Since directed graphs are less common than undirected graphs, they may be less intuitive for people to work with or understand. Graph Representations:  In graph theory, a graph representation is a technique to store graph into the memory of computer.  To represent a graph, we just need the set of vertices, and for each vertex the neighbors of the vertex (vertices which is directly connected to it by an edge).  If it is a weighted graph, then the weight will be associated with each edge.  Mainly three ways to represent:  Adjacency Matrix  Incidence Matrix  Adjacency List Adjacency Matrix:  Adjacency matrix is a sequential representation.  It is used to represent which nodes are adjacent to each other. i.e. is there any edge connecting nodes to a graph.  In this representation, we have to construct a n x n matrix A. If there is any edge from a vertex i to vertex j, then the corresponding element of A, ai,j = 1, otherwise ai,j= 0.  If there is any weighted graph then instead of 1s and 0s, we can store the weight of the edge. Adjacency Matrix: Undirected graph representation: Directed graph representation: Adjacency Matrix: Undirected weighted graph representation: Pros: Representation is easier to implement and follow. Cons: It takes a lot of space and time to visit all the neighbors of a vertex, we have to traverse all the vertices in the graph, which takes quite some time. Incidence Matrix:  Graph can be represented using a matrix of size.  Total number of vertices by total number of edges.  This matrix is filled with either 0 or 1 or -1. Where,  0 is used to represent row edge which is not connected to column vertex.  1 is used to represent row edge which is connected as outgoing edge to column vertex.  -1 is used to represent row edge which is connected as incoming edge to column vertex. Incidence Matrix: Consider the following directed graph representation. Adjacency List:  Adjacency list is a linked representation.  In this representation, for each vertex in the graph, we maintain the list of its neighbors. It means, every vertex of the graph contains list of its adjacent vertices.  We have an array of vertices which is indexed by the vertex number and for each vertex v, the corresponding array element points to a singly linked list of neighbors of v. Pros:  Adjacency list saves lot of space.  We can easily insert or delete as we use linked list.  Such kind of representation is easy to follow and clearly shows the adjacent nodes of node. Cons:  The adjacency list allows testing whether two vertices are adjacent to each other but it is slower to support this operation. Adjacency List :