Punkte verbinden - Graphentheorie?

Neue Frage »

Pascal95 Auf diesen Beitrag antworten »
Punkte verbinden - Graphentheorie?
Hallo,

ich habe eine Frage und weiß garnicht so recht, wo ich die einsortieren soll.

Ich glaube mich erriniern zu können, dass ich dieses Problem (oder ein ähnliches) schon einmal hier im Forum gefunden habe. Es existierte, so wie ich mich erriniere, keine Lösung dazu.

Die Aufgabe war die Folgende:
"Verbinde jeden der 3 Punkte mit jedem der 3 gegenüber liegenden."
Dabei sollten sich die Linien nicht überschneiden (planar verwirrt )
Dann war folgendes Bild (Punkte waren dann Quadrate - sollte egal sein):
[attach]19280[/attach]

Dazu habe ich mir folgende "Lösung" überlegt.
Leider kann ich nicht alle Kästchen verbinden:
[attach]19279[/attach]


Ist das Thema der sogenannten "Graphentheorie" ?

Vielen Dank,
Pascal
lgrizu Auf diesen Beitrag antworten »
RE: Punkte verbinden - Graphentheorie?
Schau einmal hier: Klick.

Hier im Board wurde es auch schon einmal besprochen: Das 3-Brunnen-Problem.
Hubert1965 Auf diesen Beitrag antworten »

Beides richtig:

*) Es ist ein Problem der Graphentheorie.
*) Dieses Problem hat keine Lösung.
Pascal95 Auf diesen Beitrag antworten »

Hallo,

in dem von Igrizu verlinktem Thread ist das Problem leider nicht besonders gut erklärt. Es wird nur erwähnt, dass es sich um Graphentheorie handelt.

