Question

3. (10 points) Let G be an undirected graph with nodes vi,..Vn. The adja.- cency matriz representation for G is the nx n matrix M given by: Mij-1 if there is an edge from v, to ty. and M,',-0 otherwise. A triangle is a set fvi, vjof 3 distinct vertices so that there is an edge from v, to vj, another from v to k and a third from vk to v. Give and analyze an algorithm for deciding whether a graph has a traingle in it, where the input graph is given by its adjacency matrix representation. Analyze your algorithm's worst-case performance first in terms of just the number of nodes n of the graph, then in terms of n and the number of edges m of the graph. Your algorithm should be faster when m<

Please show work clearly. Thanks

Answer 1

Answer:

Undirected Graph:

An undirected graph G is a set of vertices or nodes that are connected together where all the edges are bidirectional. An undirected graph is sometimes called an undirected network. In contrast, a graph where the edges point in a direction is called a directed graph.

One can define the undirected graph as G= (N, E), consisting of the set N of nodes and the set E of edges, which are unordered pairs of elements of N.

The most commonly used representation ways of graphs are:

• Adjacency Matrix
• Adjacency List

Adjacency Matrix:

An adjacency matrix is a square matrix which used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the given graph.

Adjacency Matrix is basically a 2D array of size nx n where n is the number of vertices in a graph. Let the 2D array be M [][]. A slot M [i][j] = 1 indicates that there is an edge from vertex i to vertex j.

Adjacency matrix for undirected graph is in always symmetric manner. Adjacency Matrix is also used to represent weighted graphs. If M[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

The adjacency matrix cell (i,j) contains a “1” if the graph has an edge from vertex i to vertex j.If there is an edge from i to j is undirected then there is also an edge from j to i. Thus, the cell (j,i) contains a value “1” as well. Cell (i,j) is equal to cell (j,i) for all cells.

A triangle is a set {Vi,Vj,Vk} of 3 distinct vertices so that there is an edge from Vi to Vj, second from Vj to Vk and third from Vk to Vi. These edges form a cycle.

Algorithm:

• Determine if an undirected graph G = (V, E) is connected where set of V = n and set of E= m.
• Find the cycle Vi to Vk through Vj in an undirected graph G.

1) Initialize all vertices as not visited.

2) Do following for every vertex 'v'.

       (a) If 'v' is not visited before, call DFSUtil(v)

       (b) Print new line character

DFSUtil(v)

1) Mark 'v' as visited.

2) Print 'v'

3) Do following for every adjacent 'u' of 'v'.

     If 'u' is not visited, then recursively call DFSUtil(u)

     Check for cycle CyclicUtil(v)

CyclicUtil(v)

1) Mark 'v' as visited.

2) From adjacency Vi to Vk through Vj

            If Vi is visited

                CyclicUtil(Vi)

            Else

                        Parent (Vi) not equal to Vk ( // If an adjacent is visited and not parent of current vertex, then there is a cycle.)

Print Cycle

3) Do following for every adjacent 'Vk' to 'Vi'.

CyclicUtil(Vk)

Algorithm's Performance Analysis:

We have used matrix representation of undirected graph. we allocate n×n nodes of matrix to store node-connectivity information for example M[i][j]=1 if there is edge between nodes i and j, otherwise M[i][j]=0.

Complexity of an algorithm in Worst Case:

(1) In terms of nodes n of the graph:

Adjacency matrix will take O(n²) time cpmplexity.

(2) In terms of nodes n and number of edges m of the graph:

  Adjacency matrix will take O(n+m) time cpmplexity.