MA 111-001 & 002
Practice for Exam 2

Use the following three graphs for questions 1-10:

Exam 2 Review Guide_IMG1

1.  Which of these graphs have an Euler Circuit?

a. Graph 1       b. Graph 2      c. Graph 3      d. Graphs 1&2      e. Graphs 2&3      f.  Graphs 1&3      g. all      h. none

2.   One Euler Circuit appearing in Graph ______ is (begin with vertex A and list all vertices visited in
proper order)_______________________________.  If there is no Euler Circuit in any of the graphs,
write None.

3.   Which of these graphs have an Euler Path?

a. Graph 1       b. Graph 2      c. Graph 3      d. Graphs 1&2      e. Graphs 2&3      f.  Graphs 1&3      g. all      h. none

4.   One Euler Path appearing in Graph ______ is (begin with vertex A and list all vertices visited in
proper order)_______________________________.  If there is no Euler Path in any of the graphs,
write None.

5.   Which of these graphs have a Hamilton Circuit?
a. Graph 1 b. Graph 2 c. Graph 3 d. Graphs 1&2 e. Graphs 2&3 f. Graphs 1&3 g. all h. none

6.   One Hamilton Circuit appearing in Graph ______ is (begin with vertex A and list all vertices visited in
proper order)_______________________________.  If there is no Hamilton Circuit in any of the
graphs, write None.

7.   Which of these graphs have a Hamilton Path?

a. Graph 1 b. Graph 2 c. Graph 3 d. Graphs 1&2 e. Graphs 2&3 f. Graphs 1&3 g. all h. none

8.   One Hamilton Path appearing in Graph ______ is (begin with vertex A and list all vertices visited in
proper order)_______________________________.  If there is no Hamiliton Path in any of the
graphs, write None.

9.   Find a circuit on Graph 3 that begins at vertex A and contains vertex C, but not vertex E.  Is this an
Euler Circuit?

10. The vertex set of Graph 2 is __________________________________.

The edge set of Graph 2 is _________________________________________.

11. Find an optimal Eulerization for the graph below.  If this were the graph representation of a
neighborhood, in which a security guard needs to walk each block at least once, beginning and
ending at the labeled vertex, how many total blocks must he walk?

Exam 2 Review Guide_IMG2

12.  Define a Complete Graph.  Draw the graph K5.  How many Hamilton Circuits are there in K5?

13.  Fill in the chart:

Vertex/Edge Set: Number of and Degree of Vertices Drawing of Graph(Place an * by drawing if there is more than one graph with the given description) Contains:A)Euler Circuit

 

B)Euler Path

C)Both

D)Neither

E)Not Enough Info

V={dog, cat, fish, plant, man,
bear, pig, car}E={Edges connect vertices if one
might eat the other.}
Ten verticesFour having degree 2

 

Two having degree 1

Four having degree 3

V={A,B,C,D,E,F,G}E={AB, AC, AD, AG, BA, BB, CD,
DG, EE, FG}
Six vertices, each having degree 2.
Exam 2 Review Guide_IMG3

14. Find an optimal coloring for the graph below.  How many colors do you need?

Exam 2 Review Guide_IMG3

15. There may be a bonus question involving a Sudoku puzzle.  Here are some practice puzzles:

Beginner

Exam 2 Review Guide_IMG6

Easy

Exam 2 Review Guide_IMG4

Medium

Exam 2 Review Guide_IMG5

Diabolical (This is just for fun, for those of you who weren’t challenged enough in class).

Exam 2 Review Guide_IMG7

 

MA 111-001 & 002
Practice for Exam 2

Use the following three graphs for questions 1-10:

Exam 2 Review Guide_IMG1

1.  Which of these graphs have an Euler Circuit?

c. Graph 3

2.   One Euler Circuit appearing in Graph 3 is (begin with vertex A and list all vertices visited in
proper order) ABCEFGAFCDA.  If there is no Euler Circuit in any of the graphs,
write None.

3.   Which of these graphs have an Euler Path?

a. Graph 1

4.   One Euler Path appearing in Graph 1 is (list all vertices visited in proper order) DAEBCABDC.  If there is no Euler Path in any of the graphs, write None.

5.   Which of these graphs have a Hamilton Circuit?
d. Graphs 1&2

6.   One Hamilton Circuit appearing in Graph 1 is (begin with vertex A and list all vertices visited in
proper order) AEBCDA.  If there is no Hamilton Circuit in any of the graphs, write None.

7.   Which of these graphs have a Hamilton Path?

g. all

8.   One Hamilton Path appearing in Graph 1 is (begin with vertex A and list all vertices visited in
proper order) AEBCD.  If there is no Hamiliton Path in any of the graphs, write None.

9.   Find a circuit on Graph 3 that begins at vertex A and contains vertex C, but not vertex E.  Is this an
Euler Circuit? ABCDA – No, it is not Euler because it doesn’t contain all of the edges in the graph.

10. The vertex set of Graph 2 is {A,B,C,D,E,F,G}.

The edge set of Graph 2 is {AB, AD, AF, AG, BC, BE, BD, BG, CD, CE, CF, EF, FG}.

11. Find an optimal Eulerization for the graph below.  If this were the graph representation of a
neighborhood, in which a security guard needs to walk each block at least once, beginning and
ending at the labeled vertex, how many total blocks must he walk?  Add double edges until all odd vertices are even.  I did it with 40 total edges.  Can you find a way with less?

 

12.  Define a Complete Graph.  Draw the graph K5.  How many Hamilton Circuits are there in K22?  A complete graph is one in which each vertex shares an edge with every other vertex.  K5 is the complete graph with 5 vertices.  It is usually drawn as a pentagon with a star inside.  There are (22-1)!=21*20*19*…*3*2*1 Hamilton Circuits in K22.

13.  Fill in the chart:

Vertex/Edge Set: Number of and Degree of Vertices Drawing of Graph(Place an * by drawing if there is more than one graph with the given description) Contains:A)Euler Circuit

B)Euler Path

C)Both

D)Neither

E)Not Enough Info

V={dog, cat, fish, plant, man,
bear, pig, car}E={Edges connect vertices if one
might eat the other.}
Varies Varies E
Varies Ten verticesFour having degree 2

Two having degree 1

Four having degree 3

Exam 2 Review Guide_IMG8 D
V={A,B,C,D,E,F,G}E={AB, AC, AD, AG, BA, BB, CD,
DG, EE, FG}
7 vertices

1 with degree 5

1 with degree 4

2 with degree 3

2 with degree 2

1 with degree 1

Exam 2 Review Guide_IMG9 D
Varies Six vertices, each having degree 2. Exam 2 Review Guide_IMG10 E
Vertex Set {A, B, C, D, E, F, G}

Edge Set {AD, BC, BG, BD, CD, CE, DE, DF, DG, EG, FG}

7 vertices

Count degrees.

 

Exam 2 Review Guide_IMG3 D

14. Find an optimal coloring for the graph below.  How many colors do you need? 3 colors

Exam 2 Review Guide_IMG11

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: