TU Wien:Diskrete Mathematik für Informatik VU (Stufler)/Probeprüfung 2022-12-06

Aus VoWi
Zur Navigation springen Zur Suche springen

Probeprüfung zur Vorbereitung auf die Prüfung (Übungsleiter: Philipp Beltran).

  1. Give the definition of a matroid and a base of a matroid and give an example.
  2. Draw the following graph G and determine if it is planar. If it is planar, then also draw one of its duals. G=(V,E) with vertex set V={1,2,3,4,5,6,7,8,9,10,11,12,13,14} and edge set E={{1,2},{2,3},{3,4},{4,5},{5,6},{5,8},{6,7},{8,9},{9,10},{10,11},{11,12},{11,13},{11,14},{13,14}}.
  3. Let G be a connected planar graph with at least 10 vertices. Show that the average degree of vertices is smaller than 10.
    1. Give one characterization of a tree and determine the relationship between the amount of vertices to the amount of edges. Also prove your claim.
    2. Let G be a connected planar graph with n≤3 vertices. Determine the maximal amount of edges and prove your claim.
Abgerufen von „https://vowi.fsinf.at/index.php?title=TU_Wien:Diskrete_Mathematik_für_Informatik_VU_(Stufler)/Probeprüfung_2022-12-06&oldid=76176“