Übungen

Übung 1

Wie wirken sich die Eigenschaften ungerichtet, schlingenfrei, ungewichtet auf die Adjazenz-Matrix eines Graphen aus?

Übung 2

(a)

Definieren Sie den Begriff der Adjazenz-Matrix für allgemeinere Graphen mit gerichteten Kanten, Schlingen und reell- oder komplexwertigen Kantengewichten.

(b)

Geben Sie die Adjazenz-Matrix des am Anfang des Kapitels dargestellten gerichteten und gewichteten Graphen an.

(c)

Argumentieren Sie, dass sich jede quadratische Matrix mit reellen oder komplexen Einträgen als Graph interpretieren lässt und umgekehrt.

Übung 3

Wie lassen sich Graphen mit (gerichteten und gewichteten) Mehrfachkanten mit Hilfe von Matrizen darstellen? Bei diesem Graphentyp können zwei Ecken durch eine beliebige endliche Anzahl von Kanten miteinander verbunden sein.

Übung 4

Skizzieren Sie alle Graphen mit der Eckenmenge E = { 1, 2, 3 } und geben Sie die zugehörigen Adjazenz- und Inzidenz-Matrizen an.

Übung 5

Sei n ≥ 1. Wie viele Graphen mit der Eckenmenge E = { 1, …, n } gibt es? Wie viele Graphen mit dieser Eckenmenge gibt es, wenn gerichtete Kanten zugelassen werden? Begründen Sie Ihre Antworten.

Übung 6

Sei G = (E, K) ein Graph und sei

U  =  { a  ∈  E | d(a) ist ungerade }

die Menge der Ecken mit ungeradem Grad. Zeigen Sie, dass |U| gerade ist.

Übung 7

Geben Sie einen Graphen G = (E, K) mit E = { 1, …, 10 } an, der die konstante Gradfolge 3, …, 3 besitzt.

Übung 8

(a)

Welche der folgenden sechs Folgen sind Gradfolgen eines Graphen? Begründen Sie Ihre Antworten.

(1, 1, 2, 3, 4),  (2, 2, 2, 3, 5),  (2, 3, 3, 4, 4),

(0, 0, 0, 0, 0),  (1, 1, 1, 1, 1),  (1, 2, 3, 3, 3).

(b)

Recherchieren Sie nach einem Satz, der die Folgen (d1, …, dn), die Gradfolgen eines Graphen mit n Ecken sind, charakterisiert.

Übung 9

Welche vollständigen Graphen sind bipartit bzw. vollständig bipartit?

Übung 10

Wie viele Kanten hat der vollständig bipartite Graph Kn, m in Abhängigkeit von n und m?

Übung 11

Wir betrachten die Graphen

G1  =  ({ 1, 2, 3, 4 }, { 12, 23, 34 })  und

G2  =  ({ 1, 2, 3, 4, 5 }, { 14, 23, 24, 25, 34 }).

Sind G1 bzw. G2 bipartit? Begründen Sie Ihre Antworten.

Übung 12

Untersuchen Sie die Kreise C3, C4, C5 und C6 auf die Eigenschaft „bipartit“. Stellen Sie eine Hypothese darüber auf, wann ein allgemeiner Kreis bipartit ist und wann nicht. Beweisen Sie Ihre Hypothese.

Übung 13

Auf einer Party sind ein Gastgeberpaar und vier weitere Paare. Am Ende fragt die Gastgeberin jede der neun anderen Personen, wie oft sie Hände geschüttelt hat. Sie erhält neun verschiedene Antworten. Finden Sie mit Hilfe eines Graphen heraus, mit wie vielen Personen die Gastgeberin Hände geschüttelt hat. Dabei gilt: Man schüttelt weder sich selbst noch seinem Partner die Hand, und man schüttelt auch niemandem zweimal die Hand.

Übung 14

Zeigen Sie, dass jeder Teilgraph eines bipartiten Graphen bipartit ist.

Übung 15

Zeigen Sie: Enthält G einen Kreis ungerader Länge, so ist G nicht bipartit. Formulieren Sie zudem die kontrapositive Form dieser Implikation (d. h. die logisch äquivalente Implikation ¬ B → ¬ A der Implikation A → B).

Übung 16

Sei G = (E, K) ein Graph, und sei G′ der Untergraph von G, der aus G durch Streichen einer gewissen Ecke a  ∈  E hervorgeht. Diskutieren Sie den Zusammenhang zwischen den Gradfolgen von G und G′.

Übung 17

(a)

Zeigen Sie: Ist G3 ein Teilgraph von G2 und weiter G2 ein Teilgraph von G1, so ist G3 ein Teilgraph von G1.

(b)

Formulieren und beweisen Sie eine analoge Aussage für Untergraphen.