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₁, ..., V, of vertices (with directed or undirected edges, multiple edges and loops allowed). The number of different paths of length r from v; where r >0 is a positive integer, equals the (i,j)th entry of A". to Vi, Proof by mathematical induction: Basis Step: By definition of the adjacency matrix, the number of paths from v; to v, 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' is the number of different paths of length r from v; to vj. Because A+1=AA, the (i,j)th entry of Ar+1 equals bija₁; +b2a2; ++ binani where bik is the (i,k)th entry of A'. By the inductive hypothesis, bk is the number of paths of length r from v; to Vk. A path of length + 1 from v; to v; is made up of a path of length r from v; to some vk, and an edge from V to vj. By the product rule for counting, the number of such paths is the product of the number of paths of length r from v; to vk (i.e., bik) and the number of edges from from v to v, (i.e, ak). The sum over all possible intermediate vertices vk is ba₁; + biza2; +.... + binani
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₁, ..., V, of vertices (with directed or undirected edges, multiple edges and loops allowed). The number of different paths of length r from v; where r >0 is a positive integer, equals the (i,j)th entry of A". to Vi, Proof by mathematical induction: Basis Step: By definition of the adjacency matrix, the number of paths from v; to v, 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' is the number of different paths of length r from v; to vj. Because A+1=AA, the (i,j)th entry of Ar+1 equals bija₁; +b2a2; ++ binani where bik is the (i,k)th entry of A'. By the inductive hypothesis, bk is the number of paths of length r from v; to Vk. A path of length + 1 from v; to v; is made up of a path of length r from v; to some vk, and an edge from V to vj. By the product rule for counting, the number of such paths is the product of the number of paths of length r from v; to vk (i.e., bik) and the number of edges from from v to v, (i.e, ak). The sum over all possible intermediate vertices vk is ba₁; + biza2; +.... + binani
Operations Research : Applications and Algorithms
4th Edition
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Wayne L. Winston
Chapter2: Basic Linear Algebra
Section: Chapter Questions
Problem 15RP
Related questions
Question
My professor went over the proof on this slide and I don't really understand it. Can you explain it in detail step by step?
Transcribed Image Text: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₁, ..., V, of vertices (with directed or undirected edges, multiple
edges and loops allowed). The number of different paths of length r from v;
where r >0 is a positive integer, equals the (i,j)th entry of A".
to Vi,
Proof by mathematical induction:
Basis Step: By definition of the adjacency matrix, the number of paths from v; to v, 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' is the number of
different paths of length r from v; to vj.
Because A+1=AA, the (i,j)th entry of Ar+1 equals bija₁; +b2a2; ++ binani where bik is the (i,k)th
entry of A'. By the inductive hypothesis, bk is the number of paths of length r from v; to Vk.
A path of length + 1 from v; to v; is made up of a path of length r from v; to some vk, and an edge from
V to vj. By the product rule for counting, the number of such paths is the product of the number of
paths of length r from v; to vk (i.e., bik) and the number of edges from from v to v, (i.e, ak). The sum
over all possible intermediate vertices vk is ba₁; + biza2; +....
+ binani
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
C++ for Engineers and Scientists
Computer Science
ISBN:
9781133187844
Author:
Bronson, Gary J.
Publisher:
Course Technology Ptr
Fundamentals of Information Systems
Computer Science
ISBN:
9781305082168
Author:
Ralph Stair, George Reynolds
Publisher:
Cengage Learning
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
C++ for Engineers and Scientists
Computer Science
ISBN:
9781133187844
Author:
Bronson, Gary J.
Publisher:
Course Technology Ptr
Fundamentals of Information Systems
Computer Science
ISBN:
9781305082168
Author:
Ralph Stair, George Reynolds
Publisher:
Cengage Learning
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning