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

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]

- edges = 2* #faces = 2n
- 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,...