Übungsaufgabe optimaler Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei G=(V,E) ein gerichteter, vollständiger Graph, d.h. ein Graph der folgende zwei Bedingungen erfüllt:
1. [mm]\forall a \in V: (a,a) \in E[/mm]
2. [mm]\forall a,b \in V, a \not= b : (a,b) \in E \gdw (b,a) \not\in E[/mm]
G heiße optimal, wenn gilt:
[mm]\forall a,b \in V \exists p \in V: (a,p),(p,b) \in E[/mm]
Also in Worten "von jedem Knoten lässt sich jeder andere über genau zwei Kanten erreichen".
Sei |V|=n die Anzahl der Knoten im Graphen.
Für welche n [mm]\in \IN[/mm] existiert ein solcher optimaler Graph? |
Ich hab die Aufgabe vor einiger Zeit mal gestellt gekriegt und fand sie ganz schön; jetzt dürft ihr auch mal.^^
Und ach ja, das ist keine Frage, das soll eine Übungsaufgabe sein - ich muss nur erst nen Mod finden der das umstellt.
Also, viel Spaß ;)
|
|
| |
|
Dummy-Frage, auf dass die Aufgabe nicht im Foren-Nirvana verschwindet...
Bitte nur auf die Aufgabe antworten, nicht auf diese Frage. ;)
|
|
|
|
