02 Graph Theory - II PDF

I NTRODUCTION TO G RAPH T HEORY Renjith P. NITC Introduction to Graph Theory 1 / 33 Special Graphs ? Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets such that each edge connects a vertex in one of these subsets...

I NTRODUCTION TO G RAPH T HEORY Renjith P. NITC Introduction to Graph Theory 1 / 33 Special Graphs ? Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets such that each edge connects a vertex in one of these subsets to a vertex in the other subset ? Job Assignments ? The graph representing marriages between men and women in a village ? Time slot - event allocation ? Scheduling Jobs to machines ? Objects and actions in a AR environment NITC Introduction to Graph Theory 2 / 33 Bipartite Graphs ? A simple graph G is called Bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2). When this condition holds, we call the pair (V1, V2) a bipartition of the vertex set V of G. ? An even cycle Cn , n is even, is a bipartite graph ? C3 , C5 ,... are not bipartite NITC Introduction to Graph Theory 3 / 33 Bipartite Graphs ? Which among the following are bipartite A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color NITC Introduction to Graph Theory 4 / 33 Complete Bipartite Graphs ? A complete bipartite graph Km,n is a graph that has its vertex set partitioned into two subsets of m and n vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset. ? The complete bipartite graphs K2,3 , K3,3 , K3,5 , and K2,6 NITC Introduction to Graph Theory 5 / 33 Sub-Graphs A subgraph of a graph G (V , E) is a graph H (W, F ), where W ⊆ V and F ⊆ E A subgraph H of G is a proper subgraph of G if H 6= G. Let G (V , E) be a simple graph. The subgraph induced by a subset W of the vertex set V is the graph (W, F ), where the edge set F contains an edge in E if and only if both endpoints of this edge are in W ? When we remove a vertex v and all edges incident to it from G (V , E), we produce a subgraph, denoted by G - v NITC Introduction to Graph Theory 6 / 33 Union of two Graphs The union of two simple graphs G1 (V1, E1) and G2 (V2, E2) is the simple graph with vertex set V1 ∪ V2 and edge set E1 ∪ E2. The union of G1 and G2 is denoted by G1 ∪ G2 ? The complementary graph G of a simple graph G has the same vertices as G. Two vertices are adjacent in G if and only if they are not adjacent in G NITC Introduction to Graph Theory 7 / 33 Graph Isomorphism The simple graphs G1 (V1, E1) and G2 (V2, E2) are isomorphic if there exists a one-to-one and onto function f from V1 to V2 with the property that a and b are adjacent in G1 if and only if f(a) and f(b) are adjacent in G2, for all a and b in V1. Such a function f is called an isomorphism. ? Two simple graphs that are not isomorphic are called nonisomorphic ? Isomorphic simple graphs must have the same number of vertices ? Isomorphic simple graphs must have the same number of edges ? In addition, the degrees of the vertices in isomorphic simple NITC graphs must be the same Introduction to Graph Theory 8 / 33 Graph Isomorphism - Some Practice Questions NITC Introduction to Graph Theory 9 / 33 Graph Isomorphism - Some Practice Questions A simple graph G is called self-complementary if G and G are isomor- phic (P3 , C5 ) NITC Introduction to Graph Theory 10 / 33 Graphic Sequence ? The degree sequence of a graph is the list of vertex degrees, usually written in nonincreasing order, as d1 ≥ · · · ≥ dn ? Every graph has a degree sequence ? A graphic sequence is a list of nonnegative numbers that is the degree sequence of some simple graph ? Not all sequences are graphic ? For a graph G, min degree: δ(G ) or simply δ max degree: ∆(G ) or simply ∆ Havel Hakimi Theorem For n > 1, an integer list d of size n is graphic if and only if d’ is graphic, where d’ is obtained from d by deleting its largest element ∆ and subtracting 1 from its ∆ next largest elements NITC Introduction to Graph Theory 11 / 33 Graphic Sequence Havel Hakimi Theorem For n > 1, d1 ≥ · · · ≥ dn is graphic if and only if d2 − 1 ≥ d3 − 1 ≥ · · · dd1 +1 − 1 ≥ dd1 +2 ≥ · · · ≥ dn is graphic ? Which of the following are graphic sequences? 1 (5,5,4,3,2,2,2,1) 2 (5,5,4,4,2,2,1,1) 3 (5,5,5,3,2,2,1,1) 4 (5,5,5,4,2,1,1,1) NITC Introduction to Graph Theory 12 / 33 Graphic Sequence Every simple graph with at least two vertices has two vertices of equal degree ? A simple graph is called regular if every vertex of this graph has the same degree. ? A regular graph is called n-regular if every vertex in this graph has degree n. ? For which values of n are these graphs regular? a) Kn b) Cn c) Wn d) Qn NITC Introduction to Graph Theory 13 / 33 Practice Questions ? For which values of n are these graphs bipartite? a) Kn b) Cn c) Wn d) Qn ? Find the degree sequence of each of the following graphs. a) K5 b) C6 c) W4 d) Q3 ? How many edges does a graph have if its degree sequence is 4, 3, 3, 2, 2? ? Determine whether each of these sequences is graphic. For those that are, draw a graph having the given degree sequence. ? How many vertices does a regular graph of degree four with 10 edges have? ? Describe each of these graphs. a) Kn b) Km,n ? Prove or disprove: Complement of a regular graph is regular. ? If G is a simple graph with 15 edges and G has 13 edges, how many vertices does G have? NITC Introduction to Graph Theory 14 / 33 Practice Questions ? If the simple graph G has v vertices and e edges, how many edges does G have? ? If the degree sequence of the simple graph G is 4, 3, 3, 2, 2, what is the degree sequence of G ? ? If the degree sequence of the simple graph G is d1, d2,...,dn, what is the degree sequence of G ? ? How many nonisomorphic simple graphs are there with n vertices, when n is a) 2? b) 3? c) 4? NITC Introduction to Graph Theory 15 / 33 Paths and Related Terminology ? A walk is defined to be an alternating sequence of vertices and edges of a graph, v0 , e1 , v1 , e2 ,... , vn−1 , en , vn , where vi−1 and vi are the endpoints of ei for i = 1, 2,... , n ? A closed walk is a walk with the same end vertices ? A trail is used to denote a walk that has no repeated edge ? A closed trail is called a circuit ? A path is a trail with no repeated vertices ? We denote a path by its vertex sequence x0 , x1 ,..., xn−1 , xn NITC Introduction to Graph Theory 16 / 33 Connected Graph ? An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph ? An undirected graph that is not connected is called disconnected ? There is a simple path between every pair of distinct vertices of a connected undirected graph NITC Introduction to Graph Theory 17 / 33 Components of a Graph ? A connected component of a graph G is a connected subgraph of G that is not a proper subgraph of another connected subgraph of G ? A connected component of a graph G is a maximal connected subgraph of G NITC Introduction to Graph Theory 18 / 33 Cut vertex and Cut edge ? A vertex whose removal produces a graph with more connected components than in the original graph is called a cut vertex (or articulation point). ? The removal of a cut vertex from a connected graph produces a subgraph that is not connected ? An edge whose removal produces a graph with more connected components than in the original graph is called a cut edge or bridge ? If the graph has more than two vertices, then at least one end point of a bridge is a cut vertex NITC Introduction to Graph Theory 19 / 33 Nonseparable Graphs ? Not all graphs have cut vertices The complete graph Kn , where n ≥ 3, has no cut vertices ? Connected graphs without cut vertices are called nonseparable graphs ? We measure the graph connectivity based on the minimum number of vertices that can be removed to disconnect a graph ? A subset V’ of the vertex set V of G (V , E) is a vertex cut, or separating set, if G - V’ is disconnected ? We define the vertex connectivity of a noncomplete graph G, denoted by κ(G ), as the minimum number of vertices in a vertex cut NITC Introduction to Graph Theory 20 / 33 k-connected graph ? Disconnected graphs and K1 have κ(G ) = 0 ? Connected graphs with cut vertices and K2 have κ(G ) = 1 ? Graphs without cut vertices that can be disconnected by removing two vertices and K3 have κ(G ) = 2 ? We say that a graph is k-connected (or k-vertex-connected), if κ(G ) ≥ k ? A graph G is 1-connected if it is connected and not a graph containing a single vertex ? A graph is 2-connected, or biconnected, if it is nonseparable and has at least three vertices NITC Introduction to Graph Theory 21 / 33 Edge Connectivity ? If G does not have a cut edge, we look for the smallest set of edges that can be removed to disconnect it ? A set of edges E’ is called an edge cut of G if the subgraph G - E’ is disconnected ? The edge connectivity of a graph G, denoted by λ(G ), is the minimum number of edges in an edge cut of G ? κ(G ) ≤ λ(G ) ≤ δ(G ) NITC Introduction to Graph Theory 22 / 33 Connectedness in Directed Graphs ? A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph ? A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph NITC Introduction to Graph Theory 23 / 33 Practice Questions ? Isomorphic or not NITC Introduction to Graph Theory 24 / 33 Practice Questions ? Isomorphic or not NITC Introduction to Graph Theory 25 / 33 Practice Questions ? Isomorphic or not NITC Introduction to Graph Theory 26 / 33 Practice Questions ? Isomorphic or not NITC Introduction to Graph Theory 27 / 33 Practice Questions ? Isomorphic or not NITC Introduction to Graph Theory 28 / 33 Practice Questions ? Connected or not NITC Introduction to Graph Theory 29 / 33 Practice Questions ? Strongly Connected or Weakly Connected NITC Introduction to Graph Theory 30 / 33 Practice Questions ? Strongly Connected or Weakly Connected NITC Introduction to Graph Theory 31 / 33 Practice Questions ? Strongly Connected or Weakly Connected NITC Introduction to Graph Theory 32 / 33 Practice Questions ? Cut vertices and Cut edges NITC Introduction to Graph Theory 33 / 33