Sunday, 6 November 2016

IPU Computer Science - Discrete Mathematics - Trees vs Graphs

Trees vs Graphs

IPU Computer Science - Discrete Mathematics - Trees vs Graphs




Trees Graphs
Shape
Model Type Hierarchical Network
No. Of Edges n-1 edges Depends on graph shape
Path Minimally connected graph, contains only one path between any two vertices. More than one path possible. Can be uni-directional or bi-directional.
Root Node One Root, Child has one Parent No concept of Root or Parent
Parent Child Relationship Parent Child relationship when moves from top to bottom. No such concept of parent child relationship.
Loops Special type of graph having no loops or circuits. Have loops, circuits and self-loops
Traversal Pre-Order, In-Order and Post-Order Depth First Search (DFS) or Breadth First Search (BFS)
Connecting Rules Restrictions for making connection between nodes through edges. As such no restrictions while connecting edges and nodes.
Direction Directed Acyclic Graph Cyclic or Acyclic
Complexity Less complex as compared to graphs. No loops, no cycles etc. More complex as it contains loops, cycles etc.
Types Binary Tree, Binary Search Tree, AVL Tree, Heaps etc. Directed and Undirected graphs
Applications Used in sorting and searching like tree traversing, binary search. Manipulate hierarchical data PERT or CPM algorithms, Graph colouring, job scheduling etc.

No comments:

Post a Comment