Waste less time on Facebook — follow Brilliant.
×

Please help!

I came across this question in Graph Theory :

A graph on the vertex set \( {1,2,3,n } \) is often denoted by a matrix \(A\) of size \(n\) ,where \(aij\) and \(aji\) are equal to the number of edges with ends \(i\) and \(j\).

What is the \(Combinatorial\) \(Interpretation\) of the entries of \(A2\) ?

Ps: This is posted on behalf of Azhaghu Roopesh M.

Note by Ishan Dasgupta Samarendra
2 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

The \((i,j)\)th entry of \(A^2\) denotes the number of paths of length \(2\) between the vertices \(i\) and \(j\). The proof is easy. Let \(B=A^2\). Then \[B_{ij}=\sum_{k=1}^{n}A_{ik}A_{kj}\] Now let us interpret each of the terms in the above summation. \(A_{ik}\) denote the number of paths of length \(1\) from vertex \(i\) to vertex \(k\). Hence the product \(A_{ik}A_{kj}\) denote the number of paths of length \(2\) from \(i\) to \(j\), passing through \(k\). Thus summing over all intermediate vertices \(k\), we obtain the result. By induction, it also follows that \((i,j)\) th entry of the matrix \(A^{m}\) denote the number of paths of length \(m\) between the vertices \(i\) and \(j\).

Abhishek Sinha - 2 years, 8 months ago

Log in to reply

Thanks a lot sir ! I have a long way to go to match up with your skills :D

Btw I am reading Graph Theory from "A course in Combinatorics" , should I continue from there or perhaps you have a better suggestion for me ?

Thanks again .

Azhaghu Roopesh M - 2 years, 8 months ago

Log in to reply

I followed Diestel's book on graph theory for basics.

Abhishek Sinha - 2 years, 8 months ago

Log in to reply

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...