Dstl notes Trees, Graph and combinatorics in Discrete mathematics Aktu notes

Trees Graphs and Combinatorics

Syllabus (Topic cover in this section):

TREES: Definitions
Binary tree,
Binary tree traversal,
Binary search tree,
 
GRAPHS: Definitions and terminology,
Representation of graphs,
Multigraph,
Bipartite Graphs,
Planar graphs,
Isomorphism and Homomorphisms of the graph,
Euler and Hamiltonian paths,
Graph Coloring,
Recurrence Relation & Generating Function: Recursive definition of function,
Recursive Algorithms,
Method of solving recurrences.
 
COMBINATORICS: Introduction, 
Counting Techniques,
Pigeonhole Principle.
( Note:- Please check all kinds of information as per your college/university curriculum because it can be updated syllabus from time to time. )

https://www.rtsall.com

 

Tree: 

A tree is a connected graph that contains no cycle or circuit. It is a simple graph having no self-loop or parallel edges. A tree contains a finite set of elements which are called vertices or nodes.

Forest:

A forest is a collection of disjoint trees. It is an undirected, disconnected, acyclic graph.

Binary tree in discrete structure:

A binary tree is a tree in which the degree of every node is less than or equal to 2. A tree consisting of no nodes is also a binary tree.

Complete binary tree in discrete structure:

A binary tree is said to be a complete binary tree if all its levels, except the last, have a maximum number of possible nodes and if all the nodes at the last level appear as far left as possible.

Full binary tree:

A binary tree is said to be an extended or full binary tree if each node has either 0or 2 children.

Tree Traversal:

A traversal of a tree is a process in which each vertex is visited exactly once in a certain manner. For a binary tree we have three types of traversal:

1.Preorder traversal

Vertex visited in the following order:
  • Visit the root(N).
  • Visit the left child (or subtree) of the root(L).
  • Visit the right child (or subtree) of the root (R).

2.Inorder traversal

  • Visit the left child (subtree) of the tree.
  • Visit the root.
  • Visit the right child (subtree) of the root.

3.Postorder traversal

  • Visit the left child (subtree) of the root.
  • Visit the right child (subtree) of the root.
  • Visit the root.

What is a binary search tree?

  • A binary search tree is a binary tree T in which data is associated with the vertices.
  • The data are arranged so that, for each vertex v in T, each data item in the left subtree of v is less than the data item in v each data item in the right subtree of v is greater than the data item in v.
  • In a binary search tree since every vertex in T exceeds every number in its left subtree and is less than every number in its right subtree.

In other words,

In a binary tree, every node can have a maximum of two children but there is no need to maintain the order of nodes basing on their values. In a binary tree, the elements are arranged in the order they arrive at the tree from top to bottom and left to right.

A binary tree has the following time complexities…
  • Search Operation – O(n)
  • Insertion Operation – O(1)
  • Deletion Operation – O(n)

Operations on a Binary Search Tree

The operations are performed on a binary search tree are as follows:
  • Search
  • Insertion
  • Deletion

Search Operation in BST

In a binary search tree, the search operation is performed with O(log n) time complexity. The search operation is performed as follows:

Step 1 – Read the search element from the user.

Step 2 – Compare the search element with the value of the root node in the tree.

Step 3 – If both are matched, then display “Given node is found!!!” and terminate the function

Step 4 – If both are not matched, then check whether the search element is smaller or larger than that node value.

Step 5 – If the search element is smaller, then continue the search process in the left subtree.

Step 6- If the search element is larger, then continue the search process in the right subtree.

Step 7 – Repeat the same until we find the exact element or until the search element is compared with the leaf node

Step 8 – If we reach the node having the value equal to the search value then display “Element is found” and terminate the function.

Step 9 – If we reach the leaf node and if it is also not matched with the search element, then display “Element is not found” and terminate the function.

Difference between BFS and DFS

Breadth-First Search (BFS)

Breadth-First  Search is an algorithm for traversing or searching tree or graph data structure.
It starts at the tree root and explores the neighbor node first, before moving to the next level neighbors.

Algorithmic Steps:

Step 1: Push the root node in the queue.
Step 2: Loop until the queue is empty.
Step 3: Remove the node from the queue.
Step 4: If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in the queue.

Depth First Search (DFS)

Depth-first search (DFS) is algorithmic for traversing or searching tree or graph data structure. One starts at the root (selecting some arbitrary node as the root in the case of a graph ) and explores as for as possible along each branch before backtracking.

Algorithmic Step:

Step 1: Push the root node in the stack.
Step 2: Loop Until the stack is empty.
Step 3: Pick the node on the stack.
Step 4: If the node has an unvisited child node, get the unvisited child node, mark it as traversed, and push it on the stack.
Step 5: If the node does not have any unvisited child nodes, pop the node from the stack.

Define Graph

A graph is a non-linear data structure consisting of nodes and edges. A graph consists of two sets as follows:
1. Set V of nodes or point or vertices of graph G.
2. Set E of ordered or unordered pair of distinct edges of G.
We denote such a Graph by G(V, E) and set vertices as V(G) and set edges as E(G).
For example: 

Order of Graph (G)

If G is finite then a number of vertices in G denoted by V(G) are called an order of G.

Size of Graph (G)

The number of edges denoted by E(G) in a finite graph G is called the size of G.

Difference between Directed and Undirected Graph

Directed Graph: A directed graph is a set of vertices (nodes) connected by edges, with each node having a direction associated with it. Edges are usually represented by arrows pointing in the direction the graph can be traversed.

In other words, A  Graph G(V, E) is said to be a directed graph or digraph if each edge e belongs to E is associated with an ordered pair of vertices as shown below:
https://www.rtsall.com
Directed Graph

Undirected Graph: 

In an undirected graph, the edges are unidirectional, with no direction associated with them. Hence, the graph can be traversed in either direction. The absence of an arrow tells us that the graph is undirected.
Other words,
A graph G(V, E) is said to be undirected if each edge e belongs to E is associated with an unordered pair  of vertices as shown below:
https://www.dstlnotes.xyz
 
 
 
 

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

error: Content is protected !!