CSC301 Lecture 10 Slides PDF

Lecture 10  GRAPH A graph is a pictorial and mathematical 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 or nodes and the links that connect the verti...

Lecture 10  GRAPH A graph is a pictorial and mathematical 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 or nodes and the links that connect the vertices are called edges or arcs or lines. In other words, a graph is an ordered pair G = (V, E) where, G specifies the graph V is the vertex-set whose elements are called the vertices, or nodes of the graph. This set is often denoted by V(G) or just V. E is the edge-set whose elements are called the edges, or connections between vertices of the graph. This set is often denoted by E(G) or just E. 2  GRAPH A graph consists of nodes (also called vertices) that are connected by edges (also called arcs). Graphs have a lot of key terms: When two nodes are connected by an edge, they are called neighbours The degree of a node is the number of other nodes that it is connected to (i.e. the number of neighbours that it has) A loop is an edge that connects a node to itself A path is a sequence of nodes that are connected by edges A cycle is a closed path, i.e. a path that starts and ends at the same node (and no node is visited more than once) 3  GRAPH Adjacent Vertices: Two vertices are said to be adjacent if there is an edge (arc) connecting them. Adjacent Edges: Adjacent edges are edges that share a common vertex. Degree of a Vertex: The degree of a vertex is the number of edges incident with that vertex. Path: A path is a sequence of vertices with the property that each vertex in the sequence is adjacent to the vertex next to it. A path that does not repeat vertices is called a simple path. Circuit: A circuit is path that begins and ends at the same vertex. 4  GRAPH Cycle: A circuit that doesn't repeat vertices is called a cycle. A Connected Graph: A graph is said to be connected if any two of its vertices are joined by a path. A graph that is not connected is a disconnected graph. A disconnected graph is made up of connected subgraphs that are called components. Bridge: A bridge is an edge whose deletion from a graph increases the number of components in the graph. If a graph was a connected graph then the removal of a bridge-edge disconnects it. Euler Path: An Euler path is a path that travels through all edges of a connected graph. Euler Circuit: An Euler circuit is a circuit that visits all edges of a connected graph. 5  GRAPH A graph is an abstract data type that can be used to represent complex, non-linear relationships between objects. A graph consists of nodes (also called vertices) that are connected by edges (also called arcs). 6  GRAPH Adjacency. If (u,v) is in the edge set we say u is adjacent to v (which we sometimes write as u ~ v). Has the following parts. The underlying set for the Verticies set is the integers. The Vertices set = {1,2,3,4,5,6} The Edge set = {(6,4),(4,5),(4,3),(3,2),(5,2),(2,1),(5,1)} 7  GRAPH A graph can be used to represent a wide variety of complex data relationships. For example: Social networking: the nodes could be individual people. An edge could represent that two people are acquaintances. Transport networks: the nodes could be towns. An edge could represent that a train line connects two towns. The internet: the nodes could be routers. An edge could represent that two routers are connected. The World Wide Web: the nodes could be webpages. An edge could represent that the pages are linked. 8  GRAPH TYPES OF GRAPH Cyclic Graph Null Graph Acyclic Graph Trivial Graph Bipartite Graph Simple Graph Complete Bipartite graph Undirected Graph Star Graph Directed Graph Weighted Graph Complete Graph Multi-graph Connected Graph Planar Graph Disconnected Graph Non - Planar Graph Regular Graph 9  GRAPH 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. 10  GRAPH Trivial Graph: A trivial graph is the graph which has only one vertex. The graph G has only one vertex 'v‘ without any edge. Therefore, it is a trivial graph. Simple Graph: A simple graph is the undirected graph with no parallel edges and no loops. A simple graph which has n vertices, the degree of every vertex is at most n -1. 11  GRAPH 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. 12  GRAPH Complete Graph: A graph in which every pair of vertices is joined by exactly one edge is called complete graph. A complete graph is graph where all vertices are connected by exactly one edge. 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 path exists between every pair of vertices. 13  GRAPH Disconnected Graph: A disconnected graph is a graph in which any path does not exist between every pair of vertices. The above graph consists of two independent components which are disconnected. Since it is not possible to visit from the vertices of one component to the vertices of other components therefore, it is a disconnected graph. 14  GRAPH 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. 15  GRAPH 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. 16  GRAPH Acyclic Graph: A graph which does not contain any cycle in it is called as an acyclic graph. 17  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. A graph G (V, E) is called bipartite graph if its vertex-set V(G) can be decomposed into two non-empty disjoint subsets V1(G) and V2(G) in such a way that each edge e ∈ E(G) has its one last joint in V1(G) and other last point in V2(G). The partition V = V1 ∪ V2 is known as bipartition of G. 18  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. A graph G (V, E) is called bipartite graph if its vertex-set V(G) can be decomposed into two non-empty disjoint subsets V1(G) and V2(G) in such a way that each edge e ∈ E(G) has its one last joint in V1(G) and other last point in V2(G). The partition V = V1 ∪ V2 is known as bipartition of G. 19  GRAPH 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. A complete bipartite graph is a bipartite graph which is complete. 20  GRAPH Star Graph: A star graph is a complete bipartite graph in which n-1 vertices have degree 1 and a single vertex have degree (n -1). This exactly looks like a star where (n - 1) vertices are connected to a single central vertex. A star graph with n vertices is denoted by Sn. 21  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. The length of Path a -> b -> c -> d -> e -> g = 5 + 4 + 5 + 6 + 5 = 25. 22  GRAPH 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. In the above graph, vertex-set B and C are connected with two edges. Similarly, vertex sets E and F are connected with 3 edges. Therefore, it is a multi graph. 23  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. 24  GRAPH 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 25  GRAPH Basic Properties of Graph Theory Following are some basic properties of graph theory: Distance between two vertices: Distance is basically the number of edges in a shortest path between vertex X and vertex Y. If there are many paths connecting two vertices, then the shortest path is considered as the distance between the two vertices. Distance between two vertices is denoted by d(X, Y). Find d(c, g) d(a, g) d(a, e) 26  GRAPH Eccentricity of a vertex: Eccentricity of a vertex is the maximum distance between a vertex to all other vertices. It is denoted by e(V). To count the eccentricity of vertex, we have to find the distance from a vertex to all other vertices and the highest distance is the eccentricity of that particular vertex. if we want to find the maximum eccentricity of vertex 'a' then: The distance from vertex a to b is 1 (i.e. ab) The distance from vertex a to c is 1 (i.e. ac) The distance from vertex a to f is 2 (i.e. ac -> cf or ad -> df) The distance from vertex a to d is 1 (i.e. ad) The distance from vertex a to e is 2 (i.e. ab -> be or ad -> de) The distance from vertex a to g is 3 (i.e. ab -> be -> eg or ac -> cf -> fg etc.) Hence, the maximum eccentricity of vertex 'a' is 3 27  GRAPH Radius of connected Graph: The radius of a connected graph is the minimum eccentricity from all the vertices. In other words, the minimum among all the distances between a vertex to all other vertices is called as the radius of the graph. It is denoted by r(G). e(a) = 3 e(b) = 3 e(c) = 3 e(d) = 2 e(e) = 3 e(f) = 3 e(g) = 3 r(G) = 2, which is the minimum eccentricity for the vertex 'd' 28  GRAPH Diameter of a Graph: Diameter of a graph is the maximum eccentricity from all the vertices. In other words, the maximum among all the distances between a vertex to all other vertices is considered as the diameter of the graph G. It is denoted by d(G). e(a) = 3 e(b) = 3 e(c) = 3 e(d) = 2 e(e) = 3 e(f) = 3 e(g) = 3 Diameter of graph d(G) = 3, which is the maximum eccentricity. 29  GRAPH Central point: If the eccentricity of the graph is equal to its radius, then it is known as central point of the graph. It consists of all the vertices whose eccentricity is minimum. Here the eccentricity is equal to the radius. e(a) = 3 e(b) = 3 e(c) = 3 e(d) = 2 e(e) = 3 e(f) = 3 e(g) = 3 'd' is the central point of the graph 30  GRAPH Circumference: The total number of edges in the longest cycle of graph G is known as the circumference of G. The circumference is 6, which is derived from the longest path a -> c -> f -> g -> e -> b -> a or a -> c -> f -> d -> e -> b -> a. 31  GRAPH Find r(G) and d(G) 32  GRAPH 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. There are different ways to optimally represent a graph, depending on the density of its edges, type of operations to be performed and ease of use. 33  GRAPH Graph Representations Adjacency Matrix Incidence Matrix Adjacency List 34  GRAPH 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 nXn 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. 35  GRAPH Directed graph representation 36  GRAPH Undirected graph representation 37  GRAPH Undirected graph representation 38  GRAPH Undirected Weighted graph representation 39  GRAPH Directed Weighted graph representation 40  GRAPH Incidence Matrix In Incidence matrix representation, graph can be represented using a matrix of size: Total number of vertices by total number of edges. It means if a graph has 4 vertices and 6 edges, then it can be represented using a matrix of 4X6 class. In this matrix, columns represent edges and rows represent vertices. 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 edge41 which is connected as  GRAPH Incidence Matrix 42  GRAPH Incidence Matrix 43  GRAPH 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. 44  GRAPH Adjacency List 45  GRAPH UNDIRECTED 46 GRAPH 47