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

From VoWi
Jump to navigation Jump to search

Task 1[edit]

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

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)[edit]

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)[edit]

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

Task 2[edit]

Draw an example for a planar graph and an example for a non-planar graph. (2 Points)[edit]

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

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

Task 3[edit]

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

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

Calculate the number of spanning trees of a cycle of length n>=3. (5 Points)[edit]

Task 4[edit]

Let G be a connected graph. Define the graph distance dG on G and prove that it is a metric. (2 Points)[edit]

Suppose that there is a vertex o surch that any edge {x,y} of G satisfies dG(o,x) =!= dG(o,y). Show that G is bipartite. (5 Points)[edit]