CLO4- Graphs Worksheet 1
1. Graph models: The table below represents the number of flights from a city to another.
Starting City Destination City No of flights
Boston Newark 4
Newark Boston 2
Newark Detroit 1
Detroit Newark 2
Newark Miami 3
Miami Newark 2
Newark Washington 3
Washington Newark 2
Washington Miami 1
Draw graph models for each of the following questions that satisfy the specific requirements.
State also the type of graph drawn. [Refer to your PPT on Graphs for the different types of
graphs]
a) an edge between vertices representing cities that have a flight between them (in either
direction).
b) an edge between vertices representing cities for each flight that operates between
them (in either direction).
CLO4- Graphs Worksheet 1-Solutions
c) an edge between vertices representing cities for each flight that operates between
them (in either direction), plus a loop for a special sightseeing trip that takes off and
lands in Miami.
d) an edge from a vertex representing a city where a flight starts to the vertex
representing the city where it ends.
e) an edge for each flight from a vertex representing a city where the flight begins to the
vertex representing the city where the flight ends.
CIS 2203 Page 2 of 7
CLO4- Graphs Worksheet 1-Solutions
2. In Exercises A–B, find the number of vertices, the number of edges, and the degree of each vertex
in the given undirected graph. Identify all isolated and pendant vertices.
A.
Question# No. of No of degree pendant isolated
vertices edges
A 6 6 Deg(a)= deg(e) = 2 c D
Deg(f) = 3 deg(b) = 4
B 5 13 Deg(a) =deg(d) =5 none none
deg(b) =deg (c) =6
deg(e) =3
B.
C.
3. State the types of graphs in the following figures.
a. Simple Graph
CIS 2203 Page 3 of 7
CLO4- Graphs Worksheet 1-Solutions
b. Multigraph
c. Pseudograph
d. Directed Multigraph
4. What are the degrees and neighborhoods of the vertices in the graphs G and H?
Graph G: deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d ) = 1, deg(e) = 3, deg(g) = 0.
N(a) = {b, f }, N(b) = {a, c, e, f }, N(c) = {b, d, e, f }, N(d) = {c}, N(e) = {b, c , f }, N(f) = {a, b, c, e},
N(g) = ∅ .
Graph H: deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5.
N(a) = {b, d, e}, N(b) = {a, b, c, d, e}, N(c) = {b}, N(d) = {a, b, e}, N(e) = {a, b ,d}.
CIS 2203 Page 4 of 7
CLO4- Graphs Worksheet 1-Solutions
5. Use an adjacency matrix to represent the pseudograph shown in the figure.
Solution:
6. Represent the pseudograph shown in the figure using an incidence matrix.
Solution:
CIS 2203 Page 5 of 7
CLO4- Graphs Worksheet 1-Solutions
7. Paths: Answer the following questions.
a. Does each of these lists of vertices form a path in the following graph?
b. Which paths are simple?
c. Which are circuits?
d. What are the lengths of those that are paths?
i. a, e, b, c, b
ii. a, e, a, d, b, c, a
iii. e, b, a, d, b, e
iv. c, b, d, a, e, c
Solution:
1. a. Yes b. Not simple path c. Not a circuit d. 4
2. a. Not a path
3. a. Not a path
4. a. Yes b. Not a simple path c. It is a circuit d. 5
8. Find a shortest path in the following figure from a to z. (Use Dijkstra’s algorithm ).
Solution:
Shortest path is : a, b, e, d, z;
Length is : 8
CIS 2203 Page 6 of 7
CLO4- Graphs Worksheet 1-Solutions
9. Find the chromatic number of the following graph.
Solution:
The chromatic number is at least 3.
CIS 2203 Page 7 of 7
