1 Crore+ students have signed up on EduRev. Have you? |
Tree:
A tree is a connected subgraph of a connected graph containing all the nodes of the graph but containing no loops, i.e., there is a unique path between every pair of nodes.
The number of closed paths in a tree of the graph is zero. Therefore is not true for tree and graph.
Twig: The branches of the tree are called twigs.
Link: Those branches of the graph which are not in the tree.
Co-tree: All the links of a tree together constitute complement of the tree and is called co-tree, in which the number of branches is equal to b - (n - 1)
Where b is the number of branches of the graph.
Number of twigs: t = n - 1
Number of links: L = b - t = b – n + 1
A red-black tree is a balanced binary search tree with the following properties:
Concept:
Tree:
The degree of a node is the number of its children. The degree of a tree is the maximum degree of any of its nodes.
The maximum number of binary trees that can be formed with 4 unlabeled nodes is
# unlabelled binary trees with 1 node
= 1
# with 2 nodes : -
= 2
# with 3 nodes :-
# with 4 nodes :-
An undirected graph G which is connected and acyclic is called ____________
An undirected graph G which is connected and acyclic is termed as a tree. G contains no cycles and if any edge is added to G a simple cycle is formed.
A star tree of order n is a tree with as many leaves as possible or in other words a star tree is a tree that consists of a single internal vertex and n-1 leaves. However, an internal vertex is a vertex of degree at least 2.
Every tree element is called a node and the lines connecting the elements are called branches. A finite tree structure has a member that has no superior and is called the “root” Or root node. Nodes that have no child are called leaf nodes.
A graph is called a bipartite graph if and only if it contains no cycle of odd length. Every tree is a bipartite graph and a median graph.
The number of labeled trees of k number of vertices is kn-2. Two labeled trees are isomorphic if their graphs are isomorphic and the corresponding points of the two trees have the same labels.
A directed acyclic graph is known as a polytree whose underlying undirected graph is a tree. In other words, a directed tree is a directed graph which would be tree if the directions on the edges were ignored.
23 videos|63 docs|60 tests
|
Use Code STAYHOME200 and get INR 200 additional OFF
|
Use Coupon Code |
23 videos|63 docs|60 tests
|
|
|
|
|
|
|
|
|
|