2023/10/9 16:32
COMP9024 23T3 - Week 4 Problem Set
https://cgi.cse.unsw.edu.au/~cs9024/23T3/probs/prob4/index.php
1/8
COMP9024 23T3
Dr. Aditya Joshi
Week 4 Problem Set
Graph Data Structures and Graph
Search
[Show with no answers] [Show with all answers]
1. (Graph fundamentals)
For the graph
give examples of the smallest (but not of size/length 0) and largest of each of the following:
a. simple path
b. cycle
c. spanning tree
d. vertex degree
e. clique
[show answer]
2. (Graph properties)
a. Write pseudocode for computing
the degree of each vertex
all 3-cliques (i.e. cliques of 3 nodes, "triangles")
and the density
of an undirected graph g with n vertices.
Your methods should be representation-independent; the only function you should use is to check if
two vertices v,w
∈
{0,…n-1} are adjacent in g.
The density is the fraction of edges present over all possible edges, which, for an undirected graph
with edges and vertices, is defined as .
b. Determine the asymptotic complexity of your three algorithms. Assume that the adjacency check is
performed in constant time, O(1).
c. Implement your algorithms in a program graphAnalyser.c that
1. builds a graph from user input:
first, the user is prompted for the number of vertices
|
E
| |
V
|
2|
E
|
|
V
|(|
V
| − 1)
