Shawn Zhong

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Notes

Home / Notes / Page 13

11.1 Introduction to Trees

  • May 07, 2018
  • Shawn
  • Math 240
  • No comments yet
Trees • Definition ○ A tree is a connected undirected graph with no simple circuits. • Example ○ Which of these graphs are trees? • Solution ○ G_1 and G_2 are trees - both are connected and have no simple circuits ○ Because e, b, a, d, e is a simple circuit, G_3 is not a tree. ○ G_4 is not a tree because it is not connected. • Definition ○ A forest is a graph that has no simple circuit, but is not connected. ○ Each of the connected components in a forest is a tree. • Theorem ○ An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. • Proof ○ (⟹)Assume that T is a tree. § Then T is connected with no simple circuits. § Hence, if x and y are distinct vertices of T, there is a simple path between them (by Theorem 1 of Section 10.4). § This path must be unique - for if there were a second path, there would be a simple circuit in T (by Exercise 59 of Section 10.4). § Hence, there is a unique simple path between any two vertices of a tree. ○ (⟸)Now assume that there is a unique simple path between any two vertices of a graph T. § Then T is connected because there is a path between any two of its vertices. § Furthermore, T can have no simple circuits since if there were a simple circuit, there would be two paths between some two vertices. ○ Hence, a graph with a unique simple path between any two vertices is a tree. Rooted Trees • Definition ○ A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root. • An unrooted tree is converted into different rooted trees when different vertices are chosen as the root. Rooted Tree Terminology • Terminology for rooted trees is a mix from botany and genealogy (such as this family tree of the Bernoulli family of mathematicians). • If v is a vertex of a rooted tree other than the root, the parent of v is the unique vertex u such that there is a directed edge from u to v. • When u is a parent of v, v is called a child of u. • Vertices with the same parent are called siblings. • The ancestors of a vertex are the vertices in the path from the root to this vertex, excluding the vertex itself and including the root. • The descendants of a vertex v are those vertices that have v as an ancestor. • A vertex of a rooted tree with no children is called a leaf. • Vertices that have children are called internal vertices. • If a is a vertex in a tree, the subtree with a as its root is the subgraph of the tree consisting of a and its descendants and all edges incident to these descendants. Examples of Rooted Trees • Example: In the rooted tree T (with root a): ○ Find the parent of c, the children of g, the siblings of h, the ancestors of e, and the descendants of b. ○ Find all internal vertices and all leaves. ○ What is the subtree rooted at G? • Solution: ○ The parent of c is b. The children of g are h, i, and j. The siblings of h are i and j. The ancestors of e are c, b, and a. The descendants of b are c, d, and e. ○ The internal vertices are a, b, c, g, h, and j. The leaves are d, e, f, i, k, l, and m. ○ We display the subtree rooted at g. Properties of Trees • Theorem 2 ○ A tree with n vertices has n − 1 edges. • Proof (by mathematical induction): ○ Basis Step § When n = 1, a tree with one vertex has no edges. § Hence, the theorem holds when n = 1. ○ Inductive Step § Assume that every tree with k vertices has k − 1 edges. § Suppose that a tree T has k + 1 vertices and that v is a leaf of T. § Let w be the parent of v. § Removing the vertex v and the edge connecting w to v produces a tree T′ with k vertices. § By the inductive hypothesis, T′ has k − 1 edges. § Because T has one more edge than T′, we see that T has k edges. § This completes the inductive step. m-ary Rooted Trees • Definition ○ A rooted tree is called an m-ary tree if every internal vertex has no more than m children. ○ The tree is called a full m-ary tree if every internal vertex has exactly m children. ○ An m-ary tree with m = 2 is called a binary tree. • Example ○ Are the following rooted trees full m-ary trees for some positive integer m? • Solution ○ T_1 is a full binary tree because each of its internal vertices has two children. ○ T_2 is a full 3-ary tree because each of its internal vertices has three children. ○ In T_3 each internal vertex has five children, so T3 is a full 5-ary tree. ○ T_4 is not a full m-ary tree for any m because some of its internal vertices have two children and others have three children. Counting Vertices in Full m-Ary Trees • Theorem 3 ○ A full m-ary tree with i internal vertices has n = mi + 1 vertices. • Proof ○ Every vertex, except the root, is the child of an internal vertex. ○ Because each of the i internal vertices has m children, ○ there are mi vertices in the tree other than the root. ○ Hence, the tree contains n = mi + 1 vertices. • Theorem 4 ○ A full m-ary tree with § n vertices has i=(n−1)/m internal vertices and l=((m−1)n+1)/m leaves, § i internal vertices has n = mi + 1 vertices and l=(m−1)i+1 leaves, § l leaves has n=(ml−1)/(m−1) vertices and i=(l−1)/(m−1) internal vertices. ○ Proof (of part i) § Solving for i in n = mi + 1 (from Theorem 3) gives i=(n−1)/m. § Since each vertex is either a leaf or an internal vertex, n=l+i. § By solving for l and using the formula for i, we see that § l=n−i=n−(n−1)/m=((m−1)n+1)/m Level of vertices and height of trees • When working with trees, we often want to have rooted trees where the subtrees at each vertex contain paths of approximately the same length. • To make this idea precise we need some definitions: ○ The level of a vertex v in a rooted tree is the length of the unique path from the root to this vertex. ○ The height of a rooted tree is the maximum of the levels of the vertices. • Example: ○ Find the level of each vertex in the tree to the right. ○ What is the height of the tree? • Solution: ○ The root a is at level 0. ○ Vertices b, j, and k are at level 1. ○ Vertices c, e, f, and l are at level 2. ○ Vertices d, g, i, m, and n are at level 3. ○ Vertex h is at level 4. ○ The height is 4, since 4 is the largest level of any vertex. Balanced m-Ary Trees • Definition ○ A rooted m-ary tree of height h is balanced if all leaves are at levels h or h − 1. • Example ○ Which of the rooted trees shown below is balanced? • Solution ○ T_1 and T_3 are balanced, but T_2 is not because it has leaves at levels 2, 3, and 4. The Bound for the Number of Leaves in an m-Ary Tree • Theorem 5 ○ There are at most mh leaves in an m-ary tree of height h. • Proof (by mathematical induction on height): ○ Basis Step § Consider an m-ary trees of height 1. § The tree consists of a root and no more than m children, all leaves. § Hence, there are no more than m^1=m leaves in an m-ary tree of height 1. ○ Inductive Step § Assume the result is true for all m-ary trees of height h. § Let T be an m-ary tree of height h. § The leaves of T are the leaves of the subtrees of T we get when we delete the edges from the root to each of the vertices of level 1. § Each of these subtrees has height ≤ h−1. § By the inductive hypothesis, each of these subtrees has at most mh− 1 leaves. § Since there are at most m such subtrees, there are at most m⋅m^(h1) = mh leaves in the tree. • Corollary 1 ○ If an m-ary tree of height h has l leaves, then h ≥ ⌈log_m⁡l⌉. ○ If the m-ary tree is full and balanced, then h = ⌈log_m⁡l⌉. (see text for the proof)
Read More >>

