Problem $3$: If there is ever a decision between multiple neighbor nodes in the BFS or DFS algorithms, assume we always choose the letter in alphabetical order. a$)$ Consider the following adjacency matrix.

A

B

C

D

E

F

G

H

A

$0$

$1$

$1$

$1$

$0$

$10$

$0$

$0$

$0$

B

$1$

$0$

$1$

$0$

$1$

$10$

$1$

$0$

$0$

C

$1$

$1$

$0$

$1$

$0$

$10$

$0$

$0$

$1$

D

$1$

$0$

$1$

$0$

$0$

$0$

$0$

$0$

$0$

E

$0$

$1$

$0$

$10$

$0$

$0$

$0$

$1$

$1$

F

$0$

$0$

$0$

$0$

$0$

$0$

$1$

$1$

$0$

G

$0$

$1$

$0$

$0$

$0$

$1$

$0$

$1$

$0$

H

$0$

$0$

$0$

$0$

$1$

$1$

$1$

$0$

$1$

$0$

$0$

$1$

$0$

$1$

$0$

$0$

$1$

$0$

a$\mathrm{.}1)$ Draw the graph that is represented by the matrix.

a$\mathrm{.}2)$ In what order will the nodes be visited using Breadth First Search? In what order will the nodes be visited using Depth First Search?

b$)$ If you have the $0/1$ adjacency matrix of a graph, and you take the matrix to the Nth power, then the $($i$,$j$)$th entry of the result tells how many paths of length N there are from vertex i to vertex j $($here the length is measured in number of edges traversed$).$ For example, in a$)$ according to the adjacency matrix there is a path of length $1$ edge between vertices A and B$.$

A

B

C

D

E

F

G

A

$0$

$1$

$1$

$1$

$0$

$0$

$0$

m

$1$

$0$

$1$

$0$

$0$

$10$

$1$

C

$1$

$1$

$0$

$1$

$0$

$1$

$0$

D $1$

$0$

$1$

$0$

$1$

$0$

$0$

E

$0$

$0$

$0$

$1$

$0$

$1$

$0$

F

$0$

$0$

$1$

$0$

$1$

$0$

$0$

G

$0$

$1$

$0$

$0$

$0$

$0$

$0$

Let G $=($V$,$E$)$ be an undirected graph. A triangle in G is a cycle consisting of exactly three vertices $($or$,$ equivalently, three edges$).$ Suppose that G is represented as an adjacency matrix. Give an algorithm to determine whether G contains any triangle in O$($nlog$27)$ worst$-$case time.

c$)$ Using matrix multiplications, find all the triangles in the graph, represented by the following adjacency matrix.