graph consists of vertices and edges that join two vertices. Graphs are used to model communications networks. One way to represent a graph on n vertices is to use an n x n matrix, called the adjacency matrix of the graph. Definition: The adjacency matrix of a graph is a matrix A with its rows and columns indexed by the vertices of the graph where { 1 if vertex j is adjacent to vertex k, otherwise. Here is a graph G with five vertices and six edges and its adjacency matrix A. Graph G 3 A = 1 2 1 1 3 1 0 1 0 0 1 0 1 0 The distance between two vertices is the number of edges used in the shortest path between them. For example, 213 is a path of length two from vertex 2 to vertex 3, but 23 is the shortest path between 2 and 3. The distance between 2 and 3 in G is one. 0 1 1 0 1 0 001 0 (a) Complete the table whose (i, j)-entry is the distance between vertex i and vertex j in the graph G above. 1 2 3 4 5 5 The diameter of a graph is the largest distance between two vertices. What is the diameter of G? (b) Let d be the diameter of the graph G above (your answer in Part (a)). Compute A³, for j = 0, 1,..., d. (Aº means the identity matrix. You may use computer for this compu- tation). Determine if {A, A²,...,4} is linearly independent. Justify your answer. (c) For a graph G with adjacency matrix A, the adjacency algebra of G is A = span {A' | j≥0}, which is set of all polynomials in A. Prove that, for any graph G, the dimension of A is at least the diameter of G plus one.
graph consists of vertices and edges that join two vertices. Graphs are used to model communications networks. One way to represent a graph on n vertices is to use an n x n matrix, called the adjacency matrix of the graph. Definition: The adjacency matrix of a graph is a matrix A with its rows and columns indexed by the vertices of the graph where { 1 if vertex j is adjacent to vertex k, otherwise. Here is a graph G with five vertices and six edges and its adjacency matrix A. Graph G 3 A = 1 2 1 1 3 1 0 1 0 0 1 0 1 0 The distance between two vertices is the number of edges used in the shortest path between them. For example, 213 is a path of length two from vertex 2 to vertex 3, but 23 is the shortest path between 2 and 3. The distance between 2 and 3 in G is one. 0 1 1 0 1 0 001 0 (a) Complete the table whose (i, j)-entry is the distance between vertex i and vertex j in the graph G above. 1 2 3 4 5 5 The diameter of a graph is the largest distance between two vertices. What is the diameter of G? (b) Let d be the diameter of the graph G above (your answer in Part (a)). Compute A³, for j = 0, 1,..., d. (Aº means the identity matrix. You may use computer for this compu- tation). Determine if {A, A²,...,4} is linearly independent. Justify your answer. (c) For a graph G with adjacency matrix A, the adjacency algebra of G is A = span {A' | j≥0}, which is set of all polynomials in A. Prove that, for any graph G, the dimension of A is at least the diameter of G plus one.
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Transcribed Image Text:A graph consists of vertices and edges that join two vertices. Graphs are used to model communications
networks. One way to represent a graph on n vertices is to use an n x n matrix, called the adjacency matrix
of the graph.
Definition: The adjacency matrix of a graph is a matrix A with its rows and columns indexed by the vertices
of the graph where
Aj,k=
1 if vertex j is adjacent to vertex k,
0 otherwise.
Here is a graph G with five vertices and six edges and its adjacency matrix A.
Graph G 1
3
The distance between two vertices is the number of edges used in the shortest path between them.
2 1 3
For example,
is a path of length two from vertex 2 to vertex 3, but 23 is the shortest path
between 2 and 3. The distance between 2 and 3 in G is one.
1
Το 1 1
0
0
1
1 0
1 0
1 0
0 1 1 0 1
0 0 0 1 0
(a) Complete the table whose (i, j)-entry is the distance between vertex i and vertex j in the graph G above.
2 3 4 5
1
2
A = 1
3
4
5
The diameter of a graph is the largest distance between two vertices. What is the diameter of G?
(b) Let d be the diameter of the graph G above (your answer in Part (a)).
Compute A¹, for j = 0, 1,..., d. (Aº means the identity matrix. You may use computer for this compu-
tation).
Determine if {A, A²,..., Aª} is linearly independent. Justify your answer.
(c)
For a graph G with adjacency matrix A, the adjacency algebra of G is A = span {4³ | j≥0}, which is
set of all polynomials in A.
Prove that, for any graph G, the dimension of A is at least the diameter of G plus one.
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 with 2 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
