Gerichteter Graph mit 6 Knoten und 9 Kanten?

Question

Ich suche nach einem Grichtetem Graphen welcher 6 Knoten und 9 Kanten besitzt.
Dazu kommt dass keine Zykel beinhaltet sein dürfen. Außerdem dürfen keine Pfade mit der Länge 2 existieren und die Kanten dürfen sich nicht überkreuzen.

Ich habe es schon mehrfach ausprobiert, jedoch habe ich maximal immer nur 8 Kanten hinbekommen.
Ich denken mittlerweile, dass dies unter genannten Bedingungen gar nicht möglich ist.

Wäre aber auf eine richtige Lösung gespannt.
Viel Erfolg

Comments

"Außerdem dürfen keine Pfade mit der Länge 2 existieren"

Wie ist das genau zu verstehen. Enthalten Pfade der Länge 3 keine Pfade der Länge 2 oder doch? 

---

also wenn die pfadlänge 3 ist, dann muss folglisch auch die pfadlänge 2 vorhanden sein. Zb.

1 -> 2 -> 3: Länge 2

1 -> 2 -> 3 -> 4: Länge 3

Answer 1

E = {(1,4) , (1,5) , (1,6) , (2,4) , (2,5) , (2,6) , (3,4) , (3,5) , (3,6)} wäre eine Lösung, wenn sich die Kanten überkreuzen dürfen. Ansonsten existiert im 2-dimensionalen Raum kein Graph unter diesen Bedingungen..

Answer 2

> Außerdem dürfen keine Pfade mit der Länge 2 existieren

Das heißt die Knotenmenge V lässt sich in zwei disjunkte Teilmengen aufteilen:

• V_out: Knoten aus denen Kanten herausführen
• V_in: Knoten in die Kanten hineinführen

mit V_out ∪ V_in = V und V_out ∩ V_in = ∅.

Betrachte |V_out|. Die Fälle |V_out|∈{3,4,5,6} entsprechen den Fällen |V_in|∈{3,4,5,6} ≡ |V_out|∈{0,1,2,3}, brauchen also nicht gesondert betrachtet werden.

• Fall |V_out| = 0: Es kann keine Kanten geben. Widerspricht der Forderung nach 9 Kanten
• Fall |V_out| = 1: Es kann höchstens 5 Kanten geben. Widerspricht der Forderung nach 9 Kanten
• Fall |V_out| = 2: Es kann höchstens 8 Kanten geben. Widerspricht der Forderung nach 9 Kanten
• Fall |V_out| = 3: Es gibt genau einen Graphen mit 9 Kanten. Dieser ist (Richtung außer acht gelassen) isomorph zu K_3,3. Widerspricht der Forderung nach Planarität

Comments

also ist dies eine unlösbare Aufgabe?