Scribd
Upload
8 views4 pages

TutorialExercises - Graph

The document outlines tutorial exercises for a Software Engineering course at Umm Al-Qura University, focusing on graphs, connectivity, Euler and Hamilton paths. It includes specific exercises for determining paths, connected components, and applying various algorithms such as DFS, BFS, Dijkstra, and Floyd Warshall. The exercises are sourced from Rosen's book and are designed to enhance understanding of graph theory concepts.

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
8 views4 pages

TutorialExercises - Graph

The document outlines tutorial exercises for a Software Engineering course at Umm Al-Qura University, focusing on graphs, connectivity, Euler and Hamilton paths. It includes specific exercises for determining paths, connected components, and applying various algorithms such as DFS, BFS, Dijkstra, and Floyd Warshall. The exercises are sourced from Rosen's book and are designed to enhance understanding of graph theory concepts.

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: 2
Main Topic: Graphs (Part 2)
Topics Covered: Connectivity, Euler and Hamilton Paths.

Connectivity [From Rosen's book - Exercises (Pages 689)]

1. Do each of these lists of vertices form a path in the following graph? Which paths are
simple? Which are circuits? What are the lengths of those that are paths?

a) a, e, b, c, b b) a, e, a, d, b, c, a
c) e, b, a, d, b, e d) c, b, d, a, e, c

3-5 In Exercises 3–5 determine whether the given graph is connected.

6. How many connected components does each of the graphs in Exercises 3–5 have? For each
graph find each of its connected components.

1
11. Determine whether each of these graphs is strongly connected and if not, whether it is
weakly connected

Recommended Exercises: 2, 14

Euler and Hamilton Paths [From Rosen's book - Exercises (Pages 703)]

1-5. In Exercises 1–8 determine whether the given graph has an Euler circuit. Construct such
a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler
path and construct such a path if one exists.

2
26. For which values of n do these graphs have an Euler circuit?
a) Kn
b) Cn
c) Wn

27. For which values of n do the graphs in Exercise 26 have an Euler path but no Euler
circuit?

28. For which values of m and n does the complete bipartite graph Km,n have an
a) Euler circuit
b) Euler Path

30-33. In Exercises 30–36 determine whether the given graph has a Hamilton circuit. If it
does, find such a circuit. If it does not, give an argument to show why no such circuit exists.

37-40. Does the graph in Exercise 30-33 so, find such a path. If it does show why no such
path exists.

3
For DFS, BFS, Dijkstra, and Floyd Warshall algorithms.
1- Apply DFS and BFS algorithms to find the path from source vertex (A) to all other
vertices.

2- Apply Dijkstra’s algorithm to find the shortest path from source vertex (a) to all
other vertices.

3- Apply Floyd Warshall algorithm to find the shortest paths for all vertices.

Hint: All odd-numbered exercises are solved at the end of the book.

You might also like