[go: up one dir, main page]
Scribd
Upload
14 views40 pages

Discrete Structure 14 - Trees

The lecture discusses the concept of trees in graph theory, defining them as connected graphs without nontrivial circuits. It covers properties of trees, types of trees such as rooted and m-ary trees, and includes exercises to illustrate these concepts. Additionally, it explains the characteristics of binary trees and the theorem related to full m-ary trees.

Uploaded by

ahmadleo498
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views40 pages

Discrete Structure 14 - Trees

The lecture discusses the concept of trees in graph theory, defining them as connected graphs without nontrivial circuits. It covers properties of trees, types of trees such as rooted and m-ary trees, and includes exercises to illustrate these concepts. Additionally, it explains the characteristics of binary trees and the theorem related to full m-ary trees.

Uploaded by

ahmadleo498
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 40

Discrete Structures

Lecture # 14

Dr. Hafiz Tayyab Javed

Department of Computer Science

FAST -- National University of Computer and


Emerging Sciences. CFD Campus
Material Partially Collected by Dr. Tayyab Javed
TREE

A tree is a connected graph that does not contain any


nontrivial circuit. (it is circuit-free).

A trivial circuit is one that consists of a single vertex.


EXAMPLE
EXAMPLES OF NON TREES
SOME SPECIAL
TREES
SOME SPECIAL
TREES
FOREST
PROPERTIES OF
TREES
PROPERTIES OF
TREES
EXERCISE

Explain why graphs (Tree) with the given specification


do not exist.
1. Tree with twelve vertices and fifteen edges.
2. Trees with five vertices and total degree 10.

SOLUTION:
SOLUTION

Tree with five vertices and total degree 10.

Any tree with five vertices will have 5 - 1 = 4 edges.

We are given total degree of graph is 10. So it must


have edges 10/2 = 5.

The two conditions contradict each other.


SOLUTION

Draw a graph with six vertices, five edges that is not a


tree.
SOLUTION:

First is not tree because it is not connected and also


has a circuit similarly for second.
TERMINAL AND INTERNAL
VERTEX

A vertex of degree ‘1’ in a tree is called terminal


vertex or a leaf (leaf has no children) and a vertex of
degree greater than ‘1’ in a tree is called an internal
vertex or a branch vertex.
EXAMPLE
ROOTED TREE
ROOTED TREE
ROOTED TREE

The root is an internal vertex unless it is the only vertex


in the graph, and in that case it will be a leaf.

Subtree

If a is a vertex in a tree, the subtree with a as its root is


the subgraph of the tree consisting of a and its
descendants and all edges incident to these
descendants.
EXAMPLE
EXAMPLE
EXAMPLE
EXERCISE
EXERCISE
EXERCISE
EXERCISE
EXERCISE
EXERCISE
EXERCISE
m-ary TREE
• A rooted tree is called m-ary tree if every internal
vertex has no more than m children.
• The tree is called full m-ary tree if every internal
vertex has exactly m children.
• An m-ary tree with m=2 is called a binary tree.
BINARY TREE

A binary tree is a rooted tree in which every internal


vertex has at most two children.

Every child in a binary tree is designated either a left


child or a right child.
FULL BINARY
TREE
EXAMPLE
THEOREM

A full m-ary tree with k internal vertices contains


n=mk+1 vertices.
THEOREM
EXERCISE
SOLUTION

2^4 =
EXERCISE
EXERCISE
EXAMPLE

Draw a binary tree with height 4 (level 3)


and having seven terminal vertices.
SOLUTION
Balanced Rooted
Tree

A rooted m-ary tree of height h is balanced if all leaves are


at levels h or h-1.

You might also like