Graph Theory Chapter 7: Trees
40 Questions
2 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

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
  • -1
  • 2

    • What is the height of a rooted tree?

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

    What is a balanced tree?

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

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

    <p>Root, Left, Right</p> Signup and view all the answers

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

    <p>Left, Root, Right</p> Signup and view all the answers

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

    <p>Left, Right, Root</p> Signup and view all the answers

    What is a characteristic of a tree?

    <p>A connected simple undirected graph with no simple circuits</p> Signup and view all the answers

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

    <p>Forest</p> Signup and view all the answers

    What is a rooted tree?

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

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

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

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

    <p>Left, Right, Root</p> Signup and view all the answers

    What is a child in a rooted tree?

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

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

    <p>Siblings</p> Signup and view all the answers

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

    <p>Infix Notation</p> Signup and view all the answers

    What is another name for Prefix Notation?

    <p>Polish Notation</p> Signup and view all the answers

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

    <p>Root</p> Signup and view all the answers

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

    <p>Forest</p> Signup and view all the answers

    In which notation is the operator written after the operands?

    <p>Postfix Notation</p> Signup and view all the answers

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

    <p>It is difficult and costly in terms of time and space</p> Signup and view all the answers

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

    <p>Operator Operand Operand</p> Signup and view all the answers

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

    <p>a b - c +</p> Signup and view all the answers

    How many notations can an arithmetic expression be written in?

    <p>3</p> Signup and view all the answers

    Which notation requires a fully parenthesized expression to remove ambiguity?

    <p>Infix notation</p> 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)?

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

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

    <p>Pre-order</p> Signup and view all the answers

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

    <p>Post-order</p> Signup and view all the answers

    What is the notation where operators precede their operands?

    <p>Prefix notation</p> Signup and view all the answers

    What is the notation where operators follow their operands?

    <p>Postfix notation</p> Signup and view all the answers

    What is an ancestor of a vertex in a tree?

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

    Which notation is also known as Polish notation?

    <p>Prefix notation</p> Signup and view all the answers

    What is a leaf in a tree?

    <p>A vertex with no children</p> Signup and view all the answers

    What is a subtree in a tree?

    <p>A subgraph consisting of a vertex and its descendants</p> Signup and view all the answers

    What is the level of a vertex in a tree?

    <p>The length of the unique path from the root to the vertex</p> Signup and view all the answers

    What is a full m-ary tree?

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

    What is an ordered rooted tree?

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

    What is the height of a tree?

    <p>The maximum level of any vertex in the tree</p> Signup and view all the answers

    What is true about a tree with n vertices?

    <p>It has n-1 edges</p> 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.

    Quiz Team

    Description

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

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser