1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Aleonysh [2.5K]
2 years ago
12

Find the number of paths of length 4 between two different vertices in K5​

Mathematics
1 answer:
Mkey [24]2 years ago
4 0

K₅ is the 5-complete graph, with adjacency matrix

A = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{bmatrix}

The (i, j)-th entry of the matrix A⁴ gives the number of length-4 paths from vertex i to vertex j. Computing A⁴ isn't so bad:

A^2 =  \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{bmatrix}  \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{bmatrix} =  \begin{bmatrix} 4 & 3 & 3 & 3 & 3 \\ 3 & 4 & 3 & 3 & 3 \\ 3 & 3 & 4 & 3 & 3 \\ 3 & 3 & 3 & 4 & 3 \\ 3 & 3 & 3 & 3 & 4 \end{bmatrix}

A^4 = \begin{bmatrix} 4 & 3 & 3 & 3 & 3 \\ 3 & 4 & 3 & 3 & 3 \\ 3 & 3 & 4 & 3 & 3 \\ 3 & 3 & 3 & 4 & 3 \\ 3 & 3 & 3 & 3 & 4 \end{bmatrix} \begin{bmatrix} 4 & 3 & 3 & 3 & 3 \\ 3 & 4 & 3 & 3 & 3 \\ 3 & 3 & 4 & 3 & 3 \\ 3 & 3 & 3 & 4 & 3 \\ 3 & 3 & 3 & 3 & 4 \end{bmatrix} = \begin{bmatrix} 52 & 51 & 51 & 51 & 51 \\ 51 & 52 & 51 & 51 & 51 \\ 51 & 51 & 52 & 51 & 51 \\ 51 & 51 & 51 & 52 & 51 \\ 51 & 51 & 51 & 51 & 52 \end{bmatrix}

We want the paths between two distinct vertices, so we ignore the entries on the diagonal and take the total of the non-diagonal entries, 20 • 51 = 1020.

You might be interested in
Jerome wrote the following scenario to match the algebraic expression s 4 − 16: “16 fewer than four times the number of songs on
Xelga [282]

Answer:

No, because the expression s/4 - 16. In the word formed she times 4 and the letter, she should have to dived it.

Step-by-step explanation:

No, because the expression s/4 - 16. In the word formed she times 4 and the letter, she should have to dived it.

5 0
3 years ago
Read 2 more answers
Which point is NOT on the line y = 2x + 3?
yaroslaw [1]

Answer:

i thinks the answer of that is letter A

5 0
3 years ago
Read 2 more answers
What is the value of x in the isosceles trapezoid below?
Yuki888 [10]
C. 10

14x+14x+(3x+10)+(3x+10)=
34x+20=360=
X=10
6 0
3 years ago
Read 2 more answers
What is answer please
Tanzania [10]

Answer:

during the first 3mins the bus was accelerating from 0km to 25 kilometers

during the next 90 mins btwn 30mins to 120 mins it was moving at a constant distance n speed

lastly for the last 60 mins from 120 mins to 180 mins it started decelerating from a distance of 25km to 0 km

8 0
3 years ago
Which linear equation has no solution?
attashe74 [19]

9514 1404 393

Answer:

  5x + 12 = 5x - 7

Step-by-step explanation:

There will be no solution when the coefficients of x are the same on both sides of the equal sign and the constants are different. That is the case for ...

  5x + 12 = 5x - 7

This reduces to ...

  19 = 0 . . . . . no value of x will make this be true: NO SOLUTION

3 0
3 years ago
Other questions:
  • A gardener wants to run a border around the outside of her garden. She plots it on a grid to plan how much she will need. The ga
    8·1 answer
  • .
    13·1 answer
  • Show steps in solving ax^2+bx+c=0
    10·1 answer
  • how to cheat on a test when your teacher lets you look up the answers on the computer and you can not use your phone
    15·1 answer
  • Daniel is starting his own sewing business. Daniel has calculated that he needs to earn $360 per week to support his family. If
    6·1 answer
  • An automobile insurance company divides customers into three categories: good risks, medium risks, and poor risks. Assume that o
    7·1 answer
  • Can anyone help with this asap?<br>8x² + 26xy + 15y²​
    6·1 answer
  • What’s the answer to this ?
    8·2 answers
  • Light travels at a speed of about 1.86×105 miles per second. Suppose a space ship is able to travel at the speed of light. If th
    5·1 answer
  • Learn with an example
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!