Sale!

# CENG 223 Take Home Exam 5 Solved

Original price was: $40.00.Current price is:$35.00.

Category:

5/5 - (1 vote)

## 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.

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.

## 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