Graphs Notes PDF

Horus University in Egypt (HUE) Faculty of Artificial Intelligence and Information CS 104 Discrete Structure Level 1 Ch10 Graphs  Text Book: Kenneth H. Rosen, “Discrete mathematics and its applications”, 8th_ed (2019)  Ch10 Graph...

Horus University in Egypt (HUE) Faculty of Artificial Intelligence and Information CS 104 Discrete Structure Level 1 Ch10 Graphs  Text Book: Kenneth H. Rosen, “Discrete mathematics and its applications”, 8th_ed (2019)  Ch10 Graphs Topics 2.Graph Terminology and Special Types of Graphs  10.2 Graph Terminology and Special Types of Graphs Basic Terminology: Definition 1: Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G if u and v are endpoints of an edge e of G. Such an edge e is called incident with the vertices u and v and e is said to connect u and v. edge(u,v) u v  10.2 Graph Terminology and Special Types of Graphs Basic Terminology: Definition 2: The set of all neighbors of a vertex 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) = ⋃v∈A N(v). 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) = ∅.  10.2 Graph Terminology and Special Types of Graphs Basic Terminology: Definition 3: The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by deg(v). deg(a) = 2 deg(b) = 4 deg(c) = 4 deg(d) = 1 deg(e) = 3 deg(f ) = 4 deg(g) = 0.  10.2 Graph Terminology and Special Types of Graphs Basic Terminology: Isolated: A vertex of degree zero is called isolated. It follows that an isolated vertex is not adjacent to any vertex Vertex g is isolated deg(a) = 2 deg(b) = 4 deg(c) = 4 deg(d) = 1 deg(e) = 3 deg(f ) = 4 deg(g) = 0.  10.2 Graph Terminology and Special Types of Graphs Basic Terminology: Pendant: A vertex is pendant if and only if it has degree one. Vertex d is pendant deg(a) = 2 deg(b) = 4 deg(c) = 4 deg(d) = 1 deg(e) = 3 deg(f ) = 4 deg(g) = 0. Example 1: What are the degrees and what are the neighborhoods of the vertices in the graphs ? N(a) = {b, d, e} N(b) = {a, b, c, d, e} N(c) = {b} N(d) = {a, b, e} deg(a) = 4 N(e) = {a, b, d} deg(b) = 6 deg(c) = 1 deg(d) = 5 deg(e) = 6 Vertex c is pendant Example 2: How many vertices and edges in the following graphs ? What are the degrees and what are the neighborhoods of the vertices in the graphs ? Number of vertices = 5 Number of edges = 13 deg(a) = 6 deg(b) = 6 deg(c) = 6 deg(d) = 5 N(a) = {a,b,e} deg(e) = 3 N(b) = {a,c, d, e} N(c) = {b,c,d} N(d) = {b,c,e} N(e) = {a, b, d} The Handshaking Theorem: Let G = (V, E) be an undirected graph with m edges. Then Edge having two endpoints and a handshake involving two hands Example 3: How many edges are there in a graph with 10 vertices each of degree six? Solution: Because the sum of the degrees of the vertices is 6 x 10 = 60, it follows that 2m = 60 where m is the number of edges. Therefore, m = 30. Definition 4: When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v is said to be adjacent from u. The vertex u is called the initial vertex of (u, v), and v is called the terminal or end vertex of (u, v). The initial vertex and terminal vertex of a loop are the same. edge(u,v) u v Definition 5: In a graph with directed edges the in-degree of a vertex v, denoted by deg−(v), is the number of edges with v as their terminal vertex. The out-degree of v, denoted by 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 this vertex.). Example : Find the in-degree and out-degree of each vertex in the graph G with directed edges shown in the following Figure? Number of vertices = 6 Number of edges = 12 deg−(a) = 2 deg+(a) = 4 deg−(b) = 2 deg+(b) = 1 deg−(c) = 3 deg+(c) = 2 deg−(d) = 2 deg+(d) = 2 deg−(e) = 3 deg+(e) = 3 deg−(f) = 0 deg+(f) = 0 Theorem : Let G = (V, E) be a graph with directed edges. Then  Some Special Simple Graphs Complete Graphs: The complete graph on n vertices, denoted by kn is a simple graph that contains exactly one edge between each pair of distinct vertices. (sample graph → no loop , no multi edges) The graphs kn for n = 1, 2, 3, 4, 5, 6, are.  Some Special Simple Graphs Cycles: The cycle Cn , n ≥ 3, consists of n vertices v1 , v2 , … , vn and edges {v1 , v2}, {v2 , v3}, … ,{vn-1 , vn}, and {vn , v1}. The cycles C3 , C4 , C5 , and C6 are  Some Special Simple Graphs Wheels: We obtain a wheel Wn when we add an additional vertex to a cycle Cn, for n ≥ 3, and connect this new vertex to each of the n vertices in Cn, by new edges. The wheels W3 , W4 , W5 ,and W6 are  Some Special Simple Graphs n-Cubes : The n-dimensional hypercube, or n-cube, denoted by Qn, is a graph that has vertices representing the 2n bit strings of length n. Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position. The graphs Q1 , Q2 , and Q3 are  Some Special Simple Graphs Definition 6: 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. Example : Determine whether the graph is bipartite or not ? Determining whether it is possible to assign either red or blue to each vertex so that no two adjacent vertices are assigned the same color. Example 1: Answer Determine whether the graph is bipartite or not? 𝑒 𝑒 𝑓 𝑑 𝑎 𝑎 𝑎 𝑑 𝑎 𝑑 𝑐 𝑏 𝑐 𝑏 𝑐 𝑏 𝑐 𝑏 𝑏𝑖𝑝𝑎𝑟𝑡𝑖𝑡𝑒 𝑏𝑖𝑝𝑎𝑟𝑡𝑖𝑡𝑒 𝑉1 = 𝑎, 𝑐 𝑉1 = 𝑎, 𝑐, 𝑒 𝑉2 = 𝑏, 𝑑 𝑉2 = 𝑏, 𝑑, 𝑓 every edge of 𝐶4 connects a every edge of 𝐶6 connects a vertex in 𝑉1and a vertex in 𝑉2. vertex in 𝑉1and a vertex in 𝑉2. ©Ahmed Hagag BS102 Discrete Mathematics 24 Example 1: Answer Determine whether the graph is bipartite or not? 𝑒 𝑒 𝑓 𝑎 𝑎 𝑑 𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑐 𝑏 𝑏𝑖𝑝𝑎𝑟𝑡𝑖𝑡𝑒 𝑉1 = 𝑎, 𝑐, 𝑒 𝑉2 = 𝑏, 𝑑, 𝑓 every edge of 𝐶6 connects a vertex in 𝑉1and a vertex in 𝑉2. ©Ahmed Hagag BS102 Discrete Mathematics 25 Example 2: Determine whether the graph is bipartite or not? ©Ahmed Hagag BS102 Discrete Mathematics 26 Example 2: Answer Determine whether the graph is bipartite or not? ©Ahmed Hagag BS102 Discrete Mathematics 27 Example 2: Answer Determine whether the graph is bipartite or not? 𝑵𝒐𝒕 𝒃𝒊𝒑𝒂𝒓𝒕𝒊𝒕𝒆 ©Ahmed Hagag BS102 Discrete Mathematics 28  Bipartite Graphs A simple graph is bipartite if V can be partitioned into V = Z1 W2 so that There is no edge from zi to zj There is no edge from wi to wj There is an edge rom vk to wh The total degree o any graph is even  Bipartite Graph A bipartite graph V1 V2 is an undirected u1 graph G = (V,E) in which V v1 can be partitioned u2 into 2 sets V1 and V2 v2 such that ( u,v)  E u3 implies either v3 u  V1 and v  V2 u4 OR v  V1 and u  V2. An example of bipartite graph application to telecommunication problems can be found in, C.A. Pomalaza-Ráez, “A Note on Efficient SS/TDMA Assignment Algorithms,” IEEE Transactions on Communications, September 1988, pp. 1078-1082. For another example of bipartite graph applications see the slides in the Addendum section 11/7/2024  Bipartite Graphs EG: C4 is a bichromatic: And so is bipartite, if we redraw it:  Bipartite Graphs EG: C4 is a bichromatic: And so is bipartite, if we redraw it:  Bipartite Graphs EG: C4 is a bichromatic: And so is bipartite, if we redraw it:  Bipartite Graphs EG: C4 is a bichromatic: And so is bipartite, if we redraw it:  Bipartite Graphs EG: C4 is a bichromatic: And so is bipartite, if we redraw it:  Bipartite Graphs EG: C4 is a bichromatic: And so is bipartite, if we redraw it: Q: For which n is Cn bipartite? Thank You 38