7. ¨Ubung Graphentheorie I - Lehrstuhl II für Mathematik

Lehrstuhl II für Mathematik
Prof. Dr. L. Volkmann
http://www.math2.rwth-aachen.de
SS 2006
7. Übung Graphentheorie I
Aufgabe 1. Es sei Tn ein Turnier der Ordnung n ≥ 3. Man beweise oder widerlege:
(a) Liegt jede Ecke auf einem orientierten Kreis, dann ist Tn stark zusammenhängend.
(b) Liegt jeder Bogen auf einem orientierten Kreis, dann besitzt Tn einen orientierten Hamiltonkreis.
(c) Liegt jede Ecke auf einem orientierten Kreis der Länge > n2 , dann besitzt Tn einen orientierten Hamiltonkreis.
(d) Ist Tn nicht transitiv und ist k ein Bogen von Tn , so besitzt der Digraph Tn − k einen
orientierten Hamiltonschen Weg.
(e) Ist Tn nicht transitiv, dann gibt es einen Bogen k von Tn , so dass der Digraph Tn − k einen
orientierten Hamiltonschen Weg besitzt.
Aufgabe 2. Es sei Tn ein Turnier der Ordnung n ≥ 3. Man zeige:
n−1
≤ ∆+ (Tn ).
(a) δ + (Tn ) ≤
2
(b) Gilt d+ (x, Tn ) = d+ (y, Tn ) für zwei Ecken x, y aus Tn , so beweise man, dass x und y in der
gleichen starken Zusammenhangskomponente von Tn liegen.
(c) Besteht Tn aus genau zwei starken Zusammenhangskomponenten, so zeige man
n
∆+ (Tn ) − δ + (Tn ) ≥ .
2
Aufgabe 3. Es sei n ≥ 3 und Tn ein Turnier mit d+ (x, Tn ) = d− (x, Tn ) für alle Ecken
x ∈ E(Tn ). Man zeige:
(a) Es gilt n = 2r + 1 für ein r ∈ N und Tn ist r-regulär.
(b) Tn ist Hamiltonsch.
Aufgabe 4. Es sei T ein reguläres Turnier. Man zeige, daß zu jedem orientierten Kreis
C gerader Länge in T ein orientierter Kreis C 0 in T existiert, so daß E(C) ⊂ E(C 0 ) und
|E(C 0 )| = |E(C)| + 1 gilt.
Aufgabe 5. Es sei n ≥ 5 und Tn ein stark zusammenhängendes Turnier der Ordnung n. Für
3 < p < n zeige man, daß es mindestens p − 2 Ecken gibt, die auf zwei orientierten Kreisen
der Länge p − 1 liegen.
Aufgabe 6. Es sei Tn ein Turnier der Ordnung n ≥ 3, das die Bedingung min{δ − , δ + } ≥
erfüllt. Man zeige, daß Tn stark zusammenhängend ist.
n−1
4

Download Report