DATA STRUCTURES
81. What is a graph?
A graph consists of a set of vertices V and set of edges E which is
mathematically represented as G=(V,E).Each edge in a pair(V,W) where V,W,
belongs to E ,edges are sometimes referred to as arcs.
82. What are Directed graphs?
If a pair of vertices for any edge is ordered, then that graph is called as
Digraph or directed graph.
83. Define Path.
A path in a graph is a sequence of vertices w1,w2w,3,wN such that Wi,Wi+1 belongs to E for a value 1<=I<=N. The length of such a path is the number Edges on the path,which is equal to n-1.
84. Define Cycle.
A cycle is a path in which the first and last vertices are the same.
85. Define Acyclic graph.
A graph with no cycles is called Acyclic graph.A directed graph with no Edges is called as a directed Acyclic graph (or) DAG.DAGS are used for compiler Optimization process.
86. Define Connected graph.
An undirected graph is connected if there is a path from every vertex to Every other vertex.A directed graph with this property is called as strongly connected Connected graph.If a directed graph is not strongly connected but the underline graph Without direction is connected it is called as a weakly connected graph.
87. What are the conditions for a graph to become a tree?
A graph is a tree if it has two properties.
i. If it is a connected graph.
ii. There should not be any cycles in the graph.
88. Define a Weighted Graph.
A graph is said to be a weighted graph if every edge in the graph is
Assigned some weight or value.The weight of the edge is a positive value that
Represents the cost of moving the edge or the distance between two vertices.
89. Give the types of representation of graphs.
1.Adjacency matrix
2.Adjacency linked list
90. What is a minimum spanning tree?
A minimum spanning tree of an undirected graph G is a tree formed
from Graph edges.that connect all the vertices of G at lowest total cost.
No comments:
Post a Comment