KEMBAR78
DM Tutorial 07 | PDF | Vertex (Graph Theory) | Theoretical Computer Science
Scribd
Upload
20 views5 pages

DM Tutorial 07

The document is a tutorial for a Discrete Mathematics course, focusing on various types of graphs and their properties. It includes tasks such as classifying graphs, creating graphs from representations, identifying vertices, determining degrees, and finding adjacency matrices. Additionally, it covers concepts like Hamilton circuits, trees, and spanning trees using depth-first and breadth-first search methods.

Uploaded by

upekshawaragoda1
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
20 views5 pages

DM Tutorial 07

The document is a tutorial for a Discrete Mathematics course, focusing on various types of graphs and their properties. It includes tasks such as classifying graphs, creating graphs from representations, identifying vertices, determining degrees, and finding adjacency matrices. Additionally, it covers concepts like Hamilton circuits, trees, and spanning trees using depth-first and breadth-first search methods.

Uploaded by

upekshawaragoda1
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
You are on page 1/ 5

Faculty of Computing

IT1160 – Discrete Mathematics


Year 1 Semester 2 (2025)
Tutorial 07

1. Classify the following graphs as Directed Graphs (Digraphs), Undirected Graphs,


Simple Graphs, or Multigraphs.

2. Create the following graphs based on the provided representations.

(a) A = G(p,q,r,s,(p,q),(p,s),(q,r),(p,r)) → Undirected Graph


(b) B = G(a,b,c,d,e,(a,c),(a,e), (b,a),(b,e),(b,c)(d,a),(c,e),(e,b)) → Directed Graph

3. Identify

(a) the adjacent vertices of vertex v2 and vertex v5.


(b) the incident vertices of edge e2 and edge e5
of the following graph.

1
4. Determine degree of each vertex of the following graphs.

5. What are the neighborhoods of the vertices in the graphs G & H.

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

7. Write down 2 circuits and their lengths from the following graph and state whether
they are simple circuits or not.

2
8. Find adjacency matrices of the following graphs.

Graph A Graph B Graph C Graph D

9. Draw the graphs with the given adjacency matrix.

Directed graphs: Undirected graphs:

(a) Graph A (c) Graph C

(b) Graph B (d) Graph D

3
10. In the following graphs, 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.

11. Which of these graphs are trees?

4
12. How many edges must be removed from a connected graph with n vertices and m
edges to produce a spanning tree?

13. In the following graphs, find a spanning tree for the graph shown by removing edges
in simple circuits.

14. Use depth-first search to produce a spanning tree for the given simple graph.
Choose “a” as the root of this spanning tree and assume that the vertices are
ordered alphabetically.

15. Use breadth-first search to produce a spanning tree for the simple graph in
Question 14.

You might also like