Author: admin
-
Binary Operation
Consider a non-empty set A and α function f: AxA→A is called a binary operation on A. If * is a binary operation on A, then it may be written as a*b. A binary operation can be denoted by any of the symbols +,-,*,⨁,△,⊡,∨,∧ etc.The value of the binary operation is denoted by placing the…
-
Spanning Tree
A subgraph T of a connected graph G is called spanning tree of G if T is a tree and T include all vertices of G. Minimum Spanning Tree: Suppose G is a connected weight graph i.e., each edge of G is assigned a non-negative number called the weight of edge, then any spanning tree…
-
Binary Search Trees
Binary search trees have the property that the node to the left contains a smaller value than the node pointing to it and the node to the right contains a larger value than the node pointing to it. It is not necessary that a node in a ‘Binary Search Tree’ point to the nodes whose…
-
Traversing Binary Trees
Traversing means to visit all the nodes of the tree. There are three standard methods to traverse the binary trees. These are as follows: 1. Preorder Traversal: The preorder traversal of a binary tree is a recursive process. The preorder traversal of a tree is 2. Postorder Traversal: The postorder traversal of a binary tree is a…
-
Binary Trees
If the outdegree of every node is less than or equal to 2, in a directed tree than the tree is called a binary tree. A tree consisting of the nodes (empty tree) is also a binary tree. A binary tree is shown in fig: Basic Terminology: Root: A binary tree has a unique node called…
-
General Trees
A graph which has no cycle is called an acyclic graph. A tree is an acyclic graph or graph having no cycles. A tree or general trees is defined as a non-empty finite set of elements called vertices or nodes having the property that each node can have minimum degree 1 and maximum degree n.…
-
Travelling Salesman Problem
Suppose a salesman wants to visit a certain number of cities allotted to him. He knows the distance of the journey between every pair of cities. His problem is to select a route the starts from his home city, passes through each city exactly once and return to his home city the shortest possible distance.…
-
Dijkstra’s Algorithm
This algorithm maintains a set of vertices whose shortest paths from source is already known. The graph is represented by its cost adjacency matrix, where cost is the weight of the edge. In the cost adjacency matrix of the graph, all the diagonal values are zero. If there is no path from source vertex Vs to…
-
Planar Graph
A graph is said to be planar if it can be drawn in a plane so that no edge cross. Example: The graph shown in fig is planar graph. Region of a Graph: Consider a planar graph G=(V,E).A region is defined to be an area of the plane that is bounded by edges and cannot be further…
-
Complete Graph
A graph G is said to be complete if every vertex in G is connected to every other vertex in G. Thus a complete graph G must be connected. The complete graph with n vertices is denoted by Kn. The Figure shows the graphs K1 through K6. Regular Graph: A graph is said to be regular…