Tutorial 20, CPSC 331, Winter 2012

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  tests -  java -  references -  Mike Jacobson

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23

 Introduction to Graphs

About This Exercise

The objectives of this exercise are to ensure that you understand the definitions and basic properties of graphs, notably including (free) trees, as well as graph-theoretic terminology and notation, and the information about the representations of graphs in computer programs that has been presented during the first two lectures on graphs

Students should read through and try to solve the problems on this exercise before attending the tutorial.

Expected Background

This is based on the introductory lecture on graphs as well as lectures on trees and spanning trees that were presented in class.

Cormen, Leiserson, Rivest and Stein’s text, Introduction to Algorithms, include more information in Chapters 22–24, including proofs of the correctness and efficiency of several of the algorithms that will be considered; University of Calgary students can read this book online.

Warmup Problems — To Check That You Understand the Basics

It is expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course and attended the lectures in which graphs and free trees were introduced (reviewing the online notes, as needed).

These warmup problems will not be discussed in the tutorial; students who do have difficulty with them should contact the course instructor to get extra help.

  1. Give definitions of each of the following.

    1. an undirected graph
    2. a directed graph
    3. a weighted graph
    4. neighbours in an undirected graph
    5. a path in an undirected graph
    6. a simple path in an undirected graph
    7. a cycle in an undirected graph
    8. a simple cycle in an undirected graph
    9. the length of a path
    10. a connnected graph
    11. an acyclic graph
    12. a (free) tree
    13. a subgraph of an undirected graph
    14. an induced subgraph of an undirected graph
    15. a spanning tree of a connected undirected graph
    16. an adjacency-matrix representation of a graph
    17. an adjacency-list representation of a graph
    18. a predecessor subgraph corresponding to a vertex v in a graph G ant to a function π

  2. At this point you have access to several different references on graphs. Indeed, if you are taking Mathematics 271 at the same time as this course then two of the textbooks that you are using, this term, have sections on graphs. Compare (and contrast) the terminology that is used in the reference material that is now available to you — noting, for example, the way that the terms “path” and “cycle” are used in various references.

  3. Both free trees and rooted trees have now been defined and used in this course. How are they different? How are they similar?

  4. Decide whether each of the following undirected graphs is a free tree, and explain why (or why not).

    1.  

      Is This a Tree?

    2.  

      Is This a Tree?

    3.  

      Is This a Tree?

    4.  

      Is This a Tree?

    5.  

      Is This a Tree?

    6.  

      Is This a Tree?

       

  5. Which (if any) of the above graphs are spanning trees of the following graph?
     

    Another Graph

     

  6. When is an “adjacency-matrix representation” a better choice than an “adjacency-list representation?” When is an “adjacency-list representation” a better choice than an “adjacency-matrix representation?”

  7. Draw adjacency-matrix and adjacency-list representations for each of the following graphs.

    1.  

      An Undirected Graph

    2.  

      A Directed Graph

    3.  

      A Weighted Graph

To Be Discussed in the Tutorial

  1. Describe how to modify each of the adjacency-matrix and adjacency-list representatives, in order to allow new vertices to be added more efficiently.

    Try to produce representations that resemble the ones that have been described but also have behaviour similar to array-based representations of stacks and queues: While the occasional operation might be expensive the total cost of a collection of operations (that add new vertices) should be linear in the number of operations considered.

    You should find that it is reasonably easy to do this for one of these two representations, but probably not for the other. Why?

  2. Consider an undirected graph G = (V, E) where V = { 0, 1, 2, 3, 4, 5, 6 } and where (i, j) ∈ E for all i and j such that i, j ∈ V and i ≠ j.

    Let s = 0 and consider a function π : V → V ∪ { NIL } such that

    π(0) = NIL,  π(1) = 0,  π(2) = 0,  π(3) = 2,  π(4) = 3,  π(5) = 3,  and  π(6) = 3.

    1. Draw the predecessor subgraph of G for the above vertex s and function π.

    2. Sketch a proof, using on the number of steps used to construct a predecessor subgraph (which is the same as the number of edges included in it), that a predecessor subgraph is always a connected graph. (One way to do this is to start by arguing that there is a part from every vertex to the start vertex, s.

    3. What additional properties (if any) are needed to establish that a given predecessor subgraph is a tree? Do these always hold, or do you need to do something to check for them?

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial20.html