Induktionsbeweis im Graph |
| 18.04.2017, 18:50 | theoInf | Auf diesen Beitrag antworten » | ||||
| Induktionsbeweis im Graph Wir definieren im Folgenden die Klasse der dreckigen Graphen. Der C3, also ein Kreis auf 3 Knoten, ist dreckig. Jeder dreckige Graph lässt sich durch (ggf. wiederholtes) Anwenden folgender Operation konstruieren: Sei G = (V,E) ein dreckiger Graph, und C = (VC,EC) ein C3. Dann ist G? := (V ? VC,E ? EC) mit |V ? VC| ? 1 ebenfalls dreckig. Zeigen Sie mittels induktivem Beweis, dass Kreise in dreckigen Graphen maximal Länge 3 haben. Hinweis: Als Kreis der Länge k bezeichnen wir eine Folge von paarweise verschiedenen Knoten v1, . . . , vk, sodass die Kante {vi?1, vi} für alle i ? {1, . . . , k} existiert, wobei v0 := vk (und vi 6= vj für alle 1 ? i < j ? k). Meine Ideen: induktionsanfang: C3 ist laut Aufgabenstellung ein kreis mit Länge 3. induktionsvorraussetzung: G sei ein beliebiger dreckiger Graph mit Kreisen von der Länge <= 3. induktionsschluß: von G -> G' wir vereinigen G mit einem C3 |
||||||
| 18.04.2017, 19:13 | Elvis | Auf diesen Beitrag antworten » | ||||
Zu ? viele ? Fragezeichen ? |
||||||
| 18.04.2017, 19:14 | mYthos | Auf diesen Beitrag antworten » | ||||
Kein Schreibfehler! Was ich ein dreckiger Graph? --------------- Und schaue mal dazu, dass die Fragezeichen korrigiert werden. Es sieht so aus, als dass der Text lieblos hingeworfen wurde, das erhöht nicht gerade die Bereitschaft, sich mit deinem Thema zu beschäftigen! mY+ |
||||||
| 18.04.2017, 19:20 | theoINF | Auf diesen Beitrag antworten » | ||||
...Dann ist G' :=( V vereinigt V_c, E vereinigt E_c) mit Betrag von V geschnitten V_c <= 1 ebenfalls dreckig. Zeigen Sie mittels induktivem Beweis, dass Kreise in dreckigen Graphen maximal Länge 3 haben. Hinweis: Als Kreis der Länge k bezeichnen wir eine Folge von paarweise verschiedenen Knoten v1, . . . , vk, sodass die Kante {v_i-1, vi} für alle i in {1, . . . , k} existiert, wobei v0 := vk (und vi ungleich vj für alle 1 <= i < j <= k). tut mir leid fürs einfügen ich bin etwas überfordert 
|
||||||
| 18.04.2017, 19:22 | theoInf | Auf diesen Beitrag antworten » | ||||
glaube das hat keine spezielle Bedeutung(das soll witzig sein) |
||||||
| 18.04.2017, 19:54 | theoInf | Auf diesen Beitrag antworten » | ||||
kann mir nicht bitte jemand einen Tipp geben? |
||||||
| Anzeige | ||||||
|
|
||||||
| 18.04.2017, 22:07 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
https://www.matheboard.de/thread.php?threadid=577355 |
||||||
| 18.04.2017, 22:39 | theoInf | Auf diesen Beitrag antworten » | ||||
|
||||||
| 18.04.2017, 22:53 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Indem du dir mal überlegst, was es für Kreise in G' denn alles für Möglichkeiten gibt! D.h. Fallunterscheidung: 1) Der Kreis enthält nur Knoten/Kanten aus G 2) ... |
||||||
| 18.04.2017, 22:58 | theoInf | Auf diesen Beitrag antworten » | ||||
wenn 1) dann gilt ja die Vorraussetzung 2) der Kreis enthält Knoten/Kanten aus G und C 3) der Kreis enthält nur Knoten/Kanten aus C |
||||||
| 18.04.2017, 23:00 | theoInf | Auf diesen Beitrag antworten » | ||||
2) muss man warscheinlich zum Widerspruch führen aber wie? gibt es noch mehr Möglichkeiten für Kreise in G' ? |
||||||
| 18.04.2017, 23:46 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Präzisiert: Er enthält sowohl Knoten aus als auch aus . Alles andere wird nämlich von 1) und 3) abgehandelt. Wenn nun in diesem 2) ein Kreis Knoten sowohl aus als auch aus enthält, dann muss er ja im Übergang über Knoten aus gehen... |
||||||
| 18.04.2017, 23:48 | theoInf | Auf diesen Beitrag antworten » | ||||
und das ist ja maximal 1, dann kanns irgentwie kein Kreis mehr sein aber ka. wie man das mathematisch formuliert |
||||||
| 18.04.2017, 23:51 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
In der Sache richtig. In der Formulierung: Na gib dir mal Mühe - muss ich den alles vorbeten? |
||||||
| 18.04.2017, 23:54 | theoInf | Auf diesen Beitrag antworten » | ||||
dann würde er doppelt vorkommen im Widerspruch dazu, dass alle Knoten paarweise verschieden sind? |
||||||
| 19.04.2017, 00:01 | theoINf | Auf diesen Beitrag antworten » | ||||
gehe schlafen,abgabefrist ist um 0:00 sowieso abgelaufen, werde dann die Lösung in der Übung sehen, danke trozdem |
||||||
| 19.04.2017, 14:13 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Vermutlich meinst du das richtige. Ich würde es letztendlich in etwa so formulieren, hiervon ausgehend:
Seien sowie zwei Knoten auf diesem Kreis. Auf dem Weg muss somit ein Knoten existieren, ebenso ein Knoten auf dem Rückweg , und es muss gelten, sonst ist es kein Kreis. Dies widerspricht aber Voraussetzung , nach der es höchstens einen Knoten in geben kann. Ergo gibt es gar keinen Kreis, der in diesen Fall 2) fällt. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
