Transcription
CS 2336Discrete MathematicsLecture 13Graphs: Introduction1
Outline What is a Graph?TerminologySome Special Simple GraphsSubgraphs and ComplementsGraph Isomorphism2
What is a Graph ?A graph consists of a nonempty set V of verticesand a set E of edges, where each edge in Econnects two (may be the same) vertices in V. Let G be a graph associated with a vertex set Vand an edge set EWe usually write G (V, E) to indicate the aboverelationship3
Examplesab12wxcd34yz Furthermore, if each edge connects two differentvertices, and no two edges connect the same pairof vertices, then the graph is a simple graph Which of the above is a simple graph ?4
Directed Graph Sometimes, we may want to specify a direction oneach edgeExample : Vertices may represent cities, and edgesmay represent roads (can be one-way) This gives the directed graph as follows :A directed graph G consists of a nonempty set Vof vertices and a set E of directed edges, whereeach edge is associated with an ordered pair ofvertices. We write G (V, E) to denote the graph.5
Examples12wxwx34yzyz6
Test Your Understanding Suppose we have a simple graph G with n verticesWhat is the maximum number of edges G cancontain, if(i) G is an undirected graph ?(ii) G is a directed graph ?7
Terminology (Undirected Graph) Let e be an edge that connects vertices u and vWe say (i) e is incident with u and v(ii) u and v are the endpoints of e ;(iii) u and v are adjacent (or neighbors)(iv) if u v, the edge e is called a loop The degree of a vertex v, denoted by deg(v), is thenumber of edges incident with v, except that aloop at v contributes twice to the degree of v8
Example What are the degrees and neighbors of eachvertex in the following graph ?acebdf9
Handshaking Theorem Let G (V, E) be an undirected graph with m edgesTheorem: deg(v) 2mv V Proof : Each edge e contributes exactly twice tothe sum on the left side (one to each endpoint).Corollary :An undirected graph has an evennumber of vertices of odd degree.10
Terminology (Directed Graph) Let e be an edge that connects vertices from u to vWe say (i) u initial vertex, v terminal vertex ;(ii) u is adjacent to v;(iii) v is adjacent from u;(iv) if u v, the edge e is called a loop The in-degree of a vertex v, denoted by deg–(v), isthe number of edges with v as terminal vertex The out-degree of a vertex u, denoted by deg (u),is the number of edges with u as initial vertex11
Example What are the in- and out-degrees of each vertexin the following graph ?acebdf12
Handshaking Theorem Let G (V, E) be directed graph with m edgesTheorem: deg–(v) deg (u)v Vu V m Proof : Each edge e contributes exactly once tothe in-degree and once to the out-degree13
Some Special Simple GraphsDefinition: A complete graph on n vertices,denoted by Kn, is a simple graph that containsone edge between each pair of distinct verticesExamples :K1K2K3K4K514
Some Special Simple GraphsDefinition: A cycle Cn, n 3, is a graph thatconsists of n vertices v1, v2, , vn and n edges{v1, v2}, {v2, v3}, , {vn – 1, vn}, {vn, v1}Examples :C3C4C5C615
Some Special Simple GraphsDefinition: A wheel Wn, n 3, is a graph thatconsists of a cycle Cn with an extra vertex thatconnects to each vertex in CnExamples :W3W4W5W616
Some Special Simple GraphsDefinition: An n-cube, denoted by Qn, is a graphthat consists of 2n vertices, each representing adistinct n-bit string. An edge exists between twovertices the corresponding strings differ inexactly one bit position.Examples :1010Q100Q211110 111010 01101100 101000 001Q3Q417
Some Special Simple GraphsDefinition: A bipartite graph is a graph such thatthe vertices can be partitioned into two sets V andW, so that each edge has exactly one endpointfrom V, and one endpoint from WExamples :bipartite graphsnon-bipartite graphs18
Some Special Simple Graphs Which of the following is a bipartite graph?aabbggccffeded19
Check if a Graph is Bipartite The following is a very useful theorem :Theorem: A simple graph is bipartite if and only ifit is possible to assign one of two different colorsto each vertex, so that no two adjacent verticesare assigned the same color Proof : If there is a way to color the vertices, thesame way shows a possible partition of vertices.Conversely, if there is a way to partition thevertices, the same way gives a possible coloring.20
Check if a Graph is Bipartite The above implies the following algorithm to checkif a connected graph is bipartite :Step 1 : Pick a vertex u. Color it with white ;Step 2 : While there are uncolored vertices(i) for each neighbor of a white vertex,color it with black ;(ii) for each neighbor of a black vertex,color it with white ;Step 3 : Report YES if each edge is colored properly.Else, report NO ;21
Some Special Simple GraphsDefinition: A complete bipartite graph Km,n is abipartite graph with vertices partitioned into twosubsets V and W of size m and n, respectively,such that there is an edge between each vertex inV and each vertex in WExamples :K2,2K3,2K3,322
Subgraphs and ComplementsIf G (V, E) is a graph, then G’ (V’, E’) is called asubgraph of G if V’ V and E’ E. Which one is a subgraph of the leftmost graph G ?ababababedededgcfed23
Subgraphs and ComplementsIf G (V, E) is a graph, then the subgraph of Ginduced by U V is a graph with the vertex set Uand contains exactly those edges from G withboth endpoints from UEx : Consider the graph on thegright sideWhat is its subgraph induced fby the vertex set { a, b, c, g } ?abced24
Subgraphs and ComplementsIf G (V, E) is a graph, then the complement of G,denoted by G, is a graph with the same vertex set,such thatan edge e exists in G e does not exist in GEx : Consider the graph on theright sideWhat is its complement ?abgcfed25
Graph IsomorphismGraphs G (V, E) and H (U, F) are isomorphic ifwe can set up a bijection f : V U such thatx and y are adjacent in G f(x) and f(y) are adjacent in HEx : The following are isomorphic to each other :26
Graph IsomorphismThe following graphs are isomorphic to each other.This graph is known as the Petersen graph :27
Graph IsomorphismHow to show the following are not isomorphic ?How to show the following are not isomorphic ?28
Discrete Mathematics Lecture 13 Graphs: Introduction 1 . Outline What is a Graph? Terminology Some Special Simple Graphs Subgraphs and Complements Graph Isomorphism 2 . What is a Graph ? A graph consists of a nonempty set V of vertices and a set E of edges, where each edge in E connects two (may be the same) vertices in V. Let G be a graph associated with a vertex set V and .File Size: 371KBPage Count: 28
