TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Prüfung 2020-12-11

Task 1

Let S be a compact orientable surfaces with genus >= k. State the Euler characteristic of S. (2 Points)

$\chi (S)=2-2k$

Let G be a connected graph that is embedded on S. State the formula relating the number of vertices, faces, and edges of G. (2 Points)

${\alpha }_0(G)-{\alpha }_1(G)+{\alpha }_2(G)=\chi (S)({\alpha }_0=|V|,{\alpha }_1=|E|,{\alpha }_2=|F|)$

Suppose that G has n faces, and each face is bounded by exactly 4 edges. Calculate the number of vertices and edges of G. (5 Points)

1. edges = 2* #faces = 2n
   
2. vertices = #edges - #faces + \chi (S) = 2n-n + (2-2k) = n + 2-2k

Task 2

Let G be a planar graph with n>=3 vertices. Prove that G has at most 3n-6 edges. (5 Points)

see https://math.stackexchange.com/questions/2414843/understanding-proof-for-e-leq-3v-6-in-planar-graphs

Task 3

What algorithms do you know for calculating spanning trees? Listing the names suffices. (2 Points)

e.g. Kruskal, Prim, BFS, DFS,...