Scribd
Upload
4 views5 pages

TutorialExercises - Graph

The document outlines tutorial exercises for a Computational Structures II course at Umm Al-Qura University, focusing on graphs and graph models. It includes various exercises related to graph terminology, special types of graphs, and methods for representing graphs, including adjacency lists and matrices. Additionally, it addresses concepts such as graph isomorphism and bipartite graphs, with recommended exercises for further practice.

Uploaded by

Hanadi Mardah
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views5 pages

TutorialExercises - Graph

The document outlines tutorial exercises for a Computational Structures II course at Umm Al-Qura University, focusing on graphs and graph models. It includes various exercises related to graph terminology, special types of graphs, and methods for representing graphs, including adjacency lists and matrices. Additionally, it addresses concepts such as graph isomorphism and bipartite graphs, with recommended exercises for further practice.

Uploaded by

Hanadi Mardah
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Umm Al-Qura University Software Engineering Department

Computers and Information Systems 1447 – 1st Semester


College Computational Structures II – SE3402

Tutorial Exercises
Week: 1-2
Main Topic: Graphs (Part 1)
Topics Covered: Graphs and Graph Models, Graph Terminology and Special Types of
Graphs, Representing Graphs and Graph Isomorphism.

Graphs and Graph Models [From Rosen's book - Exercises (Pages 649)]

3-9. For Exercises 3–9, determine whether the graph shown has directed or undirected edges,
whether it has multiple edges, and whether it has one or more loops. Use your answers to
determine the type of graph as in Table 1.

1
Graph Terminology and Special Types of Graphs [From Rosen's book - Exercises
(Pages 665)]

1-3. In Exercises 1–3 find the number of vertices, the number of edges, and the degree of
each vertex in the given undirected graph.

4. Find the sum of the degrees of the vertices of each graph in Exercises 1–3 and verify that it
equals twice the number of edges in the graph.

5. Can a simple graph exist with 15 vertices each of degree five?

7-9. In Exercises 7–9 determine the number of vertices and edges and find the in-degree and
out-degree of each vertex for the given directed multigraph.

2
10. For each of the graphs in Exercises 7–9 determine the sum of the in-degrees of the
vertices and the sum of the out-degrees of the vertices directly. Show that they are both equal
to the number of edges in the graph.

20. Draw these graphs.


a) K7 d) C7 e) W7

21-25. In Exercises 21–25 determine whether the graph is bipartite.

35. How many vertices do these graphs have?


a) Kn b) Cn c) Wn

Recommended Exercises: 26

3
56-57. In Exercises 56–57 find the union of the given pair of simple graphs. (Assume
edges with the same endpoints are the same.)

Recommended Exercises: 26

Representing Graphs and Graph Isomorphism [From Rosen's book - Exercises (Pages
675)]
1-4. In Exercises 1–4 use an adjacency list to represent the given graphs.

13-15. In Exercises 13–15 represent the given graph using an adjacency matrix.

4
17. In Exercises 16–18 draw an undirected graph represented by the given adjacency matrix.

35-37. In Exercises 34–44 determine whether the given pair of graphs is isomorphic. Exhibit
an isomorphism or provide a rigorous argument that none exists.

57. Are the simple graphs with the following adjacency matrices isomorphic?

Recommended Exercises: 5, 6, 7, 8, 9, 10, 11, 12, 16, 18, 19, 20, 21, 22, 24, 34, 38, 39, 40,
41, 42, 58
Hint: All odd-numbered exercises are solved at the end of the book.

You might also like