A graph is a mathematical tool used to represent a physical problem. It is also used to model networks, data structures, scheduling, computation and a variety of other systems where the relationship between the objects in the system plays a dominant role.
Types of graph: A graph often symbolized as G can be of two types: 1. Undirected graph: where a pair of vertices representing an edge is unordered. 2. Directed graph: where a pair of vertices representing an edge is ordered.
Graph Traversal: A graph can be traversed in two ways: Depth first search traversal: often analogous to pre-order traversal of an ordered tree. Breadth first search traversal: often analogous to level-by-level traversal of an ordered tree.
Spanning Tree: Given a connected, undirected graph, a spanning tree of that graph is a sub graph which is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavourable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree.
Shortest Path: In graph theory, the shortest path problem is the problem of finding a path between two vertices in a weighted graph such that the sum of the weights of its constituent edges is minimized.
The most important algorithms for solving this problem are: Dijkstra’s algorithm solves the single-source shortest path problems. Bellman-Ford algorithm solves the single source problem if edge weights may be negative. A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.
Describe Kruskal’s minimal spanning tree algorithm.
Kruskal’s algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). Kruskal’s algorithm is an example of a greedy algorithm.
It works as follows:
1. Create a forest F (a set of trees), where each vertex in the graph is a separate tree 2. Create a set S containing all the edges in the graph 3. While S is nonempty 4. Remove an edge with minimum weight from S 5. If that edge connects two different trees, then add it to the forest, combining two trees into a single tree 6. Otherwise discard that edge. 7. At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph.
Write the Prim’s algorithm for finding MST from a graph.
Prim’s algorithm is a Greedy algorithm. It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST.
Algorithm:
1) Create a set mistSet that keeps track of vertices already included in MST. 2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first. 3) While mstSet doesn’t include all vertices a) Pick a vertex u which is not there in mstSet and has minimum key value. b) Include u to mstSet c) Update key value of all adjacent vertices of . To update the key values, iterate through all adjacent vertices. For every adjacent vertex v. if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v
Short note on Dijkstra’s Algorithm:
Dijkstra’s algorithm works on the principle that the shortest possible path from the source has to come from one of the shortest paths already discovered. A way to think about this is the “explorer” model-starting from the source, we can send out explorers each travelling at a constant speed and crossing each edge in time proportional to the weight of the edge being traversed. Whenever an explorer reaches a vertex, it checks to see if it was the first visitor to that vertex: if so, it marks down the path it took to get to that vertex. This explorer must have taken the shortest path possible to reach the vertex. Then it sends out explorers along each edge connecting the vertex to its neighbors. It is useful for each vertex of the graph to store a “prev” pointer that stores the vertice from which the “explorer” came from. This is the vertex that directly precedes the current vertex on the path from the source to the current vertex. The pseudocode for Dijkstra’s algorithm is fairly simple and reveals a bit more about what extra information needs to be maintained. Vertices will be numbered starting from 0 to simplify the pseudocode.
Given a graph, G, with edges E of the form (v1, v2) and vertices. V, and a source vertex, s. dist: array of distances from the source to each vertex pointers to preceding vertices. prev array of : array of pointers to prededing vertices i: loop index F : list of finished vertices U : list or heap unfinished vertices /* Initialization: set every distance. to INFINITY until we prev[i] = NULL discover a path */ for i = 0 to |V| – 1 dist[i] = INFINITY prev [i] = NULL end /* The distance from the source to the source is defined to be zero */ dist [s] = 0 /* This loop ccorresponds to sending out the explorers walking the paths. where * the step of picking “the vertex, v, with the shortest path to s corresponds to an explorer arriving at an unexplored vertex */
while (F is missing a vertex) pick the vertex, v, in U with the shortest path to s add v to F for each edge of v, (v1, v2) /* The next. step is sometimes given the confusing “relaxation” if(dist [v1] + length (v1, v2) < dist [v2]) dist [v2] = dist[v1]+ length (v1, v2) prev[v2] = v1 possibly update U, depending on implementation end if end for end while
Compare DFS and BFS:
Depth First Search: DFS of a graph is analogous to the per-order traversal of an ordered tree. For a given graph the DFS will have the following rules. Rule 1: If possible, visit an adjacent unvisited vertex, mark it visited, and push it on the stack. Rule 2: If Rule 1 fails, then if possible pop a vertex off the stack follow Rule 1 from it. Rule 3: Repeat Rule 1 and Rule 2 until the all the vertices are visited.
Breadth First Search: BFS of a graph is analogous to level-by-level traversal of an ordered tree. For a given graph the BFS will have the following rules. Rule 1: Visit all the next unvisited vertices (if any) that is adjacent to the current vertex, and insert them into a queue one at a time on every visit. Rule 2: If there is no unvisited vertex, remove a vertex from the Queue and make it the current vertex and then follow Rule 1. Rule 3: Repeat Rule 1 and Rule 2 until the all the vertices visited. Breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored.neighbor nodes, and so on, until it finds the goal. The time complexity can also be expressed as O(E+VI) since every vertex and every edge will be explored in the worst case.
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure. or graph. Intuitively, one starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking. The time complexity is also given by O(| E|+| VI).
Prove that the number of odd degree vertices in a graph is always even.
The number of odd degree vertices in a graph is always even: Degree of a vertex is defined as no. of edges incident on a particular vertex with the self loop counted twice. Now, let us take the sum of degree of all the vertices. Now. this summation is an even number, because each edge contributes twice when we are calculate degree of different vertices. Now, if we take the summation of all the degrees
that is nothing but the twice the number of edges = 2e = even number