Scribd
Upload
15 views20 pages

Trees

A tree is a connected, undirected graph with no circuits, allowing a unique path between vertices. Rooted trees have a designated root with directed edges, and properties include that a tree with n vertices has n-1 edges. Spanning trees include all vertices of a graph and Kruskal's algorithm helps find the minimum spanning tree for cost-effective connectivity.

Uploaded by

janssenmarana18
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
15 views20 pages

Trees

A tree is a connected, undirected graph with no circuits, allowing a unique path between vertices. Rooted trees have a designated root with directed edges, and properties include that a tree with n vertices has n-1 edges. Spanning trees include all vertices of a graph and Kruskal's algorithm helps find the minimum spanning tree for cost-effective connectivity.

Uploaded by

janssenmarana18
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/ 20

TREES

TREES

A tree is a simple, connected, undirected graph


with no simple circuits. This means there is a unique
simple path between any two of its vertices.
TREES

A rooted tree is a tree in which one vertex has been


designed as the root and every edge is directed away
from the root.
Height = 3 Root node
a
level
internal vertex parent of g 0
b c
1

d e f g
2
leaf
siblings
h i
3
subtree
___ is the parent of b,
___ is the child of a,
_________are siblings,
_______ are ancestors of f
_______ are descendants of b
_______ are leaves of the tree a,
______ are internal vertices of the tree
Look for subtree
TREES
M-ary tree
if every vertex has no more than m children. The
tree is called a full m-ary tree if every internal vertex
has exactly m-children.
Properties of TREES V E
Theorem: 0
A tree n 1
vertices has n-1 2
edges
3
n n-1
TREES
Let 𝑻𝟏 = 𝑽𝟏 , 𝑬𝟏 𝒂𝒏𝒅 𝑻𝟐 = 𝑽𝟐 , 𝑬𝟐 be two
trees with 𝑬𝟏 = 𝟏𝟏 and 𝑽𝟐 = 𝟐 𝑽𝟏 . Find
a. 𝑽𝟏
b. 𝑽𝟐
c. 𝑬𝟐
Determine if the following graphs are trees?
a. 𝐺 = 𝑉, 𝐸
𝑉 = 𝑎, 𝑏, 𝑐, 𝑑, 𝑒
𝐸 = 𝑎, 𝑏 , 𝑎, 𝑒 , 𝑏, 𝑐 , 𝑐, 𝑑 , (𝑑, 𝑒)

b. 𝐺 = 𝑉, 𝐸
𝑉 = 𝑎, 𝑏, 𝑐, 𝑑, 𝑒
𝐸 = 𝑎, 𝑏 , 𝑏, 𝑐 , 𝑐, 𝑑 , (𝑑, 𝑒)
SPANNING TREES
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
Kruskal's algorithm is a minimum spanning tree
algorithm that takes a graph as input and finds
the subset of the edges of that graph
A company requires reliable internet and
phone connectivity between their five
offices (named A, B, C, D, and E for
simplicity) in Taguig, so they decide to
lease dedicated lines from the phone
company. The phone company will
charge for each link made. The costs, in
thousands of dollars per year, are shown
in the graph. Find the minimum cost
spanning tree.
The Edges of the
Edge Weight
Graph Weight
Source Vertex Destination Vertex

E F 2
F D 2 A C
B C 3
C F 3 D
B
C D 4
B F 5
B D 6 E F
A B 7
A C 8

You might also like