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)=Ar 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.
