TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Test 1 2016W

Zwischentest in VU Diskrete Mathematik für Informatik bei Martin Rubey.
10 Punkte gesamt.

[2 Punkte]
1a: Handshake Lemma angeben
1b: gegeben |E| und Anazhl vertices mit degree |Vd=1|, |Vd=2|, war zu finden mit Handshake Lemma Anzahl vertices mit |Vd=3|

[3 Punkte]
2: Zwei Basen B1 = {{r,s},{r,t},{s,t}}, B2 = {{u,x},{x,y},{y,z}}
welche davon ist Basis eines Matroids, welche nicht und warum.
B2 ist es nicht. axiom 1 + 2 sind klar (leere menge klar, und teilmengen der basen einfach per definition).
zu zeigen axiom 3: wenn man bei einer basis ein elem entfernt, müssen wir in einer der urspr. basen ein element finden dass wir wieder dazugeben können um zu eine der urspr. basen oder deren subsets (diese sind ja independent). bei B1 geht das, bei B2 aber nicht mit A = {y, z} B = {u}, denn {u, y} oder {u, z} sind keine der basen oder deren submengen

[5 Punkte]
3a: Adjazenzmatrix von undirected simple graph
3b: #paths pfadlänge 4 (Adjazenzmatrix hoch 4)
3c: existiert ein induzierter subgraph mit 2 edges? d.h. man wähle ein V' ⊆ V, und MUSS dann alle edges nehmen die zwischen den neuen vertices im ursprünglichen graph liegen. in diesem fall ging das.