Graph Theory Chapter 7: Trees

Podcast Beta

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the number of vertices in a full m-ary tree with I internal vertices and L leaves?

I + L - 1

I × L - 1

m × I + 1 (correct)

m × I - L

What is the formula for the number of internal vertices in a full m-ary tree with n vertices?

I = (n - 1) × m

I = (n + 1) / m

I = (n + 1) × m

I = (n - 1) / m (correct)

What is the level of the root in a rooted tree?

0 (correct)

-1

What is the height of a rooted tree?

The length of the longest path from the root to any vertex Signup and view all the answers

What is a balanced tree?

A tree with all leaves at levels h or h - 1 Signup and view all the answers

What is the order of visiting vertices in a pre-order traversal?

Root, Left, Right Signup and view all the answers

What is the order of visiting vertices in an in-order traversal?

Left, Root, Right Signup and view all the answers

What is the order of visiting vertices in a post-order traversal?

Left, Right, Root Signup and view all the answers

What is a characteristic of a tree?

A connected simple undirected graph with no simple circuits Signup and view all the answers

What is the name of a graph with no simple circuits?

Forest Signup and view all the answers

What is a rooted tree?

A tree with one node designated as the root and every edge directed away from the root Signup and view all the answers

What is the definition of a parent in a rooted tree?

A vertex u such that there is a directed edge from u to v Signup and view all the answers

What is the order of traversal in Post-order notation?

Left, Right, Root Signup and view all the answers

What is a child in a rooted tree?

A vertex v such that there is a directed edge from u to v Signup and view all the answers

What is the term for vertices with the same parent in a rooted tree?

Siblings Signup and view all the answers

Which notation is easy for humans to read, write, and speak in?

Infix Notation Signup and view all the answers

What is another name for Prefix Notation?

Polish Notation Signup and view all the answers

What is the term for a vertex with in-degree 0 in a rooted tree?

Root Signup and view all the answers

What is the term for a graph that is not connected?

Forest Signup and view all the answers

In which notation is the operator written after the operands?

Postfix Notation Signup and view all the answers

What is the difficulty with using Infix Notation in computing devices?

It is difficult and costly in terms of time and space Signup and view all the answers

What is the order of operands and operator in Prefix Notation?

Operator Operand Operand Signup and view all the answers

What is the equivalent of 'a - b + c' in Infix Notation?

a b - c + Signup and view all the answers

How many notations can an arithmetic expression be written in?

3 Signup and view all the answers

Which notation requires a fully parenthesized expression to remove ambiguity?

Infix notation Signup and view all the answers

What is the correct prefix notation for the expression ((x + y)^2) + ((x – 4) / 3)?

<ul> <li>^ x y 2 / – x 4 3</li> </ul> Signup and view all the answers

What is the correct postfix notation for the expression ((x + y)^2) + ((x – 4) / 3)?

x y + 2 ^ x 4 – 3 / + Signup and view all the answers

What type of traversal is used to evaluate a prefix expression?

Pre-order Signup and view all the answers

What type of traversal is used to evaluate a postfix expression?

Post-order Signup and view all the answers

What is the notation where operators precede their operands?

Prefix notation Signup and view all the answers

What is the notation where operators follow their operands?

Postfix notation Signup and view all the answers

What is an ancestor of a vertex in a tree?

A vertex in the path from the root to the vertex, excluding the vertex itself Signup and view all the answers

Which notation is also known as Polish notation?

Prefix notation Signup and view all the answers

What is a leaf in a tree?

A vertex with no children Signup and view all the answers

What is a subtree in a tree?

A subgraph consisting of a vertex and its descendants Signup and view all the answers

What is the level of a vertex in a tree?

The length of the unique path from the root to the vertex Signup and view all the answers

What is a full m-ary tree?

A tree in which every internal vertex has exactly m children Signup and view all the answers

What is an ordered rooted tree?

A rooted tree in which the children of each internal node are ordered Signup and view all the answers

What is the height of a tree?

The maximum level of any vertex in the tree Signup and view all the answers

What is true about a tree with n vertices?

It has n-1 edges Signup and view all the answers

Study Notes

Trees

A tree is a connected simple undirected graph with no simple circuits.
Properties of a tree:
- Unique simple path between any two vertices.
- No loops.
- No multiple edges.

Forest

An undirected graph without simple circuits is called a forest.
A forest is a set of trees having disjoint sets of nodes.

Rooted (Directed) Trees

A rooted tree is a tree in which one node has been designated the root and every edge is directed away from the root.
Key terms:
- Root: Vertex with in-degree 0.
- Parent: Vertex u is a parent, such that there is a directed edge from u to v.
- Child: If u is a parent of v, then v is a child of u.
- Siblings: Vertices with the same parents.
- Ancestors: Vertices in the path from the root to vertex v, excluding v itself, including the root.
- Descendents: All vertices that have v as ancestors.
- Leaf: Vertex with no children.
- Internal node: Vertex that has children.
- Subtree: Subgraph consisting of v and its descendents and their incident edges.

Levels and Height

Level of v is the length of the unique path from the root to v.
Height is the maximum of the vertices' levels.

m-ary Trees

A rooted tree is called m-ary if every internal vertex has no more than m children.
A full m-ary tree is a tree where every internal vertex has exactly m children.
A 2-ary tree is called a binary tree.

Ordered Rooted Trees

A rooted tree where the children of each internal node are ordered.
In ordered binary trees, we can define left child, right child, left subtree, and right subtree.
For m-ary trees with m > 2, we can use terms like “leftmost”, “rightmost”, etc.

Properties of Trees

A tree with n vertices has n - 1 edges.
A full m-ary tree with I internal vertices and L leaves contains:
- n = m × I + 1 vertices.
- n = I + L vertices.

Balanced Trees

A rooted m-ary tree of height h is balanced if all leaves are at levels h or h - 1.

Tree Traversal

Traversal algorithms:
- Pre-order traversal.
- In-order traversal.
- Post-order traversal.
Tree traversals:
- Pre-order: Root, Left, Right.
- In-order: Left, Root, Right.
- Post-order: Left, Right, Root.

Infix, Prefix, and Postfix Notation

Infix notation: Operators are used in-between operands.
Prefix notation (Polish notation): Operator is prefixed to operands.
Postfix notation (Reverse-Polish notation): Operator is postfixed to operands.
Notations can be used to represent mathematical expressions.
Examples:
- Infix: a + b.
- Prefix: +ab.
- Postfix: ab+.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Learn about the properties and examples of trees in graph theory, including connected simple undirected graphs with no simple circuits.