Graph theory

Question 1

Define transitivity for a graph

Answer 1

if a is related to b and b is related to c then a must be related to c.

Question 2

Imagine you have Gi, Gj graphs how would you figure out whether they are isomorphic to each other?

Answer 2

1. Look at each graph’s degree and determine if it matches with another graph. if no (it is subset in the partition)
2. if all vertices in Gi have an equal degree with Gj then they are isomorphic.

Question 3

What does degree mean?

Answer 3

The number of edges a vertical has on an undirected graph.

Question 4

in a directed graph; what is the difference between out-neighbor and in-neighbor?

Answer 4

out-neighbor: any other vertex that can be reached by following an edge that points away from the given vertex. EX A->B then B is out-nerighbor.

in-neighbor: any vertex from which the given vertex can be reached by following an edge that points towards the given vertex. EX A<-B then B is a in-neighbor

Question 5

in a directed graph; what is the difference between out-degree and in-degree?

Answer 5

Out-degree is the number of edges going out from that vertex to other vertices (number of out-neighbors)

hin-degree of a vertex is the number of edges coming into that vertex from other vertices (the number of in-neighbors).

Question 6

what word do you use when you want to solve algorithms in an alphabetic order?

Answer 6

lexiographic order

Question 7

How would you describe DFS

Answer 7

You want to find the route that go farthest before backtracking

Question 8

How would you decribe BFS?

Answer 8

Explores all neighbors before moving to the next

Question 9

How would you do Topological sort?

Answer 9

1. consider in lexiographic order the directed edges and note delevery/finish-time.
   call DFS to compute finish time
   as vertex v finished, add to front of list

Question 10

How would you do SCC(strongly connected components)

Answer 10

1. in lexicographic order consider directed edges and note discovery/finish time.
2. group vertacies
3. note in krøllet parenteser your grouped vertcies.