Graphentheorie < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:58 Mi 06.01.2010 | | Autor: | Drechen |
| Aufgabe | | Beweise: dass jeder Springer Graph bipartit ist. |
Hallo!
Also, dass jeder Springer bipartit ist, ist ja klar.. denn der Springer-Graph ist ja quasi ein Schachfeld und zwischen den Feldern, wo man durch einen Springerzug hingelangen kann gibt es graphentheoretisch modelliert Kanten... Man gelangt jedoch immer von einem schwarzen auf ein weißes Feld und umgekehrt..
jedoch habe ich ka, wie ich das graphentheoretisch beweisen kann?
Über Ansätze wäre ich sehr dankbar.
Liebe Grüße
Andrea
Ich habe diese Frage in keinem anderen Forum und auf keiner anderen Internetseite gestellt.
|
|
| |
|
Hallo Andrea,
> Beweise: dass jeder Springer Graph bipartit ist.
> Hallo!
> Also, dass jeder Springer bipartit ist, ist ja klar.. denn
> der Springer-Graph ist ja quasi ein Schachfeld und zwischen
> den Feldern, wo man durch einen Springerzug hingelangen
> kann gibt es graphentheoretisch modelliert Kanten... Man
> gelangt jedoch immer von einem schwarzen auf ein weißes
> Feld und umgekehrt..
Ja eben. Es sind also keine zwei schwarzen Felder untereinander duch eine Kante verbunden, und auch keine zwei weißen Felder.
Genau das nennt man ![[]](/images/popup.gif) bipartit.
> jedoch habe ich ka, wie ich das graphentheoretisch
> beweisen kann?
Ich finde, das hast Du schon. Du musst es nur noch etwas mathematischer aufschreiben...
> Über Ansätze wäre ich sehr dankbar.
>
> Liebe Grüße
> Andrea
lg
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:22 Mi 06.01.2010 | | Autor: | Drechen |
| Aufgabe | | Beweise, dass jeder Springer Graph bipartit ist |
Hey..
okay.. mir fehlte da halt auch das mathematische.. ich hab das probiert mal etwas in Formeln etc aufzuschreiben aber ich weiß immer noch nicht ob man das als Beweis so stehen lassen kann..
Annahme: Jeder Springer Graph ist bipartit.
Es gibt also zwei Teilmengen U und V
U = (weiße Felder des Schachfeldes)
V = (schwarze Felder des Schachfeldes)
E = die disjunkte Verieningungder zwei nichtleeren Teilmengen (hab gerad unten das mathematische Zeichen nicht gefunden)
Da keine Kanten zwischen U und V bestehen ist meine Annahme richtung und der Graph daher bipartit.
Irgendwie kommt mir das immer noch so vor, dass etwas mathematisches fehlt.. hier ein kleiner Tipp wäre super :)
|
|
|
| |
|
Hallo nochmal,
das sieht doch schon ganz gut aus.
> Beweise, dass jeder Springer Graph bipartit ist
> Hey..
> okay.. mir fehlte da halt auch das mathematische.. ich hab
> das probiert mal etwas in Formeln etc aufzuschreiben aber
> ich weiß immer noch nicht ob man das als Beweis so stehen
> lassen kann..
>
> Annahme: Jeder Springer Graph ist bipartit.
>
> Es gibt also zwei Teilmengen U und V
> U = (weiße Felder des Schachfeldes)
> V = (schwarze Felder des Schachfeldes)
, die disjunkt sind. Es gilt also [mm] U\cap V=\emptyset.
[/mm]
> E = die disjunkte Verieningungder zwei nichtleeren
> Teilmengen (hab gerad unten das mathematische Zeichen nicht
> gefunden)
[mm] E=U\dot{\cup}V
[/mm]
> Da keine Kanten zwischen U und V bestehen
Nicht doch. Alle Kanten verlaufen zwischen U und V.
Das ist gleichbedeutend mit: Keine Kante verläuft innerhalb von U und keine innerhalb von V. Eine ausführlichere Notation findest Du im schon verlinkten Wikipedia-Artikel.
> ist meine Annahme
> richtungig und der Graph daher bipartit.
Da Du die Annahme für den Nachweis doch gar nicht brauchst, würde ich sie weglassen. Unbedingt nötig sind Annahmen nur bei Widerspruchsbeweisen.
> Irgendwie kommt mir das immer noch so vor, dass etwas
> mathematisches fehlt.. hier ein kleiner Tipp wäre super :)
Die verwendeten Zeichen und ihre Schreibweise:
[mm] \emptyset[/mm] \emptyset
[mm] \cap[/mm] \cap
[mm] \cup[/mm] \cup
[mm] \dot{\cup}[/mm] \dot{\cup}
lg
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:07 Mi 06.01.2010 | | Autor: | Drechen |
Hey..
danke für die Erklärung der Zeichen.. ja klar das war irgendwie ein Fehler in der Eile.. eigentlich weiß ich was bipartit heißt ;)
danke, danke!!!
:)
|
|
|
|
