Trees

>> rules :-

If a graph G there is one and only one path between each pair of vertices G is a tree.
A graph is a tree if and only if it a minimal connected.

>> Directed trees :- tress having indegree 1 and no outdegree are called external , terminal (nodes or vertices) or vertices.

the node which has outdegree greater than 1 is called internal node.

Discrete Mathematics Introduction of Trees

>> ordered tree :- order is defined.

>>Rooted Trees:

If a directed tree has exactly one node or vertex called root whose incoming degrees is 0 and all other vertices have

incoming degree one, then the tree is called rooted tree.

Note:

A tree with no nodes is a rooted tree (the empty tree)
A single node with no children is a rooted tree.

>> path length

>> Diff between trees and graphs:-

> trees have unique path to each vertex but graphs can have many paths.

>in trees there is only one root node but in graphs there is no such thing like root node.

>trees don't have loops and self loops

>trees have n-1 edges if it have n vertices but graph can have any numbr of edges.

>trees are hierarchical model whereas graph are network model.

>An n-vertex graph has n-1 edges.

> an n vertex tree also have n-1 edges.

Binary Trees :-

>>General tree can have any number of children but binary tree have only 2 childern one left child and one right child.

every node can have either 0 children or 1 child or 2 children but not more than 2 children

there is no such general tree having zero nodes but binary tree can have empty general tree.

>>Basic Terminology:

>> in upper figure B is left child and C is right child of A.

Ancestors : in upper figure A is ancestor of all other nodes.

Descendent : in upper figure all the nodes are descendant of root node A.

Left sub tree : in upper figure B is left child of its parent A so it is left sub tree similarly C is right sub tree of A .

level of node : distance from root node is called level and level of root node is 0.

maximum number of nodes at any level n is 2n.

Depth or Height of a tree: max number of nodes in a branch of tree , depth of root node is 1

maximum number of nodes in a binary tree of depth d is 2d-1, where d ≥1

External nodes: have no children

Internal nodes: have one or more children.

Traversal of Binary trees

Algorithm to draw a Unique Binary Tree when In order and Preorder Traversal of the tree is Given:

Algorithm to draw a Unique Binary Tree when Inorder and Postorder Traversal of the tree is Given:

inorder 4 6 10 12 8 2 1 5 7 11 13 9 3

Postorder 12 10 8 6 4 2 13 11 9 7 5 3 1

Algorithm to convert General Tree into the binary tree

general form :

binary form

spanning trees :- if any connected graph have n vertices and e edges then a tree of that graph which contain all vertices and n-1 edges then it is callled spanning tree.

disconneted graphs don't form spanning tree

A complete undirected connected graph can have maximum

nn-2 number of spanning trees

Circuit Rank: jaise ek connected graph dia hai jisme n nodes hain and e edges hain to iske spanning tree mein n-1 edges honge to circuit rank = e - (n-1) yaa phir kitna edges remove krna pdega spanning tree bnane k liye .

Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning tree is minimally connected.
Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is maximally acyclic.

>>cut sets :

> Connectivity: kisi bhi 2 vertex k beech m path hona chaiye .

>Cut Vertex : vertex jiske remove krne se graph dissconnected bn jaae and max it can have

n-2 cut vertex.

>Cut Edge (Bridge): edge jiskr remove krne se graph disconnected bn jaae. and max number of cut edges possible = n-1. if cut edge exist then cut vertex exist but if cut vertex exist then cut edge may or maynot exist.

>Cut Set of a Graph: agr total edges m se some edges remove krne se graph disconnected horha hai to set of those edges is called cut edges.

>Edge Connectivity : Let ‘G’ be a connected graph. The minimum number of edges whose removal makes ‘G’ disconnected is called edge

connectivity of G. Notation − λ(G)

>Vertex Connectivity

Let ‘G’ be a connected graph. The minimum number of vertices whose removal makes ‘G’ either disconnected or reduces ‘G’ in to a trivial graph is called its vertex connectivity.

Notation − K(G)

>Notation − For any connected graph G,

K(G) ≤ λ(G) ≤ δ(G)

Vertex connectivity (K(G)), edge connectivity (λ(G)), minimum number of degrees of G(δ(G)).

>>For every spanning tree with n vertices and n edges what is the least number of different Spanning trees can be

formed is 3 because n-1 edges koi cycle ni bnaenge and last edge ek cycly bnaega to 3 diff types se uss edge ko remove kr paaenge.