Exam text content

 

MAT-62756 Graph Theory Examination 19.12.2013

Examiner: Keijo Ruohonen

NB This is a elosed-book exam, no materia] is allowed. Nonprogrammable calculators are
allowed.

1. a) Show that for each numbern > 1 there isa connected graph with n vertices all of
them having different degrees.

b) Is this possible for any n > 1ifitis reguired that the graph is simple but not nec-
essarily connected? Explain your reasoning!

2. Explain briefly whatisa) the adjacency matrix, b) the incidence matrix, €) the cut matrix,
d) the circuit matrix, €) the fundamental cut matrix and f) the fundamental circuit matrix
of a digraph.

 

3. 4) The Hungarian Algorithm for bipartite graphs, how it
works and what is its function.

b) Apply the Hungarian Algorithm to the graph on the right
starting from the empty edge set. Explain carefully each
Step you take! (The graph is bipartite.)

4. a) Givean example of a case where a transport network häs a cycle and the Ford-
Fulkerson Algorithm gives a positive flow for each arc of the cycle. Explain the
steps of the algorithm in detail.

b) Show thatifa transport network has cycles then there is a maximum flow such that
in each cycle there is at least one arc with a zero flow.

(Flow around a cycle may in fact be useful in some situations (e.g. as a storage), but usually it

g.
just eats resources and should be removed. Algorithmically this is a bit tricky.)

5. The Davidson-Harel Algorithm, how it works and what is its function.

Suomeksi —— + ="