+1 Punkt
2,9k Aufrufe

ich habe mich gerade an ein Problem erinnert, über das ich mal in der Grundschule nachgedacht habe. Also folgende Skizze:

Und jetzt die Frage: Wie kann man beweisen, dass es unmöglich ist, jeden der roten Punkte mit jedem der grünen Punkte zu verbinden, ohne dass sich zwei Striche überschneiden?

Hat jemand eine Idee, wie man es beweisen könnte? ^^

 

Danke

 

Thilo

Gefragt von 4,4 k
Ich mag mich noch daran erinnern, dass es etwas mit dem Grad der Punkte zu tun hat, also wie viele Linien davon abgehen, bin mir aber nicht sicher....

2 Antworten

+1 Punkt

Hi ich hoffe das kommt für dich noch rechtzeitig.

Ich hatte das Thema auch mal, und ich kann dir dazu nur die PDF:

http://www.uni-giessen.de/~gc1099/dm/DM%20II%20-%20Wiederholung%20-%20Graphentheorie.pdf

Empfehlen.

Dort wird auch genau dein Problem behandelt, und wiederlegt ;).

Beantwortet von
+1 Punkt

Gemäß Tipp von nouse:

Ein Graph heißt planar, falls er ohne Überschneidungen in der Ebene gezeichnet ist. 

Ein Graph ist plättbar, wenn er überschneidungsfrei in die Ebene gezeichnet werden kann.

Es ist nicht möglich!

Beweis: Angenommen, wir könnten diesen Graphen als planaren Graphen zeichnen. Dann hätte dieser  n = 6  Ecken, m = 9 Kanten, und nach der Eulerschen Polyederformel könnten wir die Anzahl der Länder ausrechnen:  2 = n – m + g = 6 – 9 + g, also  g = 5.

Jedes Gebiet des Graphen muß eine gerade Anzahl von Ecken haben, denn Häuser (rote Punkte) und Versorgungswerke (grüne Punkte) wechseln sich ab. Daher hat jedes Gebiet mindestens 4 Ecken und also auch mindestens 4 Kanten. Daher gilt ∑m(L) ≥ 4g und daher 2m ≥ 4g.

In unserem Fall bedeutet dies  18 = 2m ≥ 4g = 20. Dieser Widerspruch zeigt, dass K3,3 nicht plättbar ist.

Der gute alte Euler, unglaublicher Kerl!

--

Ich wollte zuerst mit Jordanischem Kurvensatz ansetzen, aber das wäre wohl nichts geworden :)

Beantwortet von
Zum noch besseren Verständnis sei ein englisches Video nachgereicht, das die Lösung mit der Eulerschen Formel schön darstellt:



Siehe auch http://de.wikipedia.org/wiki/Eulerscher_Polyedersatz

lg Kai

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...