Hier (http://www.funnygames.nl/spel/gas_licht_en_water.html) habe ich das auch gefunden (ganz lustig als Spiel aufbereitet smile ).

Dafür ist der "Zum Begriff Topologie" ziemlich ausführlich Augenzwinkern Danke sehr.

@Hubert1965
Danke auch dir, aber weiß villeicht jemand WARUM das Problem nicht lösbar ist ?
kiste Auf diesen Beitrag antworten »

Es geht eigentlich hier um die Plättbarkeit von Graphen.

Der obige Graph heißt , der vollständige bipartite (3,3) Graph.
Soweit ich mich erinnern kann, wurde der Beweis, das dieser nicht planar ist, mittels einer Abschätzung zwischen Kanten und Knoten Zahl von planaren bipartiten Graphen gemacht.

Ein Suchstichwort wäre noch der Satz von Kuratowski, der besagt dass ein Graph genau dann plättbar ist, falls er keinen K_3,3 oder K_5 "enthält".
Pascal95 Auf diesen Beitrag antworten »

Hallo,

ein bisschen klarer wird mir die Sache allmählich.

Hier wird versucht zu beweisen, warum nicht plättbar ist (sich in einer Ebene zeichnen lässt).

Hier sind die Graphen auch abgebildet.

Wo man dann schon gerade beim Thema ist, wird mit hier nicht klar, wie man G2 anders zeichnen kann verwirrt
Ich verstehe also die Umwandlung nicht (Ich sehe den Schnittpunkt der 2 linien in der mitte auch nicht mehr ?)

Pascal
 
 
kiste Auf diesen Beitrag antworten »

Da ist doch das Bild wie man G2 anders zeichnen kann. Wichtig bei Graphen sind nur die Verbindungen. In beiden Zeichenvarianten hat es aber diesselben Verbindungen(Kanten)
Pascal95 Auf diesen Beitrag antworten »

Sorry,

ich verstehe gar nicht, was die gemeinsam haben.

[attach]19302[/attach]

Muss denn nicht etwa das Kreuz erhalten bleiben?

Oder wird der rechte obere Punkte einfach nach links unten geschoben??
kiste Auf diesen Beitrag antworten »

Das Kreuz hat doch keine graphentheoretische Eigenschaft. Die wichtige Eigenschaft hier ist doch, dass jeder Knoten mit jedem anderen Knoten verbunden ist.

Ja du kannst es so veranschaulichen, dass der rechte obere Punkt nach innen gezogen wird.
Pascal95 Auf diesen Beitrag antworten »

Aha, ok.
Jetzt ist es mir klar.
Danke!

Kennst du vielleicht auch einen Beweis dafür, dass nicht planar ist, oder ist der Beweis hier gut?

[attach]19303[/attach]

Die Graphentheoretische Eigenschaft, von der man dann wohl spricht, wäre hier, dass jeder der drei linken Punkte mit jedem der 3 rechten verbunden ist. ( deswegen)

Pascal
kiste Auf diesen Beitrag antworten »

Der Beweis, der dort als falsch betitelt wurde ist das was ich machen würde Big Laugh

In bipartiten planaren Graphen gilt m <= 2n-4 mit m = Anzahl Kanten, n= Anzahl Knoten.
Dies ist hier nicht erfüllt.
Pascal95 Auf diesen Beitrag antworten »

Ok, also "Anzahl der Kanten" ist kleinergleich "2*Anzahl der Knoten-4"

(Anzahl der Kanten, also Verbindungen)
(Anzahl der Knoten, also Punkte)

Die Frage ist nun , also und das stimmt nicht!

Habe ich richtig verstanden? :
bipartiter Graph:
Graph entspricht dem Verbinden von Elementen einer Menge mit Elementen einer anderen Mengen. Dann ist das Produkt der Elemente der Mengen gleich der Anzahl der Kanten, aber können auch mehr als 2 Mengen im Spiel sein?

Hier stimmt es nicht mehr, dass man 2*2*3 = 12 Kanten benötigt.
Schau dir mal mein Bild an:
[attach]19304[/attach] (schöne Zeichnung Augenzwinkern )

Nennt man den Graphen auch bipartit?

Ich hab das mal schön übersichtlich mit Farben gemacht :
Von jedem roten Punkt gehen 2 Kanten an jeweils einen blauen und 3 jeweils an einen grünen. Das sind dann pro rotem Punkt 5 Kanten, also 10 Kanten von rot aus.
Das stimmt auch.

Wenn man das aber so weiter macht, zählt man doch doppelt?
Wie kann man dafür Formeln finden?

Und warum gilt für bipartite Graphen:
[edit] ?
Und planar ist dasselbe wie plättbar?

Pascal
kiste Auf diesen Beitrag antworten »

Dein Bild ist kein bipartiter Graph, vllt. ein tripartiter(Begriff erfunden Augenzwinkern )

Ich habe bei der Formel nie ein genau dann wenn behtauptet, nur die eine Richtung.

Planar ist eine Eigenschaft der konkreten Einbettung, bei deinem Beispiel G2 war die erste Einbettung nicht planar, aber die zweite.
Plättbar heißt, dass es eine planare Einbettung gibt.

Du solltest dir ein Skript zur Graphentheorie anschauen, man kann hier keine Vorlesung ersetzen.
Pascal95 Auf diesen Beitrag antworten »

Hallo.

Zitat:
Original von kiste
Dein Bild ist kein bipartiter Graph
Weil er aus 3 verbundenen Mengen besteht, oder?

Zitat:
Original von kiste
Ich habe bei der Formel nie ein genau dann wenn behtauptet, nur die eine Richtung.

Achso, klar. "In bipartiten planaren Graphen gilt... " meintest du.
.
Also WENN der Graph planar ist, dann gilt diese Ungleichung.
Und die Kontraposition lautet:
.
Also wenn die Ungleichung nicht so erfüllt ist, dann ist der Graph nicht planar Augenzwinkern

Zitat:
Original von kiste
Planar ist eine Eigenschaft der konkreten Einbettung, bei deinem Beispiel G2 war die erste Einbettung nicht planar, aber die zweite.
Plättbar heißt, dass es eine planare Einbettung gibt.

Ok, das versteh ich sogar Big Laugh

Zitat:
Original von kiste
Du solltest dir ein Skript zur Graphentheorie anschauen.

Das werde ich. Wenn ich fragen habe, weiß ich ja, wohin ich mich wenden kann.

Danke sehr,
Pascal
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »