A subgraph is a subset of branches and nodes of a graph. There are two types of a subgraph. If the subgraph contains branches and nodes less in number than those on the graph, then a subgraph is called proper subgraph.
If a subgraph contains all the nodes of a graph and the branches, then a subgraph is called improper subgraph.
A path is a improper subgraph such that,
i) At the terminating node only one branch is incident.
ii) At the remaining nodes, two branches are incident.
If a path exists between any pair of nodes, then graph is called connected graph; otherwise its called a disconnected graph.
Tree:
Tree is a set of branches with every node connected to every other node, such that any one of the branches removed changes the property. In other words, we can state that a connected subgraph of a connected graph containinng all the nodes of the graph not forming any loop. Thus, tree is a set of branches with all nodes not forming any loop or closed path.
Properties of a tree:
1) Tree contains all nodes of the graph.
2) Tree does not contain any closed path.
3) In a tree, there exists only one path between any pair of nodes.
4) In a tree, minimum end nodes or terminal nodes are two.
5) Every connected graph has at least one tree.
6) The rank of the tree is same as the rank of the graph i.e (n-1).
7) Tree contain (n-1) branches if n are nodes of the tree.
If a subgraph contains all the nodes of a graph and the branches, then a subgraph is called improper subgraph.
A path is a improper subgraph such that,
i) At the terminating node only one branch is incident.
ii) At the remaining nodes, two branches are incident.
If a path exists between any pair of nodes, then graph is called connected graph; otherwise its called a disconnected graph.
Tree:
Tree is a set of branches with every node connected to every other node, such that any one of the branches removed changes the property. In other words, we can state that a connected subgraph of a connected graph containinng all the nodes of the graph not forming any loop. Thus, tree is a set of branches with all nodes not forming any loop or closed path.
Properties of a tree:
1) Tree contains all nodes of the graph.
2) Tree does not contain any closed path.
3) In a tree, there exists only one path between any pair of nodes.
4) In a tree, minimum end nodes or terminal nodes are two.
5) Every connected graph has at least one tree.
6) The rank of the tree is same as the rank of the graph i.e (n-1).
7) Tree contain (n-1) branches if n are nodes of the tree.
0 comments:
Post a Comment