A Graph consists of sets of nodes and a set of arcs. Each arc in a graph is specified by a pair of nodes.
2) What is a digraph?
If the pair of nodes that make up the arcs are ordered pairs, then the graph is called as a digraph.
3) Define the term incident.
A node n is incident to an arc x, if one of the two nodes in the ordered pair of nodes that constitutes x.
4) What is degree of node in a graph?
The degree of a node is the number of arcs incident to it.
5) What is indegree and outdegree?
Indegree of a node n is the number of arcs that have n as the head and the outdegree of n is the number of arcs that have n as the tail.
6) Define the term adjacent
A node n is adjacent to a node m, if there is an arc from m to n.
7) What is a weighted graph?
A graph in which there is a number associated with each arc is called as weighted graph.
8) What is cycle, cyclic graph and acyclic graph?
A path from a node to itself is called a cycle. A graph that has a cycle is called cyclic graph. The graph that do not have cycle is called acyclic graph.
9) What is capacity function?
Capacity function c(a,b), is defined as Let a, b are nodes. Adjacent(a,b) is tue , c(a,b) is the capacity of the pipe from a to b. If there is no pipe C(a,b)=0;
10) What is flow function?
The flow function f(a,b) is 0 if b is not adjacent to a, and the amount of water flowing from the pipe a to b otherwise.
11) What is a forest?
A forest may be defined as an acyclic graph in which every node has one or no predecessors.
12) What is a tree?
A tree may be defined as a forest in which only a single node called the root exists, and has no predecessors.
13) What is an ordered forest?
Any forest that consists of collection of trees that are ordered is called ordered forest.
14) What is a spanning forest?
Given a graph G, F is a spanning forest of G if
i) F is a subgraph of G containing all nodes of G
ii) F is an ordered forest containing trees t1, t2… tn
iii) Ti contains all nodes that are reachable in G from the root of Ti and are not contained in Tj for some j must exist whenever an arc
16) Define DFS and BFS.
DFS visits all nodes that are reachable from s. BFS visits all the successors of a visited node before visiting any successors of any of those successors.
17) What is a minimum spanning tree?
Minimum spanning tree is one in which the sum of the weights of the tree edges is as small as possible
No comments:
Post a Comment