Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    Assignment 2 (Online Version)

    Uploaded by

    Alan Ling
    This document contains an assignment on discrete mathematics. It includes 5 questions on graphs, trees, and binary trees. Question 1 involves identifying properties of graphs such as whether they contain an Euler path/circuit or neither. Question 2 asks to identify graph-related terms based on descriptions. Question 3 provides a weighted graph and asks to find the minimum spanning tree using Prim's algorithm. Question 4 provides a rooted tree and asks questions about its structure like listing leaves and descendants. Question 5 defines spanning trees, minimal spanning trees, and binary trees, then asks about tree traversals and to perform the three types of traversals on a given binary search tree.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd

    Assignment 2 (Online Version)

    Uploaded by

    Alan Ling
    19 views4 pages
    This document contains an assignment on discrete mathematics. It includes 5 questions on graphs, trees, and binary trees. Question 1 involves identifying properties of graphs such as whether they contain an Euler path/circuit or neither. Question 2 asks to identify graph-related terms based on descriptions. Question 3 provides a weighted graph and asks to find the minimum spanning tree using Prim's algorithm. Question 4 provides a rooted tree and asks questions about its structure like listing leaves and descendants. Question 5 defines spanning trees, minimal spanning trees, and binary trees, then asks about tree traversals and to perform the three types of traversals on a given binary search tree.

    Original Title

    Assignment 2 (online version)

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains an assignment on discrete mathematics. It includes 5 questions on graphs, trees, and binary trees. Question 1 involves identifying properties of graphs such as whether they contain an Euler path/circuit or neither. Question 2 asks to identify graph-related terms based on descriptions. Question 3 provides a weighted graph and asks to find the minimum spanning tree using Prim's algorithm. Question 4 provides a rooted tree and asks questions about its structure like listing leaves and descendants. Question 5 defines spanning trees, minimal spanning trees, and binary trees, then asks about tree traversals and to perform the three types of traversals on a given binary search tree.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    19 views4 pages

    Assignment 2 (Online Version)

    Uploaded by

    Alan Ling
    This document contains an assignment on discrete mathematics. It includes 5 questions on graphs, trees, and binary trees. Question 1 involves identifying properties of graphs such as whether they contain an Euler path/circuit or neither. Question 2 asks to identify graph-related terms based on descriptions. Question 3 provides a weighted graph and asks to find the minimum spanning tree using Prim's algorithm. Question 4 provides a rooted tree and asks questions about its structure like listing leaves and descendants. Question 5 defines spanning trees, minimal spanning trees, and binary trees, then asks about tree traversals and to perform the three types of traversals on a given binary search tree.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 4

    POLITEKNIK KUCHING SARAWAK

    JABATAN MATEMATIK, SAINS & KOMPUTER


    KM22, JLN MATANG, 93050 KUCHING

    B2009 DISCRETE MATHEMATICS


    ASSIGNMENT 2

    Question 1
    Graphs

    (a) Based on the graphs below, complete the table below. Do they contain an Euler Path,
    Euler Circuit or neither? (9 marks)
    Graph 1 Graph 2 Graph 3

    Graph Number of Odd Number of Even Euler Path / Euler Circuit /


    Degree Degree Neither
    1
    2
    3

    Question 2
    Graphs

    Give the name of the item to the description relating to a given graph G. (9 marks)
    (a) Any edge which starts and ends at the same vertex.
    (b) Any edge which disconnects the graph when deleted.
    (c) Any line joining two vertices of the graph.
    (d) The number of edges which meet at a given vertex.
    (e) Two edges of a graph are connected by a common vertex.
    (f) Two vertices joined by a single edge.
    (g) Any sequence of adjacent edges which appear only once.
    (h) A sequene of adjacent vertices which start and end at the same place.
    (i) A graph where two vertices are joined by a graph.
    Question 3
    Trees

    Use Prim’s algorithm to find a minimum spanning tree in the following weighted graph.
    (12
    marks)

    B 5 D
    2 2

    A 6 3 1 Z

    3 2 4
    C E

    Question 4
    Trees

    For the following questions, consider the rooted tree (T, v0) shown below. (10 marks)

    V0

    V3

    V1

    V5 V2 V9
    V4

    V11 V12 V6 V7 V8 V10


    V14
    V15 V13

    V16

    (a) List all level 1-vertices.


    (b) List all leaves.
    (c) What are the siblings of v2?
    (d) What are the descendants of v8?
    (e) Compute the tree T(V3).
    (f) What is the height of (T, v0)?

    Question 5
    Trees

    (a) Define
    i. Spanning tree (2 marks)
    ii. A minimal spanning tree (1 mark)
    iii. A binary tree. (2 marks)
    (b) Explain Tree Traversal in Computer Science context. (2 marks)
    (c) Based on the following binary search tree, find the tree traversals sequence of
    i. Pre-order (1 mark)
    ii. In-order (1 mark)
    iii. Post-order (1 mark)

    You might also like