CMSC 250 Homework 14 Fall 2001
Not ever due.

You may write things however you want since this is just for practice.

  1. Draw a directed graph representing the computer science courses you could take to complete a course of study in the department. (Start with $106-->114$, and end with 6 400-level courses. Check the department webpage for the courses and their prerequisites.)

  2. Draw a connected graph with 6 vertices numbered 1-6 such that the degree of vertex $n$ is numbered $n$. If you need more vertices to draw the graph, you may add them and give them any degrees you desire, but try to minimize the number of extra vertices you draw and the number of extra edges you have attached to those extra vertices.

  3. Draw a simple graph with no loops and vertices numbered 1-4 and a, such that vertices 1-4 have degree 1-4, and vertex a has degree 2.

  4. A K-partite graph is one in which a set of vertices $\{v_{k}\}$, $1\leq k\leq n$, is partitioned into $K$ subsets $\{V_{K}\}$, such that no edges join vertices in the same $V_{j}$. Draw an example of a connected 3-partite graph where the original set of vertices has 9 members, and each subset in the partition $V_{j}$ has 3 vertices.

  5. Let $R$ be a binary relation on the set $A=\{a,b,c,d,e,f,g,h\}$ defined by the following matrix:

    1 0 1 0 0 1 0 1
    0 1 1 0 1 0 1 0
    0 0 1 0 1 1 0 1
    1 0 0 1 1 1 0 0
    0 0 1 1 0 0 0 0
    0 1 1 0 0 1 0 1
    0 0 0 0 0 1 0 1
    1 0 1 0 1 0 1 0

    1. Draw $R$ as a directed graph.

    2. Find the in-degree and out-degree for each vertex.

    3. Remove the directions from the edges and redraw the graph as a multigraph.

    4. Find the degree of each of the vertices in the resulting graph.

    5. Collapse multiple edges between vertices and loops from vertices to themselves and redraw the graph.

    6. Find the degree of each of the vertices in the resulting graph.

  6. Construct a directed graph with 4 vertices such that the in-degree plus the out-degree of each vertex is 3, and the transitive closure of the relationship represented by the graph is the complete graph on 4 elements. (The in-degree of a vertex is the number of directed edges pointing into the vertex, and the out-degree is the number of directed edges leading out from that vertex.)

  7. Construct a connected undirected simple graph on 7 or 8 vertices such that every vertex has and odd degree of at least 3.

  8. Given the following graph G,

    \includegraphics {h14.eps}

    construct the following (if possible).

    1. An Euler circuit.

    2. A Hamiltonian circuit.

    3. A walk from 2 to 5 that is not a simple path.

    4. A closed walk from 1 to 1 passing through every vertex that is not a circuit.

    5. A circuit from 3 to 3 that is not a simple circuit.

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode h14q.tex

The translation was initiated by Deep Saraf on 2001-12-05

Deep Saraf
2001-12-05