10.4 Connectivity

  • May 07, 2018
  • Shawn
  • Math 240
  • 1 comment
Paths • Informal Definition ○ A path is a sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph. ○ As the path travels along its edges, it visits the vertices along this path, that is, the endpoints of these. • Applications ○ Numerous problems can be modeled with paths formed by traveling along edges of graphs such as ○ determining whether a message can be sent between two computers. ○ efficiently planning routes for mail delivery. • Definition ○ Let n be a nonnegative integer and G an undirected graph ○ A path of length n from u to v in G is a sequence of n edges e_1,…,e_n of G for which § there exists a sequence x_0=u,x_1,…,x_(n−1),x_n=v of vertices such that § e_i has, for i=1,…,n, the endpoints x_(i−1) and x_i. ○ When the graph is simple, we denote this path by its vertex sequence § x_0,x_1,…,x_n (since listing the vertices uniquely determines the path). ○ The path is a circuit if it begins and ends at the same vertex and has length greater than zero. ○ The path or circuit is said to pass through the vertices x_1,x_2,…,x_(n−1) and traverse the edges e_1,…,e_n. ○ A path or circuit is simple if it does not contain the same edge more than once. • Example ○ In the simple graph here: ○ a, d, c, f, e is a simple path of length 4. ○ d, e, c, a is not a path because e is not connected to c. ○ b, c, f, e, b is a circuit of length 4. ○ a, b, e, d, a, b is a path of length 5, but it is not a simple path. Degrees of Separation • Paths in Acquaintanceship Graphs ○ In an acquaintanceship graph there is a path between two people if there is a chain of people linking these people, where two people adjacent in the chain know one another. ○ In this graph there is a chain of six people linking Kamini and Ching. • Note: ○ Some have speculated that almost every pair of people in the world are linked by a small chain of no more than six, or maybe even, five people. ○ The play Six Degrees of Separation by John Guare is based on this notion. Connectedness in Undirected Graphs • Definition ○ An undirected graph is called connected if there is a path between every pair of vertices. ○ An undirected graph that is not connected is called disconnected. ○ We say that we disconnect a graph when we remove vertices or edges, or both, to produce a disconnected subgraph. • Example ○ G_1 is connected because there is a path between any pair of its vertices, as can be easily seen. ○ However G_2 is not connected because there is no path between vertices a and f, for example. • Theorem ○ Every pair of distinct vertices in a connect graph is connected by a simple path • Proof ○ Let u and v be two distinct vertices of the connected undirected graph G=(V,E) ○ Because G is connected, there is at least one path between u and v ○ Let x_0,x_1,…,x_n, where x_0=u and x_n=v, be the vertex sequence of a path of least length. ○ This path of least length is simple. ○ To see this, suppose is not simple, then x_i=x_j for some i and j with 0≤i j ○ This means that there is a path from u to v of shorter length with vertex sequence § x_0,x_1,…,x_(i−1),x_j,…,x_n ○ Obtained by deleting the edges corresponding to the vertex sequence x_i,…,x_(j−1) Connected Components Definition 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 graph G that is not connected has two or more connected components that are disjoint and have G as their union. Example The graph H is the union of three disjoint subgraphs H_1, H_2, and H_3, none of which are proper subgraphs of a larger connected subgraph of G These three subgraphs are the connected components of H. Connectedness in Directed Graphs • Definition ○ A directed graph is strongly connected if there is a path from a to b and a path from b to a whenever a and b are vertices in the graph. • Definition ○ A directed graph is weakly connected if there is a path between every two vertices in the underlying undirected graph, which is the undirected graph obtained by ignoring the directions of the edges of the directed graph. Counting Paths between Vertices • We can use the adjacency matrix of a graph to find the number of paths between two vertices in the graph. • Theorem ○ Let G be a graph with adjacency matrix A with respect to the ordering v_1,…,v_n of vertices ○ (with directed or undirected edges, multiple edges and loops allowed). ○ The number of different paths of length r from v_i to v_j, where r 0 is a positive integer, equals the (i,j)th entry of A^r. • Proof by mathematical induction: ○ Basis Step § By definition of the adjacency matrix, the number of paths from v_i to v_j of length 1 is the (i,j)th entry of A. ○ Inductive Step § For the inductive hypothesis, we assume that that the (i,j)th entry of A^r is the number of different paths of length r from v_i to v_j. § Because A^(r+1)=A^r A, the (i,j)th entry of A^(r+1) equals b_i1 a_1j+b_i2 a_2j+…+b_in a_nj, where b_ik is the (i,k)th entry of A^r. § By the inductive hypothesis, b_ik is the number of paths of length r from v_i to v_k. § A path of length r + 1 from v_i to v_j is made up of a path of length r from v_i to some v_k, and an edge from v_k to v_j. § By the product rule for counting, the number of such paths is the product of the number of paths of length r from v_i to v_k (i.e., b_ik ) and the number of edges from from v_k to v_j (i.e, akj). § The sum over all possible intermediate vertices v_k is b_i1 a_1j+b_i2 a_2j+…+b_in a_nj.
Read More >>

