Graphentherorie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
leider komme ich bei diesen Aufgaben, die ich für mein GHR Studium brauche überhaupt nicht weiter. Danke im Vorraus für Euer Bemühen.
25) Beweise: In einem 2-zusammenhängenden Graphen liegen je zwei Kantn auf einem Kreis.
26) Beweise: In einem kritisch 2-zusammenhängenden Graphen gibt es mindestens eine Ecke vom Grade 2
27) Finde zu jedem n>=2 einen kritisch 2-zusammenhängenden Graphen, der mindestens eine Ecke vom Grade n hat.
P.S.: Ich bin sicher, dass das meine Grundschüler später brennend interessieren wird!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:12 Do 23.06.2005 | | Autor: | Zyllyn |
kannst du mir kurz nochmal die Definitionen für 2-zusammenhängend und kritisch 2-zusammenhängend aufschreiben?
danke
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:58 Do 23.06.2005 | | Autor: | fabian1983 |
Def: Ein Graph G mit mindestens drei Ecken heißt 2-zusammenhängend, wenn
er nach Entfernen einer - egal welcher - Ecke zusammenhängend ist.
Def: Sei G ein KRITISCH-2Zusammenhängender Graph; das bedeutet, dass G 2-Zusammenhängend ist, aber kein Graph G-e für [mm] e\inE(G9) [/mm] ist 2-Zusammenhängend
Danke für dein Bemühen!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:26 Do 23.06.2005 | | Autor: | Zyllyn |
> wenn er nach Entfernen einer - egal welcher - Ecke
> zusammenhängend ist.
bist du sicher, das es Ecke heißt, und nicht Kante?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:57 Do 23.06.2005 | | Autor: | fabian1983 |
Laut Matouseks "Dirskrete Mathematik" lautet der Satz:
Ein Graph G mit mindestens drei Ecken heißt 2-zusammenhängend, wenn er nach Entfernen einer - egal welcher! - Ecke zusammenhängend bleibt
Aber ich finde auch das Kante logischer wäre, weil 2-Zusammenhängend ja eigentlich ausdrückt, dass man auf zwei verschiedenen Wegen zu einen Punkt kommen muss!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:05 Do 23.06.2005 | | Autor: | Zyllyn |
also
für mich heißt das - wenn der Graph 2-zusammenhängend ist, dann:
- jede Kante ist Teil eines Kreise (sonst kann ich eine der Ecken wegnehmen und der Graph ist nicht mehr zusammenhängend)
- wenn ich mir zwei beliebige Ecken aussuche, dann gibt es (mindestens) zwei Wege von der einen Ecke zur anderen (sonst könnte ich eine Kante auf dem Weg finden, welche ich entfernen und damit den Zusammenhang zerstören kann)
folglich liegen immer zwei beliebige Ecken auf (mind.) einem Kreis
nun wähle ich eine beliebige Kante (die hat zwei Ecken) und eine angrenzende Kante (also eine zusätzliche Ecke). Nun betrachte ich den Weg den die beiden Kanten bilden, nach der Folgerung von eben (mit den Endpunkten als Ecken) liegen beide Kanten auf einem Kreis.
dann einfach noch ne Kante dran setzen, usw.
nun sollte sich doch eine Art Induktion möglich sein (einfach bis alle Kanten alle sind)
nicht sehr schön formal aber vielleicht reicht es als Beweisidee für 25
zu 26 wenn ich das richtig verstanden habe:
kritisch 2-zusammenhängend - wenn ich eine beliebige Kante (Ecke?) wegnehme dann ist der Graph nicht mehr 2-zusammenhängend
den Beweis würde ich über das Gegenteil führen:
Vorbetrachtung:
Keine Ecke hat den Grad 1 (sonst könnte ich die benachbarte Ecke wegstreichen und der Graph zerfällt sprich nicht mal 2-zusammenhängend)
Beh.:
Jede Ecke hat den Grad 3 oder mehr
folglich mind. 4 Ecken (vollständiger Graph)
eine Ecke weg, immer noch 2-zusammenhängend (wird bei mehr Ecken nicht besser, da der Graph mind. 3-zusammenhängend ist)
ergo, falls es überhaupt kritisch 2-zusammenhängende Graphen gibt (einfach ein Beispiel angeben), dann haben die mindestens eine Ecke mit Grad 2 :)
zu 27
Einfach mit der Ecke mit dem Grad n anfangen. Die n Kanten einzeichnen. Die Ecken mit Grad 1 nun paarweise verbinden (bei n ungerade klappt das nicht immer mit dem paarweise, so erhält eine Ecke den Grad 3, sonst alle Grad 2)
voila :)
alles wiedermal formal unsauber, aber vielleicht hilf es
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:22 Fr 24.06.2005 | | Autor: | fabian1983 |
Vielen Dank,
ich werde jetzt mal versuchen, dass einigermaßen in eine Form zu bringen und dann abgeben!
|
|
|
|
