Graphs & graph algorithms

Question 0

what is complete graph (clique) ?

what is bipartite?

Answer 0

a graph is complete if every pair vertices is joined by an edge.

two sets of disjoint vertices, each vertices is joined with all the vertices on the other set. bipartite is complete

Question 1

what is connected graph?
what is a tree?
what is a forest?

Answer 1

if every pair of vertices is joined by a path

tree is connected and acyclic

a forest is acyclic and components are trees

Question 2

directed graph
u->v
in degree and out degree of a vertice

Answer 2

u is adjacent to v and v is adjacent from u
in degree = number of arrow pointing to the vertices
out degree = number of arrow pointing from the vertices

Question 3

depth first search vs breadth first search

Answer 3

depth first search follows a path of unvisited vertices until path can not be extended the backtrack until an unvisited vertex can be reached.  
a   d  e
||
V
b
||
V
c

breadth first search visits all the adjacent vertices first. referring to processing the current vertex. visited nodes are added into the queue. continue until all vertices in the current component have been processed

a=>d=>f
b
c

Question 4

application of depth first search and its complexity

Answer 4

to determine a connected graph
to identify the connected component of graph
to determine a cycle
to determine a bipartite

complexity O(n+m)
n is number of vertices
m is number of edges

Question 5

application of breadth first search and its complexity

Answer 5

find the distance between two vertices in a graph
distance is the number of edges in the shortest path

complexity = O(|V| + |E|) 
v is number of vertices 
E is number of edges 
each vertices is visited once and each 
each adjacent  list is traversed once

Question 6

Dijkstra algorithm

Answer 6

create list of all known nodes and include starting node u with distance of 0

set all unknown nodes shortest distance to infinity

calculate all distances from u to adjacent nodes (0 + distance)

update the shortest distances of the adjacent nodes according to min(current distance, distance of u+distance)

visit the node with the shortest distance and continue the update shortest nodes and visit the shortest distance nodes until the destination is reached

Question 7

directed acyclic graph
topological order
source and sink

Answer 7

DAG is a directed graph with no cycles

topological order in DAG is a labelling of vertices such that label u < label v

only DAG has topological order

source is a vertex with in degree 0
sink is a vertex with out degree 0

DAG has at least one source and one sink

Question 8

Spanning tree

Answer 8

a subgraph that includes all vertices of the graph and is a tree

Question 9

prim jarnik algorithm

Answer 9

find minimum spanning tree

it finds a subset of edges that forms a tree that includes every vertex where the total weight of all the edges is minimized

local optimality -> globally optimal

Question 10

dijkstra refinement to shortest spanning tree

Answer 10

introduce attribute bestTV for each non tree vertex q which distance between p and q is minimized

complexity O(n^2)