10.3 Representing Graphs and Graph Isomorphism

  • May 07, 2018
  • Shawn
  • Math 240
  • No comments yet
Representing Graphs: Adjacency Lists • Definition ○ An adjacency list can be used to represent a graph with no multiple edges by specifying the vertices that are adjacent to each vertex of the graph. • Example 1 • Example 2 Representation of Graphs: Adjacency Matrices • Definition ○ Suppose that G=(V,E) is a simple graph where |V|=n. ○ Arbitrarily list the vertices of G as v_1,v_2,…,v_n. ○ The adjacency matrix A_G of G, with respect to the listing of vertices, is the n×n zero-one matrix with 1 as its (i, j)th entry when v_i and v_j are adjacent, and 0 as its (i, j)th entry when they are not adjacent. ○ In other words, if the graphs adjacency matrix is A_G=[a_ij ], then ○ a_ij={■8(1&if {v_i,v_j } is an edge of G@0&otherwise)┤ • Example 1 ○ The ordering of vertices is a, b, c, d. • Example 2 ○ The ordering of vertices is a, b, c, d. • Note ○ The adjacency matrix of a simple graph is symmetric, i.e., a_ij=a_ji ○ Also, since there are no loops, each diagonal entry a_ii for i = 1, 2, 3, …, n, is 0. • Note ○ When a graph is sparse, that is, it has few edges relatively to the total number of possible edges, it is much more efficient to represent the graph using an adjacency list than an adjacency matrix. ○ But for a dense graph, which includes a high percentage of possible edges, an adjacency matrix is preferable. Adjacency Matrices: Graphs with Loops and Multiple Edges • Adjacency matrices can also be used to represent graphs with loops and multiple edges. • A loop at the vertex v_i is represented by a 1 at the (i, j)th position of the matrix. • When multiple edges connect the same pair of vertices v_i and v_j, (or if multiple loops are present at the same vertex), the (i, j)th entry equals the number of edges connecting the pair of vertices. • Example ○ We give the adjacency matrix of the pseudograph shown here using the ordering of vertices a, b, c, d. Adjacency Matrices: Directed graphs • Adjacency matrices can also be used to represent directed graphs. • The matrix for a directed graph G=(V, E) has a 1 in its (i, j)th position if there is an edge from v_i to v_j, where v_1,v_2,…,v_n is a list of the vertices. • In other words, if the graphs adjacency matrix is A_G=[a_ij ], then ○ a_ij={■8(1&if (v_i,v_j ) is an edge of G@0&otherwise)┤ • The adjacency matrix for a directed graph does not have to be symmetric, because there may not be an edge from v_i to v_j, when there is an edge from v_j to v_i. • To represent directed multigraphs, the value of a_ij is the number of edges connecting v_i to v_j. Representation of Graphs: Incidence Matrices • Definition ○ Let G=(V, E) be an undirected graph with vertices v_1,v_2,…,v_n and edges e_1,e_2,…,e_m. ○ The incidence matrix with respect to the ordering of V and E is the n×m matrix ○ M=[m_ij ],where m_ij={■8(1&when edge e_j is incident with v_i@0&otherwise)┤ • Example ○ Simple Graph and Incidence Matrix ○ ○ The rows going from top to bottom represent v_1 through v_5 ○ The columns going from left to right represent e_1 through e_6. • Example ○ The rows going from top to bottom represent v_1 through v_5 ○ The columns going from left to right represent e_1 through e_8. Isomorphism of Graphs • Definition ○ The simple graphs G_1 = (V_1, E_1) and G_2 = (V_2, E_2) are isomorphic if § there is a one-to-one and onto function f from V_1 to V_2 with the property that § a and b are adjacent in G_1 if and only if f(a) and f(b) are adjacent in G_2, for all a and b in V_1. ○ Such a function f is called an isomorphism. ○ Two simple graphs that are not isomorphic are called nonisomorphic. • Example ○ Show that the graphs G=(V, E) and H=(W, F) are isomorphic. • Solution ○ The function f with f(u_1) = v_1, f(u_2)=v_4, f(u_3) = v_3, and f(u_4) = v_2 is a one-to-one correspondence between V and W. ○ Note that adjacent vertices in G are u_1 and u_2, u_1 and u_3, u_2 and u_4, and u_3 and u_4. ○ Each of the pairs f(u_1) = v_1 and f(u_2) = v_4, f(u_1)=v_1 and f(u_3)=v_3 , f(u_2)=v_4 f(u_4)=v_2, f(u_3) = v_3 and f(u_4) = v_2 consists of two adjacent vertices in H • Note ○ It is difficult to determine whether two simple graphs are isomorphic using brute force because there are n! possible one-to-one correspondences between the vertex sets of two simple graphs with n vertices. ○ The best algorithms for determining whether two graphs are isomorphic have exponential worst case complexity in terms of the number of vertices of the graphs. ○ Sometimes it is not hard to show that two graphs are not isomorphic. ○ We can do so by finding a property, preserved by isomorphism, that only one of the two graphs has. ○ Such a property is called graph invariant. ○ There are many different useful graph invariants that can be used to distinguish nonisomorphic graphs, such as the number of vertices, number of edges, and degree sequence (list of the degrees of the vertices in nonincreasing order). ○ We will encounter others in later sections of this chapter. • Example ○ Determine whether these two graphs are isomorphic • Solution ○ Both graphs have eight vertices and ten edges. ○ They also both have four vertices of degree two and four of degree three. ○ However, G and H are not isomorphic. ○ Note that since deg(a) = 2 in G, a must correspond to t, u, x, or y in H, ○ because these are the vertices of degree 2. ○ But each of these vertices is adjacent to another vertex of degree two in H ○ which is not true for a in G. ○ Alternatively, note that the subgraphs of G and H made up of vertices of ○ degree three and the edges connecting them must be isomorphic. ○ But the subgraphs, as shown at the right, are not isomorphic. • Example ○ Determine whether these two graphs are isomorphic. • Solution ○ Both graphs have six vertices and seven edges. ○ They also both have four vertices of degree two and two of degree three. ○ The subgraphs of G and H consisting of all the vertices of degree two and the edges connecting them are isomorphic ○ So, it is reasonable to try to find an isomorphism f. ○ We define an injection f from the vertices of G to the vertices of H that preserves the degree of vertices. ○ We will determine whether it is an isomorphism. ○ The function f with f(u_1)=v_6,f(u_2)=v_3,f(u_3)=v_4,f(u_4)=v_5,f(u_5)=v_1,f(u_6)=v_2 is a one-to-one correspondence between G and H ○ Showing that this correspondence preserves edges is straightforward, so we will omit the details here. ○ Because f is an isomorphism, it follows that G and H are isomorphic graphs. ○ See the text for an illustration of how adjacency matrices can be used for this verification.
Read More >>

10.2 Graph Terminology and Special Types of Graphs

  • May 07, 2018
  • Shawn
  • Math 240
  • 2 comments
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
Read More >>

10.1 Graphs and Graph Models

  • May 07, 2018
  • Shawn
  • Math 240
  • No comments yet
Graphs • Definition ○ A graph G = (V, E) consists of § a nonempty set V of vertices (or nodes) § and a set E of edges. ○ Each edge has either one or two vertices associated with it, called its endpoints. ○ An edge is said to connect its endpoints. • Example ○ This is a graph with four vertices and five edges. • Remarks ○ The graphs we study here are unrelated to graphs of functions studied in Chapter 2. ○ We have a lot of freedom when we draw a picture of a graph. ○ All that matters is the connections made by the edges, not the particular geometry depicted. ○ For example, the lengths of edges, whether edges cross, how vertices are depicted, and so on, do not matter ○ A graph with an infinite vertex set is called an infinite graph. ○ A graph with a finite vertex set is called a finite graph. We (following the text) restrict our attention to finite graphs. Graph Terminology • In a simple graph each edge connects two different vertices and no two edges connect the same pair of vertices. • Multigraphs may have multiple edges connecting the same two vertices. • When m different edges connect the vertices u and v, we say that {u,v} is an edge of multiplicity m. • An edge that connects a vertex to itself is called a loop. • A pseudograph may include loops, as well as multiple edges connecting the same pair of vertices. • Example ○ This pseudograph has both multiple edges and a loop. Directed Graphs • Definition: ○ An directed graph (or digraph) G = (V, E) consists of § a nonempty set V of vertices (or nodes) § and a set E of directed edges (or arcs). ○ Each edge is associated with an ordered pair of vertices. ○ The directed edge associated with the ordered pair (u,v) is said to start at u and end at v. • Remark: ○ Graphs where the end points of an edge are not ordered are said to be undirected graphs. Some Terminology (continued) • Definition ○ A simple directed graph has no loops and no multiple edges. • Example ○ This is a directed graph with three vertices and four edges. • Definition ○ A directed multigraph may have multiple directed edges. ○ When there are m directed edges from the vertex u to the vertex v, ○ We say that (u,v) is an edge of multiplicity m. • Example ○ In this directed multigraph the multiplicity of (a,b) is 1 and the multiplicity of (b,c) is 2. Graph Models: Computer Networks • When we build a graph model, we use the appropriate type of graph to capture the important features of the application. • We illustrate this process using graph models of different types of computer networks. • In all these graph models, the vertices represent data centers and the edges represent communication links. • To model a computer network where we are only concerned whether two data centers are connected by a communications link, we use a simple graph. • This is the appropriate type of graph when we only care whether two data centers are directly linked (and not how many links there may be) and all communications links work in both directions. • To model a computer network where we care about the number of links between data centers, we use a multigraph. • To model a computer network with diagnostic links at data centers, we use a pseudograph, as loops are needed. • To model a network with multiple one-way links, we use a directed multigraph. • Note that we could use a directed graph without multiple edges if we only care whether there is at least one link from a data center to another data center. Graph Terminology: Summary • To understand the structure of a graph and to build a graph model, we ask these questions: ○ Are the edges of the graph undirected or directed (or both)? ○ If the edges are undirected, are multiple edges present that connect the same pair of vertices? ○ If the edges are directed, are multiple directed edges present? ○ Are loops present? Other Applications of Graphs • We will illustrate how graph theory can be used in models of: ○ Social networks ○ Communications networks ○ Information networks ○ Software design ○ Transportation networks ○ Biological networks • It’s a challenge to find a subject to which graph theory has not yet been applied. • Can you find an area without applications of graph theory? Examples of Collaboration Graphs • The Hollywood graph models the collaboration of actors in films. ○ We represent actors by vertices and we connect two vertices if the actors they represent have appeared in the same movie. ○ We will study the Hollywood Graph in Section 10.4 when we discuss Kevin Bacon numbers. • An academic collaboration graph models the collaboration of researchers who have jointly written a paper in a particular subject. ○ We represent researchers in a particular academic discipline using vertices. ○ We connect the vertices representing two researchers in this discipline if they are coauthors of a paper. ○ We will study the academic collaboration graph for mathematicians when we discuss Erdős numbers in Section 10.4. Transportation Graphs • Graph models are extensively used in the study of transportation networks. • Airline networks can be modeled using directed multigraphs where ○ airports are represented by vertices ○ each flight is represented by a directed edge from the vertex representing the departure airport to the vertex representing the destination airport • Road networks can be modeled using graphs where ○ vertices represent intersections and edges represent roads. ○ undirected edges represent two-way roads and directed edges represent one-way roads. Biological Applications • Graph models are used extensively in many areas of the biological science. • We will describe two such models, one to ecology and the other to molecular biology. • Niche overlap graphs model competition between species in an ecosystem • Vertices represent species and an edge connects two vertices when they represent species who compete for food resources. • Example: This is the niche overlap graph for a forest ecosystem with nine species. • We can model the interaction of proteins in a cell using a protein interaction network. • In a protein interaction graph, vertices represent proteins and vertices are connected by an edge if the proteins they represent interact. • Protein interaction graphs can be huge and can contain more than 100,000 vertices, each representing a different protein, and more than 1,000,000 edges, each representing an interaction between proteins • Protein interaction graphs are often split into smaller graphs, called modules, which represent the interactions between proteins involved in a particular function. • Example: This is a module of the protein interaction graph of proteins that degrade RNA in a human cell.
Read More >>
  • 1
  • …
  • 11
  • 12
  • 13
  • 14
  • 15
  • …
  • 84

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 – Discrete Math
    • Math 375 – Linear Algebra
    • Math 431 – Intro to Probability
    • Math 514 – Numerical Analysis
    • Math 521 – Analysis I
    • Math 541 – Abstract Algebra
    • Math 632 – Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 – Intro to Computer Engr.
    • CS/ECE 352 – Digital System Fund.
    • Learn Haskell
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E＆M
    • AP Physics C: Mechanics
    • CLEP Psychology
  • 2048 Game
  • HiMCM 2016
  • 登峰杯 MCM

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E＆M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (2)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP