Turniere

  • 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]

  • Zitat

    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-

    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  • 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)).