CSC 230 -- Discrete Structures

Graph Practice

  1. Four of the graphs below are isomorphic to graph A. One is not. Which of the graphs is NOT the same? What is different about it?

2. A non directed multigraph has vertex set V = { 1, 2, 3, 4} andedge set E = { (1,1), (1,2), (1,4), (2,3), (3,4), (3,4) }.

a) Draw the graph. b) Give its adjacency matrix.

1 2
3 4 /

c) Create M2 and use it the determine how many paths of length 2 there are between vertices 1 and 3.

M M M2

/ X / / = / / There are _____ paths of length 2 between vertices 1 and 3.

d) Every graph can be thought of as a relation with the underlying setequal to the set of vertices and having an (i,j) pair if and only if there is an edge between i and j. Give the edge set that represents the transitive closure of the relation corresponding to the graph you drew in part ‘a’. What is the significance of this new relation?

3. Use the graph to the right to answer the following questions. /
a)Illustrate the method necessary to determine the shortest path from vertex 'a' to vertex 'c'. List this path and give its length. / b) Find the minimum “cost” spanning tree for the same graph.

4. Is it possible to walk in and out of each room in the house to the right so that each door of the house is used EXACTLY once? Why or why not? The short lines represent doors. /
5. Draw a minimum cost spanning tree for
this graph.

6.Model each of the following problems with an appropriate graph and indicate what FEATURE you would look for in the graph to solve the problem.

a) Five Computer Science teachers each know a variety of programming languages (1 to 4 each). A section each of C++, Java, VisualBASIC, Lisp, and Perl must be taught. If they all meet at the same time (and thus the SAME teacher cannot teach more than one of the classes), can all 5 classes be staffed by the 5 teachers?

b)Show that 4 different colors are needed to color the map shown if no 2 adjacent regions can be of the same color. /

c) Ten mothers decide to form a babysitting coop. Each has certain times she needs a sitter and has certain times she is available to offer childcare. Can a schedule be worked out so each woman can babysit for one of the others and can have one of the others babysit for her once a week?

d) What is the minimum number of miles a traveling salesman must travel to visit each town on his route and return home?

e)What is the minimum number of miles of road that must be plowed to allow all towns in a county to be connected in a big snowstorm?

f) Is there is route that will allow a road inspector to inspect all the roads in his district without having to traverseany twice?

Twelve students from different countries are gathered in a Youth Hostel. Each speaks certain languages.

g) Can every student communicate directly with every other one?

h) Can every student communicate with every other student if one or more of the others act as translators?

i) Can every student communicate with each of the others using AT MOST one translator?

In Graphs A, B, C, D, AND F, highlight the edge set that produces a minimum cost spanning tree (MCST) and give its “cost”

In Graph E, hightlight the edge set that gives the lowest cost path from S to V6 and give its “cost”.

A.
/ B.

C.
/ D.

E.
/ F.