Einbettung von Gr. auf Torus < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:50 Do 12.01.2012 | | Autor: | clemenum |
| Aufgabe | | Man zeige, dass die Graphen [mm] $K_5$ [/mm] und [mm] $K_{3,3}$ [/mm] auf den Torus eingebettet werden können. |
Nun, es ist bekannt, dass [mm] $K_5$ [/mm] und [mm] $K_{3,3}$ [/mm] nicht planar sind (dürfen wir voraussetzen). Ich kann daher wirklich nicht verstehen, warum sie bei Aufzeichung auf einen Körper auf der Oberfläche planar sein sollen. Wieso sollten sich hier die Linien doch nicht mehr überkreuzen?
Meine Idee der Vorgehensweise ist die, dass ich den beiden Graphen geeignete Funktionsgleichungen gebe und dann mit der Torusgleichung gleichsetze.
|
|
| |
|
Hallo,
> Man zeige, dass die Graphen [mm]K_5[/mm] und [mm]K_{3,3}[/mm] auf den Torus
> eingebettet werden können.
> Nun, es ist bekannt, dass [mm]K_5[/mm] und [mm]K_{3,3}[/mm] nicht planar
> sind (dürfen wir voraussetzen). Ich kann daher wirklich
> nicht verstehen, warum sie bei Aufzeichung auf einen
> Körper auf der Oberfläche planar sein sollen. Wieso
> sollten sich hier die Linien doch nicht mehr überkreuzen?
Mag sein, dass mir das nötige hintergrundwissen fehlt, aber für mich sprichst du in rätseln. was bedeutet denn [mm]K_5[/mm] und [mm]K_{3,3}[/mm]?
Handelt es sich nicht um eine geometrische aufgabe?
gruss
matthias
>
> Meine Idee der Vorgehensweise ist die, dass ich den beiden
> Graphen geeignete Funktionsgleichungen gebe und dann mit
> der Torusgleichung gleichsetze.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:49 Di 17.01.2012 | | Autor: | clemenum |
Ich zittiere aus Wiki:
"Der Satz von Kuratowski benutzt zwei spezielle Graphen: [mm] $K_5$ [/mm] und [mm] $K_{3,3}.$ [/mm] Bei [mm] $K_5$ [/mm] handelt es sich um den vollständigen Graphen mit 5 Knoten, bei [mm] $K_{3,3}$ [/mm] um einen vollständig bipartiten Graphen, der in zwei je dreielementige Teilmengen aufgeteilt ist. Beide Graphen sind nicht planar. Sie sind sogar die kleinsten nicht-planaren Graphen überhaupt, was direkt aus dem Satz von Kuratowski folgt. "
Nun, die Gleichung des Torus wurde uns angegeben und lautet: [mm] $\left( c- \sqrt{x^2+y^2}\right)^2 [/mm] + [mm] z^2 [/mm] = [mm] a^2.$ [/mm] Außer einer zeichnerischen Lösung (mit ein wenig Geschick kann man die beiden Graphen auf dem Papier auf den auf die Papierebene projezierten Torus zeichnen) misslingt mir leider jeglicher Lösungsversuch. Die einzige (analytische) Idee wäre, den beiden Graphen irgendwie eine Funktionsvorschrift zu versehen und dann mit der Torusgleichung gleichzusetzen, was Auskunft über die Anzahl der Überschneidungen geben sollte... ?
Kann mir jemand helfen?
|
|
|
| |
|
> Ich zittiere aus Wiki:
> "Der Satz von Kuratowski benutzt zwei spezielle Graphen:
> [mm]K_5[/mm] und [mm]K_{3,3}.[/mm] Bei [mm]K_5[/mm] handelt es sich um den
> vollständigen Graphen mit 5 Knoten, bei [mm]K_{3,3}[/mm] um einen
> vollständig bipartiten Graphen, der in zwei je
> dreielementige Teilmengen aufgeteilt ist. Beide Graphen
> sind nicht planar. Sie sind sogar die kleinsten
> nicht-planaren Graphen überhaupt, was direkt aus dem Satz
> von Kuratowski folgt. "
>
> Nun, die Gleichung des Torus wurde uns angegeben und
> lautet: [mm]\left( c- \sqrt{x^2+y^2}\right)^2 + z^2 = a^2.[/mm]
> Außer einer zeichnerischen Lösung (mit ein wenig Geschick
> kann man die beiden Graphen auf dem Papier auf den auf die
> Papierebene projezierten Torus zeichnen) misslingt mir
> leider jeglicher Lösungsversuch. Die einzige (analytische)
> Idee wäre, den beiden Graphen irgendwie eine
> Funktionsvorschrift zu versehen und dann mit der
> Torusgleichung gleichzusetzen, was Auskunft über die
> Anzahl der Überschneidungen geben sollte... ?
>
> Kann mir jemand helfen?
Hallo Clemenum,
mir waren die Bezeichnungen [mm] K_5 [/mm] und [mm] K_{3,3} [/mm] zunächst auch
nicht geläufig, aber es fiel mir gleich ein, was damit
wohl gemeint sein muss, da diese Graphen bei der
Frage nach der Planarität von Graphen eine grundlegende
Rolle spielen.
Für alle, die sich nicht ganz auskennen:
[mm] K_5 [/mm] ist ein Graph mit 5 Knoten und genau einer (ungerichteten)
Kante für jedes der 10 möglichen Knotenpaare - anders gesagt
ein Fünfeck ABCDE mit allen Seiten AB,BC,CD,DE,EA und
Diagonalen AC,CE,EB,BD,DA.
[mm] K_{3,3} [/mm] ist ein Graph mit Knoten (Ecken) A,B,C,1,2,3
und den Kanten A1,A2,A3,B1,B2,B3,C1,C2,C3 .
Nicht klar ist mir aber, was du mit dem "auf die Ebene
projizierten Torus" meinst. Es kommt ganz drauf an,
an welche Art von Projektion du dabei denkst.
Nach meiner Meinung würde eine geeignete zeichnerische
Lösung durchaus genügen.
Als "Projektion" würde ich dabei z.B. die Abbildung
$\ f:\ (x,y)\ [mm] \mapsto [/mm] \ [mm] (x-\lfloor x\rfloor [/mm] \ ,\ [mm] y-\lfloor y\rfloor [/mm] )$
benützen, welche [mm] \IR^2 [/mm] auf das Einheitsquadrat und dieses
dann auf den Torus abbildet.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:23 Di 17.01.2012 | | Autor: | clemenum |
Hallo Al-Chwarizmi!
Erstmal, vielen Dank für deine Reaktion und Erklärungen.
Mit "Projezieren auf das Papier" meine ich natürlich, dass ich den Torus auf das Papier zeichne und auf diesen dann die beiden Graphen einzubetten versuche.
Ich habe leider nicht verstanden, was mir die Abbildung auf das Einheitsquadrat bringen soll. Ich sehe hier den Zusammenhang zu [mm] $K_{3,3}$ [/mm] und [mm] $K_5$ [/mm] nicht. Hattest du hiermit eine analytische Lösung versucht? Wenn ja, dann bitte ich dich - solltest du kurz Zeit haben - mir den Zusammenhang zu den beiden Graphen kurz zu erläutern.
Vielleicht stehe ich nur gerade auf der Leitung :/
|
|
|
| |
|
> Hallo Al-Chwarizmi!
>
> Erstmal, vielen Dank für deine Reaktion und Erklärungen.
>
> Mit "Projezieren auf das Papier" meine ich natürlich, dass
> ich den Torus auf das Papier zeichne und auf diesen dann
> die beiden Graphen einzubetten versuche.
Naja, auch die Beschreibung "den Torus auf das Papier
zeichnen" kann man unterschiedlich verstehen. Ich vermute
mal, dass du meinst, so etwas wie einen Rettungsring
so zu zeichnen, wie ihn deine Handykamera abbilden
würde. Das geht natürlich, nur musst du dich dann halt
um die sichtbaren und die unsichtbaren Teile der Zeichnung
kümmern.
> Ich habe leider nicht verstanden, was mir die Abbildung auf
> das Einheitsquadrat bringen soll.
Den besagten Rettungsring (oder einen ringförmigen
Gummischlauch wie die früheren Schläuche der Autoreifen)
kann man so parametrisieren:
[mm] $\vec [/mm] X(t,p) = [mm] \begin{pmatrix} x \\ y \\ z \end{pmatrix} [/mm] = R [mm] \cdot \begin{pmatrix} \cos(t) \\ \sin(t) \\ 0 \end{pmatrix} [/mm] + r [mm] \cdot \begin{pmatrix} \cos(t) \cdot \cos(p) \\ \sin(t) \cdot \cos(p) \\ \sin(p) \end{pmatrix}=\begin{pmatrix} (R + r \cdot \cos(p)) \cos(t) \\ (R + r \cdot \cos(p)) \sin(t) \\ r \cdot \sin(p) \end{pmatrix}$
[/mm]
Dabei müssen die beiden Parameter p und t je ein Intervall
der Länge [mm] 2\pi [/mm] durchlaufen, damit die gesamte Torusfläche
einmal abgedeckt wird. Es wird also ein Quadrat in der
p-t-Ebene auf die Torusfläche abgebildet. Die Abbildung
ist aber sowohl in p- und in t-Richtung periodisch, so dass
man das "Grundquadrat" in der p-t-Ebene auch verlassen
darf, um eine überschneidungsfreie Darstellung eines
Graphen wie zum Beispiel [mm] K_5 [/mm] zu zeichnen.
Ich würde dir aber eine Zeichnung auf einem echten
Torus jedenfalls auch ans herz legen.
LG Al-Chw.
|
|
|
| |
|
> Hallo Al-Chwarizmi!
>
> Erstmal, vielen Dank für deine Reaktion und Erklärungen.
>
> Mit "Projezieren auf das Papier" meine ich natürlich, dass
> ich den Torus auf das Papier zeichne und auf diesen dann
> die beiden Graphen einzubetten versuche.
>
> Ich habe leider nicht verstanden, was mir die Abbildung auf
> das Einheitsquadrat bringen soll. Ich sehe hier den
> Zusammenhang zu [mm]K_{3,3}[/mm] und [mm]K_5[/mm] nicht. Hattest du hiermit
> eine analytische Lösung versucht? Wenn ja, dann bitte ich
> dich - solltest du kurz Zeit haben - mir den Zusammenhang
> zu den beiden Graphen kurz zu erläutern.
Hallo clemenum,
mir geht es keineswegs um eine "analytische" Lösung,
sondern um eine rein graphische.
Man kann eine Torusfläche durch zwei kreisförmige
Schnitte (einem Meridiankreis und z.B. dem äußeren
Äquatorkreis entlang) in ein viereckiges Flächenstück
zerschneiden (das dabei nicht in verschiedene Stücke
zerfällt). Dieses Flächenstück kann man auf ein
Rechteck (oder ein Quadrat) abbilden. Wandert man
auf diesem Flächenstück geradeaus und gelangt dabei
an den Rand des Vierecks, kann man über diesen
hinaus weitergehen (da die Randlinie ja kein wirkli-
cher Rand des ursprünglichen Torus war). Die Fort-
setzung der Wanderung erfolgt dann einfach am
gegenüber liegenden Rand. Diese in einem
ebenen p-t-Koordinatensystem flach ausgebreitete
"Toruswelt" ist sowohl in p- als auch in t-Richtung
periodisch.
Für eine Darstellung des [mm] K_{3,3} [/mm] - Graphen kann man
nun etwa die Knoten A,B,C,1,2,3 in einem Grund-
quadrat verteilen und diese Grundfigur nach rechts
und links und dann alles auch nach oben und unten
wiederholen. Zu beachten ist dabei, dass alle unendlich
vielen Quadrate, die dann in der Ebene entstehen,
als zueinander identisch betrachtet werden müssen.
Es handelt sich nur um verschiedene Bilder der einen
Torusfläche, so wie alle Spiegelbilder einer Kerzenflamme
in einem Spiegelsaal eben nur verschiedene Bilder
einer einzigen realen Flamme sind.
Nun kann man alle 9 Kanten des Graphen kreuzungs-
frei einzeichnen:
[Dateianhang nicht öffentlich]
Al-Chwarizmi
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
> Man zeige, dass die Graphen [mm]K_5[/mm] und [mm]K_{3,3}[/mm] auf den Torus
> eingebettet werden können.
> Nun, es ist bekannt, dass [mm]K_5[/mm] und [mm]K_{3,3}[/mm] nicht planar
> sind (dürfen wir voraussetzen). Ich kann daher wirklich
> nicht verstehen, warum sie bei Aufzeichung auf einen
> Körper auf der Oberfläche planar sein sollen. Wieso
> sollten sich hier die Linien doch nicht mehr überkreuzen?
Die Oberfläche eines Torus ist eben topologisch nicht
äquivalent zur Ebene oder auch zur Kugeloberfläche.
In der Terminologie von Science Fiction könnte man es
vielleicht so ausdrücken: Versehen wir eine Kugelfläche
mit einem "Wurmloch", so erhalten wir die Torusfläche.
Und nun dürfen wir eben einzelne Kanten durch dieses
Wurmloch führen - und siehe da, es wird möglich, alle
10 Kanten des Graphen [mm] K_5 [/mm] ohne Überschneidungen
auf die Fläche zu legen !
LG Al-Chwarizmi
|
|
|
|
