Hallo!

Wir haben in der Uni folgenden Aufgabe bekommen:

Beweisen Sie:
Sei G=(V,E) ein ungerichteter, zusammenhängender Graph und e (element) E eine Kante, die auf keinem Kreis in G liegt: Dann ist e in jedem minimalen Spannbaum von G enthalten.

Wenn man darüber nachdenkt, ist das ja auch ganz logisch so. Mein Problem ist nur, dass ich das nicht in einem formalen Beweis ausdrücken kann. Vielleicht könnt ihr mir da ein paar Tips geben, wie ich da in etwa vor gehen könnte.

Danke schon mal!

Nur mal so gefragt:

Denkst Du, ein Informatiker weiss überhaupt wovon Du sprichst?

Ich habe mal ein paar Semester Mathematik absolviert und habe da auch mal Graphentheorie gehabt, habe aber die Unterlagen momentan nicht greifbar.

*biglol* Du sprichst mir aus der Seele!!!
Ach kommt, er sucht hilfe, und vertraut uns sein Problem an! Ich find das toll! Obwohl ich leider bei disem Problem passen muss

Die Problemstellung tönt interessant, aber ich habe leider auch absolut keine Ahnung was damit gemeint ist resp. was ein Graph ist. Vielleicht Graf falsch geschrieben? Das würde bedeuten:
G=(V,E) entspricht Graf=(Verlobte, Erzprinz) ?

Also mal für alle Nicht-Mathematiker:

einen (2-dimensionalen) ungerichteten, zusammenhängenden Grafen G=(V,E) seht ihr im angehängten Bild. Dabei entspricht die Menge V den roten Eckpunkten und die Menge E den blauen Kanten (sorry, thorsten_upb, für die laienhafte Erklärung, aber die Informatiker sollen doch verstehen, wovon wir reden )

Mit einem Kreis ist einfach ein in sich geschlossener Linienzug gemeint. Ein Spannbaum ist eine minimale Anzahl von Kanten, die den Graphen "aufspannt".

Man muss jetzt zeigen, dass eine Kante, die nicht auf einem Kreis liegt (also eine, die eine "freie" Ecke hat, z.b. die ganz unten) in jedem minimalen Spannbaum enthalten sein muss.

Also eigentlich ist das doch gar keine schwere Aufgabe, wenn man es über die Mengenlehre macht:

Wenn die unterste Ecke mit dem Spannbaum abgedeckt werden muss, dann muss mindestens eine Kante in dem Spannbaum enthalten sein, die wiederum diese besagte Ecke als Element enthält und das ist ja gerade nur diese eine Kante e (da es ja keinen Kreis gibt!)

Ich hoffe, dass das einigermassen verständlich war. Ansonsten würde ich Dir, thorsten_upb, mal empfehlen deine Mit-Studenten zu fragen, da deren Graphentheorie wesentlich präsenter ist als meine Erinnerungen.

Bahnhof

Grs Jürg

Bei mir Hauptbahnhof

@remix
danke für die erklärung...
.
.
.
.
.
....aber ich schliese mich meinen vorrednern an

Greezli HAMSTER

Zumal ich auch nur Bahnhof verstehe bitte noch eine Info: Wozu ist das Ganze eigentlich gut?

Damit kann man z.B. beweisen, dass max. vier Farben genügen um eine bel. Landkarte einzufärben, ohne dass zwei benachbarte Länder die gleiche Farbe haben.
Oder man kann berechnen wieviele Kugeln maximal in einen Hohlkörper beliebiger Form passen (interessant für die Chemie, bzw. Kristallographie.

Mathematik ist die Grundlage aller technischen Wissenschaften (einschliesslich Informatik) und ist nicht immer auf den ersten Blick offensichtlich.

remix

Wow, das find ich wieder mal Klasse. Da kommt jemand mit einer Frage aus der Mathewelt und die wird dann noch beantwortet. Ich find dieses Board klasse