Description
Question 1
b c
a e d
Figure 1: Graph G in Q1.
Consider the graph G in Figure 1 to answer the following questions. Explain all the answers.
a) What is the sum of degrees of all nodes of G?
b) What is the number of non-zero entries in the adjacency matrix representation of G?
c) What is the number of zero entries in the incidence matrix representation of G?
d) Does G have a complete graph with at least four vertices as a subgraph? If yes, give the subgraph.
e) Is G bipartite? Explain your answer.
f) How many directed graphs are there that have G as their underlying undirected graph?
g) What is the length of the simple longest path in G? Give the path.
h) What is the number of connected components of G? Explain your answer.
i) Is there an Euler circuit in G? If yes, give such a circuit; if no, state the reason.
j) Is there an Euler path in G? If yes, give such a path; if no, state the reason.
k) Does G have a Hamilton circuit? If yes, find such a circuit; if no, justify your answer.
l) Does G have a Hamilton path? If yes, find such a path; if no, justify your answer.
1
Question 2
Given the graphs G and H in Figure 2.
b e
d c
a
(a) G
d’ c’
e’ b’
a’
(b) H
Figure 2: Graph G and H in Q2.
Determine whether G and H are isomorphic, or not. Explain your answer.
Question 3
Find the shortest path from vertex s to vertex t in the following weighted graph G (see Figure 3) using
Dijkstra’s algorithm. Describe the steps clearly.
s
u y
w z
1 v x t
4
5
8
3 3
11
1 9
4
6 3
12
8
2
6
Figure 3: Graph G in Q3.
2
Question 4
Use either Kruskal’s or Prim’s algorithm to find a minimum spanning tree for the graph G given below
(Figure 4). Please state the algorithm you choose at the beginning of your solution.
a
b c d
e f g
h i j
k
3
5
8
2
5 7
3
2 6 7 2
4
7
4
5 4 3 4
6
2 6
5
Figure 4: Graph G in Q4.
a) Write the order in which the edges are added to the tree.
b) Draw the minimum spanning tree.
c) Is the minimum spanning tree unique? Justify your answer.
1 Regulations
1. Your submission should be a single vector-based PDF document with the name the5.pdf.
2. Do not write any extra stuff like question definitions to the answer file. Just give your solution to
the question. Otherwise you will get 0 from that question.
3. Late Submission: Not allowed!
4. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be
punished according to the university regulations.
5. Newsgroup: You must follow the newsgroup (odtuclass.metu.edu.tr) for discussions and possible
updates on a daily basis.
6. Evaluation: Your .pdf file will be checked for plagiarism automatically using ”black-box” technique and manually by assistants, so make sure to obey the specifications.
2 Submission
Submission will be done via odtuclass. For those who prefer to use LATEX to generate the vector-based
PDF file, download the given template answer file ”the5.tex”. You need to compile the filled template
yourselves and submit the generated .pdf file only.
3