 |
 |
 |
 |
 |
 |
Startseite » Forum » Vollständige Induktion bei Graph
Vollständige Induktion bei Graph
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie, Vollständig Induktion
 
|
  |
|---|
|
Ich soll für Mathe folgendes tun: vollständige Induktion nach Anzahl der Knoten zu: jeder zusammenhängende Graph mit Knoten hat mindestens Kanten Habe leider keine Ahnung, wie ich anfangen soll...ich brauche die Behauptung für LG Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg." |
|
 |
|
Hallo, jeder zusammenhängende Graph mit Knoten hat mindestens Kanten heißt für jeder zusammenhängende Graph mit () 1 Knoten hat mindestens () 0 Kanten Oder war das nicht deine Frage? Mfg Michael |
 |
|
So in etwa. was mich nur wundert ist - damit kann ich nicht weiter rechnen. Bräuchte also eine formelartige Behauptung und da komme ich nicht drauf. ich muss am Schluss folgendes haben (und weiß nicht recht weiter): Behauptung Dies gilt wegen: Induktionsvoraussetzung Zu zeigen ist: Das gilt wegen: Habe da bisher so was in der Art: Behauptung Jeder zusammenhängende Graph mit 1 Knoten hat mindestens 0 Kanten. daraus folgt Dies gilt wegen: weniger als 0 Kanten kann es nicht geben (weil es logisch ist) Induktionsvoraussetzung daraus folgt Zu zeigen ist: daraus folgt Das gilt wegen: ? kann mir da jemand helfen vielleicht den Ansatz zu berichtigen oder einen das gilt wegen Ansatz zu finden? |
|
|
|
Hallo, zum Induktionsanfang: So kann man das auschreiben. Es gibt keine Menge, deren Elementzahl negativ ist. Also ist der Anfang eher total trivial. Beim Induktionschluss solltest du die Graphentheorie im Auge behalten. Denke daran, dass zusammenhängend ist. Mfg Michael |
|
|
|
Angenommen gibt Die Anzahl der Kanten in Abhängigkeit von der Anzahl der Knoten an. Induktionsbehauptung: Induktionsanfang: wurde ja bereits besprochen. Induktionsschritt: Wenn du zu einem zusammenhängenden (!) Graphen einen Knoten hinzufügst, dann musst du auch mindestens eine Kante hinzufügen um den Knoten mit dem Graphen zu verbinden, das heißt: Da wir das ganze unter Voraussetzung der Induktionsbehauptung betrachten, können wir behaupten: Hast du zufällig noch mehr solcher Aufgaben? Ich würde gerne noch ein paar Induktionsbeweise an Graphen üben. |
|
|
|
Hallo, nein, habe ich nicht. Dazu sind Lehrbücher da. Schau dich mal in eurer Bibliothek um. Ich habe zwar ein Lehrbuch zur Graphentheorie, kann da aber leider im Moment nicht ran. Mfg Michael |
|
|
|
Vielen Dank für die Antwort! Ich habe mich bereits recht gründlich in unserer Hochschulbibliothek umgeschaut. Ich habe das tolle Buch "Algorithmische Graphentheorie" von Voler Turau ausgeliehen, aber leider sind da keine Lösungen für die Aufgaben und ich weiß auch nicht genau ob man die gegebenen Aussagen überhaupt mit vollständiger Induktion beweisen kann. Einige Beispiele aus dem Buch: "Beweisen Sie folgende Aussage: Haben in einem ungerichteten Graphen alle Ecken den Eckengrad 3, so ist die Anzahl der Ecken gerade." "Sei G ein ungerichteter bipartiter Graph mit n Ecken und m Kanten. Beweisen Sie, dass folgende Ungleichung gilt: 4m <= n²" Kann man diese Aussagen mit vollständiger Induktion beweisen? Ich habe mich daran versucht, aber leider konnte ich den Induktionsschritt nicht machen, bzw. fehlte mir der Ansatz. Vollständige Induktion hat mir schon immer sehr gefallen, aber bei Graphen fehlt mir noch die Übung. P.S. Für eine Literaturempfehlung wäre ich auch sehr dankbar. |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1067506
1067037