Question

Write a program that specifies a simple undirected graph by its “adjacency matrix”. Recall that that the adjacency matrix A is such that A(i, j) = 1 if nodes i and j are adjacent and A(i, j) = 0 otherwise.

• Let α_k(i ,j) be the number of paths of length k between nodes i and j. For instance, the number of paths of length-1 between nodes i and j in a simple undirected graph is 1 if they are adjacent and zero otherwise.

• Show by numerical experiments that the matrix A_k allows you to calculate α_k(i ,j) for all i and j. You should consider small graphs for which you can verify the result by hand. You should submit the code and your numerical verification.

Answer 1

I have written page number on the page so you can sequence them easily

//Code that verifies the above proven statements and demonstrates the results

You have to understand Matrix exponentiation to understand the code because for greater values of k, time complexity would be exponential by using brute force approaches.

#include <bits/stdc++.h>
using namespace std;
#define N 3
// Function to multiply two matrices
void multiply(int a[][N], int b[][N], int AK[][N])
{
   int mul[N][N];
   for (int i = 0; i < N; i++)
{
       for (int j = 0; j < N; j++)
{
           mul[i][j] = 0;
           for (int k = 0; k < N; k++)
               mul[i][j] += a[i][k] * b[k][j];
       }
   }
// Storing the multiplication result in res[][]
   for (int i = 0; i < N; i++)
       for (int j = 0; j < N; j++)
           AK[i][j] = mul[i][j];
}

// Function to compute G raised to the power n
void power(int A[N][N], int AK[N][N], int n)
{

   // Base condition
   if (n == 1) {
       for (int i = 0; i < N; i++)
           for (int j = 0; j < N; j++)
               AK[i][j] = A[i][j];
       return;
   }

   // Recursion call for first half
   power(A, AK, n / 2);

   // Multiply two halves
   multiply(A, A, AK);

   // If n is odd
   if (n % 2 != 0)
       multiply(AK, A, AK);
}
int main()
{
   int A[N][N] = { { 1, 1, 1 },
                   { 0, 0, 1 },
                   { 0, 1, 0 } };

   int k, AK[N][N];
cout << "Enter the value of k" << endl;
cin>>k;
power(A, AK, k);
for (int i = 0; i < N; i++)
{
       for (int j = 0; j < N; j++)
           cout << AK[i][j] << " ";
       cout << "\n";
   }
return 0;
}