Graph - Concepts & Terminologies
Definition of Graph.
A Graph G (V,E) is composed of V - set of vertices and E-set of edges with no self edges.
It has two traversing operations Depth First Search (DFS) and Breadth First Search (BFS).
What are the applications of Graph?
Activity-on-Vertex (AOV) Network
Activity -on-Edge (AOE) Network
Shortest path calculation.
Electronic Circuit implementation.
GPS
Operating System - Deadlock handling
Decision making systems.
What is the difference between directed and undirected graph?
An undirected graph is one in which the pair of vertices in an edge is unordered, (v0, v1) = (v1, V0).
A directed graph is one in which each edge is a directed graph of vertices , <V0,V1> != <V1, V0>.
What is the degree of a vertex? How it is different in directed and undirected graph?
The degree of a vertex is the number of edges incident to that vertex. If (v0, v1) is an edge in an undirected graph,v0 and v1 are adjacent, which means the edge (v0, v1) is incident on vertices v0 and v1.
If <v0, v1> is an edge in a directed graph v0 is adjacent to v1, and v1 is adjacent from v0, which means the edge <v0, v1> is incident on v0 and v1.
In undirected graph, we can calculate degree as edges are bidirectional,
In directed graph, vertices are not bidirectional, hence, we can identify in-degree and out-degree explicitly.
For directed graph, the in-degree of a vertex v is the number of edges that have v as the head and the out-degree of a vertex v is //the number of edges that have v as the tail.
"Every binary tree is a graph , but every graph cannot be a binary tree." Comment & Justify.
Every binary tree is a graph with no cycles. As per the definition of graph, every graph is a set of vertices and edges and binary tree has set of vertices and edges.
But, like graph which can have cycles, binary tree is a disjoint set of vertices and hence no cycles, hence every graph may not be a binary tree.
Define path in graph.
Path is a sequence of vertices v1,v2,. . .vk such that consecutive vertices vi and vi+1 are adjacent.
Define simple path and cycle.
Simple path is a non-repeating sequence of vertices v1,v2,. . .vk such that consecutive vertices vi and vi+1 are adjacent.
Cycle is a simple path is a path of vertices v1,v2,. . .vk such that consecutive vertices vi and vi+1 are adjacent except that the last vertex is the same as the first vertex.
Define Connected Graph.
Connected graph is a graph with any two vertices are connected by some path.
Define Connected Component of Graph.
Connected Component is the maximal connected subgraph. E.g., the graph below has 3 connected components.
Define subgraph.
Subgraph is a subset of vertices and edges forming a graph.
How many total edges are possible in directed and undirected graph?
For directed graph , if it is complete has n(n -1)/2 edges as each edge is considered in both directions.
For undirected graph , if it is complete, has n(n -1) edges as each edge is considered only in one direction.
What are the operations possible on graph?
Graph Create()::=return an empty graph
Graph InsertVertex(graph, v)::= return a graph with v inserted. v has no incident edge.
Graph InsertEdge(graph, v1,v2)::= return a graph with new edge between v1 and v2
Graph DeleteVertex(graph, v)::= return a graph in which v and all edges incident to it are removed
Graph DeleteEdge(graph, v1, v2)::=return a graph in which the edge (v1, v2) is removed
Boolean IsEmpty(graph)::= if (graph==empty graph) return TRUE
else return FALSE
List Adjacent(graph,v)::= return a list of all vertices that are adjacent to v
Including two traversing operations Depth First (DFT) and Breadth First (BFT).
List all possible representations for graph.
Adjacency Matrix
Adjacency Lists
Reverse Adjacency List
Orthogonal List
Adjacency Multilist
What is adjacency matrix representation of graph?
In adjacency matrix representation, each row represent vertex at tail and column represents vertex at head for every edge. Usually, every element in matrix has value 1 for presence of edge and 0 for absence of edge.
If the graph is weighted, for presence of edge weight can be stored instead of just marking it as 1.
Efficiency
Time require for all algorithms is O(n2) as n2-n are required to be examined.
What is adjacency list representation of graph?
Takes n header nodes in array and 2e nodes in edge lists for undirected graphs.
Takes n header nodes in array and e nodes in the edge lists for directed graph.
Efficient in determining outdegree, but indegree calculations are complex.
Efficiency
All operations are always O(n+e), where n represents vertices and e represents edges (edge nodes).
What is inverse adjacency list representation of graph?
Same as adjacency list except every edge node represents incoming edge instead of outgoing.
Efficient in determining indegree, but outdegree calculations are complex.
Efficiency
All operations are always O(n+e), where n represents vertices and e represents edges (edge nodes).
What is orthogonal list representation of graph?
Orthogonal list has multiple header nodes sharing common edge nodes in the linked list. We can say, it is a linked representation of adjacency matrix.
Efficient in determining both in-degree as well as out-degree, but overall implementation is complex.
Efficiency
All operations are always O(n+e), where n represents vertices and e represents edges (edge nodes).
What is adjacency multi-list representation of graph?
Exclusively used to represent undirected graph as edge nodes can be shared amongst multiple lists.
Efficiency
Efficient utilization of memory as undirected graph needs two edge nodes to be created in adjacency list or orthogonal list, which is avoided in this.
What are the two operations of graph traversal?
Depth First Search - Once a possible path is found, continue the search until the end of the path.
Breadth First Search - Start several paths at a time, and advance in each one step at a time.
Explain Depth First Search / Traversal algorithm?
Depth First Search / Traversal Algorithm (Recursive):-
/* Graph can be disconnected so it is needed to invoke depth first traversal for every node/verted separately. */
For every node nd
visit(nd) = FALSE;
s = a pointer to the starting node foe the traversal;
While ( s != NULL)
{
dftraverse(s);
s = select();
}
/* Actual function for traversal of graph using starting node/vertex. */
dftraverse(s)
{
visit(s);
p = successor();
while ( p != NULL)
{
if ( visited(p) == FALSE)
dftraverse(p);
p = successor(s);
}
}
Depth First Search / Traversal Algorithm (Non-Recursive):-
for (every node nd) visited(nd) = FALSE;
s = a pointer to the starting node for traversal;
ndstack = EMPTY;
While ( s != NULL)
{
visit(s);
p = successor(s);
while ( (p == NULL) && (!isempty(ndstack))
{
s = pop(ndstack);
p = successor(p);
}
if ( p != NULL)
{
push(p);
s = p;
}
else s = select();
}
Efficiency
Adjacency matrix (operations) – n2 + n i.e. O(n2)
Adjacency list (operations) – O(n + e)
Application - Topological sort
Explain Breadth First Search / Traversal algorithm?
Breadth First Search / Traversal Algorithm (Recursive):-
/* Every node must be selected as starting node as graph can be disconnected .*/
ndque = EMPTY;
While ( s != NULL)
{
visit(s);
insert(ndque, s);
while (!isemptyq(ndque))
{
p = deleteq(ndque);
p = successor(p);
while (p != NULL)
{
if (!visited (p))
{
visit(p);
insert (ndque, nd);
}
p = successor(p);
}
}
s = select();
}
Efficiency
O(n2) operations for adjacency matrix
O(n+e) operations for adjacency list
Applications -
Finding cycles
To find Connected components in a graph
To calculate Shortest path
What is AOV network?
Definition
An Activity On Vertex(AOV) network is a directed network in which each vertex models some subtask that must be completed as part of an overall task, and each edge models a prerequisite relationships between the activity of its head and that of its tail.
Topological Sort can provide linear list of activity.
Topological Sort
A topological sort is an ordering of the vertices in a digraph such that no vertex precedes any vertex it is adjacent from (no activity occurs before any of its prerequisites).
Topological sort is possible in a digraph having no cycles. and one digraph will have several topological sorts.
Implementation Issues
What is AOE network?
Definition
An activity on edge network is a directed network in which each edge models an activity with the weight of the edge representing the time needed to complete the activity
The vertex models significant events
1.An event represented by a vertex only happens when all of the activities modeled by edge leading into it have been completed
2.No activity can start until the event modeled by the vertex at its tail has occurred
3.The events modeled by the vertices are often project milestones such as “specification accepted by user”
4.Normally, we include a start vertex with in-degree 0 to model the event “Project Begins”
Applications - Evaluate performance to reduce time
Critical path - A path that has largest length, It defines minimum time required to complete the project.
Slack time = Latest Time (i) – Earliest Time (i)
Amount of time by which activity will be delayed without affecting project finish time
Finding the critical path proceeds in two phases
1.Forward phase – calculates earliest time for each event ( ETj = ETi + Dij (max) )
2.Backword phase - calculates latest time for each event ( LTi = LTj + Dji (min) )
Want to read more?
Subscribe to questionbankos.com to keep reading this exclusive post.
