0
Wegen dem genau wenn müssen wir hier eine Biimplikation zeigen, die Implikation -> verstehe ich, die Summe von jedem Knoten Grad aus einem Graph ist ja 2|E|. Aber die andere Seite muss doch nicht gelten, wenn man jetzt ein Graph mit den zwei Teilgraphen eines Baumes mit 3 Knoten und $K_2$, dann wird die Rechte Bedingung erfüllt, aber es handelt sich nicht um einen Baum. Zu der Aufgabe gibt es auch lösungen (2. Bild), aber ich verstehe die Induktion nicht. Könnte mir bitte jemand erklären wie ich die andere Seite zeige und was mein Denkfehler ist.
Diese Frage melden
gefragt
henry dutter
Schüler, Punkte: 135
Schüler, Punkte: 135
Schau erstmal, dass Du die Aussage verstehst. Wenn Du einen Beispielgraph diskutieren willst, lade ein Bild hoch und alle Angaben, die in dem Satz vorkommen, dazu. Beachte auch, dass da nicht steht, dass jeder Graph, der die rechte Seite erfüllt, ein Baum ist. Zur Induktion: Fang und sag konkret, wie weit Du kommst, und was konkret Deine erste Frage ist. Ind. Anf. erledigt?
─
mikn
05.10.2023 um 12:12
1. Das heißt Äquivalenz und nicht Biimplikation.
2. Da steht nur, dass es einen Baum gibt, nicht dass jeder Graph, der das erfüllt, ein Baum ist. Das ist ein großer Unterschied. Bitte immer genau lesen. ─ cauchy 05.10.2023 um 12:16
2. Da steht nur, dass es einen Baum gibt, nicht dass jeder Graph, der das erfüllt, ein Baum ist. Das ist ein großer Unterschied. Bitte immer genau lesen. ─ cauchy 05.10.2023 um 12:16
"Biimplikation" ist (für mich) eine ungewöhnliche Bezeichnung, scheint aber von manchen verwendet zu werden-
─
mikn
05.10.2023 um 12:19
Okay. Konnte ich nichts zu finden.
─
cauchy
05.10.2023 um 12:21
Wir haben gelernt das genau dann wenn, eine Biimplikation bedeutet. Ich verstehe halt nicht was mit der Induktion gezeigt werden soll. Mein Bsp. war falsch, ich meinte einen Graphen der die Teilgraphen $K_3$ und $K_2$ hat, da gibt es ja 5 Knoten und 4 kanten. Und wir nennen das Biimplikation im Studium.
─
henry dutter
05.10.2023 um 14:33
Folge den Hinweisen, damit Hilfe ansetzen kann. Falls notwendig, Induktion wiederholen. Aussagen sorgfältig und vollständig notieren.
─
mikn
05.10.2023 um 15:09
Ich habe, wie bereits gesagt, es so verstanden, das wenn die Summe gilt, es ein Baum sein muss und er mit der Induktion das gezeigt werden soll. Dazu habe ich ja ein gegenbeispiel gezeigt mit dem Graph der die Komponenten $K_3$ und $K_2$ hat (Der sieht ja eindeutig aus). Aber mir wurde ja hier gesagt, das es da nicht steht, deshalb wollte ich fragen was sonst mit der Induktion gezeigt werden soll.
─
henry dutter
05.10.2023 um 16:09
Ein Beispiel wäre ein guter Einstieg, aber bis jetzt hast du das noch nicht vorgelegt (Hinweise dazu oben). Und "mir wurde gesagt..." heißt, du hast es selbst noch nicht verstanden. Da könnte das Beispiel helfen... genug Tipps gegeben...
─
mikn
05.10.2023 um 16:40
Also, am besten, man schreibt sich die "\(\Leftarrow\)"-Richtung mal sauber, als eigenen Satz formuliert, auf:
Satz:
Sei \(d_1,\ldots,d_n \in \mathbb{N}\) eine Folge positiver, natürlicher Zahlen.
Sei \(\displaystyle \sum_{i=1}^n d_i = 2n-2\).
Dann gibt es einen Baum mit der Knotenmenge \( \{v_1,\ldots,v_n\}\) und \(\mbox{deg}(v_i)=d_i\).
Dass es da noch andere Nicht-Baum-Graphen mit n Knoten und \(\mbox{deg}(v_i)=d_i\) gibt, ist egal. Diese Nicht-Baum-Graphen interessieren nicht, denn nichts davon steht im obigen Satz. Im Satz geht es nur um Bäume.
─ m.simon.539 05.10.2023 um 18:50
Satz:
Sei \(d_1,\ldots,d_n \in \mathbb{N}\) eine Folge positiver, natürlicher Zahlen.
Sei \(\displaystyle \sum_{i=1}^n d_i = 2n-2\).
Dann gibt es einen Baum mit der Knotenmenge \( \{v_1,\ldots,v_n\}\) und \(\mbox{deg}(v_i)=d_i\).
Dass es da noch andere Nicht-Baum-Graphen mit n Knoten und \(\mbox{deg}(v_i)=d_i\) gibt, ist egal. Diese Nicht-Baum-Graphen interessieren nicht, denn nichts davon steht im obigen Satz. Im Satz geht es nur um Bäume.
─ m.simon.539 05.10.2023 um 18:50
Entschuldigung, die zweite Implikation habe ich falsch verstanden, vielen Dank. Versuch mich jetzt noch mal an die Induktion heran.
─
henry dutter
05.10.2023 um 19:22
@simon Meine Idee war, dass der Frager sich erstmal selbst mit der Aussage auseinandersetzt. Dieses Vorlesen-aus-Büchern und das Denken abnehmen bringt doch nichts. Und es war nun klar was passiert: Er setzt sich nicht mehr mit seinem Beispiel und der Aussage auseinander, wozu auch? Also gleich ran an die Induktion. Schade, Chance vertan.
─
mikn
05.10.2023 um 19:46
@Mikn: Naja, wenn man's anders macht, bleibt's halt nebulös.
─
m.simon.539
05.10.2023 um 20:25
@simon Man sollte als Helfer auch abwarten können. Und ob es nun weniger nebulös ist, werden wir ja sehen.
─
mikn
05.10.2023 um 20:34