10.2 Graph Terminology and Special Types of Graphs

Basic Terminology • Definition 1 ○ Two vertices u, v in an undirected graph G are called adjacent (or neighbors) in G if there is an edge e between u and v. ○ Such an edge e is called incident with the vertices u and v and e is said to connect u and v • Definition 2 ○ The set of all a vertices v of G = (V, E), denoted by N(v), is called the neighborhood of v. ○ If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent to at least one vertex in A. So, ○ N(A)=⋃8_(v∈A)▒N(V) • Definition 3 ○ The degree of a vertex in a undirected graph is the number of edges incident with it, except that a loop at a vertex contributes two to the degree of that vertex. ○ The degree of the vertex v is denoted by deg(v). Degrees and Neighborhoods of Vertices What are the degrees and neighborhoods of the vertices in the graphs G and H? • For graph G ○ deg(a)=2,deg(b)=deg(c)=deg(f)=4,deg(d)=1,deg(e)=3,deg(g)=0. ○ N(a)={b,f},N(b)={a,c,e,f},N(c)={b,d,e,f},N(d)={c}, ○ N(e)={b,c,f},N(f)={a,b,c,e},N(g)=∅. • For graph H ○ deg(a)=4,deg(b)=deg(e)=6,deg(c)=1,deg(d)=5. ○ N(a)={b,d,e},N(b)={a,b,c,d,e},N(c)={b},N(d)={a,b,e},N(e)={a,b,d}. Degrees of Vertices • Theorem 1 (Handshaking Theorem) ○ If G=(V,E) is an undirected graph with m edges, then ○ 2m=∑_(v∈V)▒deg⁡v • Proof ○ Each edge contributes twice to the degree count of all vertices. ○ Hence, both the left-hand and right-hand sides of this equation equal twice the number of edges. ○ Think about the graph where vertices represent the people at a party and an edge connects two people who have shaken hands. • Example ○ How many edges are there in a graph with 10 vertices of degree six? • Solution ○ Because the sum of the degrees of the vertices is 6⋅10=60, the handshaking theorem tells us that 2m = 60. ○ So the number of edges m = 30. • Example ○ If a graph has 5 vertices, can each vertex have degree 3? • Solution ○ This is not possible by the handshaking theorem ○ Because the sum of the degrees of the vertices 3⋅5=15 is odd. • Theorem 2 ○ An undirected graph has an even number of vertices of odd degree. • Proof ○ Let V_1 be the vertices of even degree and V_2 be the vertices of odd degree in an undirected graph G=(V, E) with m edges.Then § 2m=∑_(v∈V)▒deg⁡v =∑_(v∈V_1)▒deg⁡v +∑_(v∈V_2)▒deg⁡v , where § ∑_(v∈V_1)▒deg⁡v must be even since deg⁡v is even for each v∈V_1 § ∑_(v∈V_2)▒deg⁡v must be even because 2m is even § and the sum of the degrees of the vertices of even degrees is also even. ○ Because this is the sum of the degrees of all vertices of odd degree in the graph, there must be an even number of such vertices Directed Graphs • Definition ○ An directed graph G = (V, E) consists of § V, a nonempty set of vertices (or nodes), and § E, a set of directed edges or arcs. ○ Each edge is an ordered pair of vertices. ○ The directed edge (u,v) is said to start at u and end at v. • Definition ○ Let (u,v) be an edge in G, then § u is the initial vertex of this edge and is adjacent to v and § v is the terminal (or end) vertex of this edge and is adjacent from u. ○ The initial and terminal vertices of a loop are the same. • Definition: ○ The in-degree of a vertex v, denoted deg^−⁡(v), is the number of edges which terminate at v. ○ The out-degree of v, denoted deg^+⁡(v), is the number of edges with v as their initial vertex. ○ Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of the vertex. • Example ○ In the graph G we have § deg^−⁡(a) = 2, deg^−⁡(b) = 2, deg^−⁡(c) = 3, deg^−⁡(d) = 2, deg^−⁡(e) = 3, deg^−⁡(f) = 0. § deg^+⁡(a) = 4, deg^+⁡(b) = 1, deg^+⁡(c) = 2, deg^+⁡(d) = 2, deg^+⁡(e) = 3, deg^+⁡(f) = 0. • Theorem 3 ○ Let G=(V, E) be a graph with directed edges. Then: § |E|=∑_(v∈V)▒〖deg^{−⁡(v)+deg}+⁡(v) 〗 • Proof ○ The first sum counts the number of outgoing edges over all vertices and the second sum counts the number of incoming edges over all vertices ○ It follows that both sums equal the number of edges in the graph. Special Types of Simple Graphs: Complete Graphs • A complete graph on n vertices, denoted by K_n, is the simple graph that contains exactly one edge between each pair of distinct vertices. Special Types of Simple Graphs: Cycles and Wheels • A cycle C_n for n ≥ 3 consists of ○ n vertices v_1,v_2,…,v_n, and ○ edges {v_1,v_2 },{v_2,v_3 },…,{v_(n−1),v_n },{v_n,v_1 } • A wheel W_n is obtained by ○ adding an additional vertex to a cycle C_n for n ≥ 3, and ○ connecting this new vertex to each of the n vertices in C_n by new edges. Special Types of Simple Graphs: n-Cubes • An n-dimensional hypercube, or n-cube, Q_n, is ○ a graph with 2n vertices representing all bit strings of length n, where ○ there is an edge between two vertices that differ in exactly one bit position. Bipartite Graphs • Definition ○ A simple graph G is bipartite if V can be partitioned into two disjoint subsets V_1 and V_2 such that every edge connects a vertex in V_1 and a vertex in V_2 ○ In other words, there are no edges which connect two vertices in V_1 or in V_2. • It is not hard to show that an equivalent definition of a bipartite graph is a graph where it is possible to color the vertices red or blue so that no two adjacent vertices are the same color. Bipartite Graphs and Matchings • Bipartite graphs are used to model applications that involve matching the elements of one set to elements in another, for example: • Job assignments - vertices represent the jobs and the employees, edges link employees with those jobs they have been trained to do. • A common goal is to match jobs to employees so that the most jobs are done. Bipartite Graphs (continued) • Example ○ Show that C_6 is bipartite. • Solution ○ We can partition the vertex set into V_1={v_1, v_3, v_5} and V_2={v_2, v_4, v_6} so that every edge of C_6 connects a vertex in V_1 and V_2. • Example ○ Show that C_2 is not bipartite. • Solution ○ If we divide the vertex set of C_3 into two nonempty sets, one of the two must contain two vertices ○ But in C_3 every vertex is connected to every other vertex ○ Therefore, the two vertices in the same partition are connected. ○ Hence, C_3 is not bipartite. Complete Bipartite Graphs • Definition ○ A complete bipartite graph K_(m,n) is a graph that has its vertex set partitioned into two subsets V_1 of size m and V_2 of size n such that there is an edge from every vertex in V_1 to every vertex in V_2. • Example ○ We display four complete bipartite graphs here. New Graphs from Old • Definition ○ A subgraph of a graph G = (V,E) is a graph (W,F), where W⊂V and F⊂E. ○ A subgraph H of G is a proper subgraph of G if H≠G. • Example ○ Here we show K_5 and one of its subgraphs. • Definition ○ 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 are in W. • Example ○ Here we show K_5 and the subgraph induced by W={a,b,c,e}. • Definition ○ The union of two simple graphs G_1=(V_1, E_1) and G_2=(V_2, E_2) is the simple graph with vertex set V_1∪V_2 and edge set E_1∩E_2 ○ The union of G_1 and G_2 is denoted by G_1∪G_2. • Example