Turniere

[azi]

Hab da noch eine Graphenfrage aus dem PO ausgegraben für die ich keine Lösung habe:
Nennen Sie eine Bedingung, daß es in einem Turnier einen eindeutige Reihenfolge gibt! Gibt es ein Turnier, bei dem alle Erster sind? Wieviele stark zusammenhängende Komponenten hat ein transitives Turnier mit n Knoten? [4P]

[-z0nk-]

Original geschrieben von azi
Hab da noch eine Graphenfrage aus dem PO ausgegraben für die ich keine Lösung habe:
Nennen Sie eine Bedingung, daß es in einem Turnier einen eindeutige Reihenfolge gibt! Gibt es ein Turnier, bei dem alle Erster sind? Wieviele stark zusammenhängende Komponenten hat ein transitives Turnier mit n Knoten? [4P]

Eine Eindeutige Reihenfolge gibt es bei einem Turnier genau dann, wenn das Turnier transitiv ist, d.h. wenn die kanten (a,b) und (b,c) im Turnier existieren, dann existiert (als Folge) auch die Kante (a,c).

Turnier, bei dem alle erster sind: 3 Teilnehmer, jeder gewinnt ein spiel.

Ein transitives Turnier mit n Knoten hat genau n stark zusammenhängende Komponenten, nämlich jeden Knoten einzeln.

MfG, -z0nk-

[azi]

Dank! Wieviele Turniere der Ordnung 4 bis auf Isomorphie gibt es, bzw wie kann ich am schnellsten prüfen ob 2 Turniere isomorph sind?

[Neo]

da das turnier eine spezielle Form eines gerichteten Graphen ist, wird man (vermute ich) die Isomorphie genauso wie bei den anderen gerichteten Graphen bestimmen.

=> gleiche Knotenmenge, gleiche Kantenmenge, gleiche Gradfolge

und die Bedingung:

seien T1 und T2 Turniere. Dann sind sie genau dann isomorph, wenn es eine Funktion phi und eine Funktion sigma gibt mit: wenn e (Element von E(T1)) = (x, y) (Element von V(T1) x V(T1)), dann gilt: phi(e) (Element von E(T2)) = (sigma(x), sigma(y)) (Element von V(T2) x V(T2)).