0 Daumen
886 Aufrufe

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

Avatar von

"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

2 Antworten

+1 Daumen
 
Beste Antwort

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

Avatar von
0 Daumen

> 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:

  • Vout: Knoten aus denen Kanten herausführen
  • Vin: Knoten in die Kanten hineinführen

mit Vout ∪ Vin = V und Vout ∩ Vin = ∅.

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

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

also ist dies eine unlösbare Aufgabe?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community