Beweis um den Hypercube |
21.01.2018, 00:11 | TiMauzi | Auf diesen Beitrag antworten » | ||||
Beweis um den Hypercube Hallo liebe Leute! Für die Diskrete-Mathematik-Vorlesung sitze ich nun seit einiger Zeit vor einer Aufgabe, wo mich schon die Begrifflichkeiten stutzig werden lassen. Momentan ist Thema der Vorlesung Graphen, Spannbäume, Matroide usw. Zur Aufgabe: Es soll um einen sogenannten Hypercube gehen. Es soll bewiesen werden, dass für je zwei Knoten des Hyperwürfels mindestens Pfade zwischen ihnen existieren, die innen-disjunkt sind. Zusätzlich ist der Hinweis gegeben, dass eine Fallunterscheidung zwischen Knotenpaaren, "die keine gleichen Einträge besitzen und solchen, die mindestens einen gleichen Eintrag besitzen", getroffen werden soll. Meine Ideen: Ein Hypercube oder Hyperwürfel ist ja ein Graph, der quasi einen Würfel in verschiedenen Dimensionen darstellt. Er hat Knoten und Kanten. Innen-disjunkt wurde uns so erklärt, dass alle Kanten, die auf den verschiedenen Pfaden zwischen Start- und Endknoten jeweils besucht werden, unterschiedlich sein müssen. Was mich persönlich bisher am meisten verwirrt ist die Aussage im sogenannten "Hinweis". Was ist mit "gleiche Einträge" bzw. überhaupt "Einträge" gemeint. Der Begriff sagt mir im Bezug auf Graphentheorie nicht wirklich etwas. Vielleicht könnt ihr mir helfen? Meine bisherige Idee ist es, den Beweis als Induktion zu führen. So könnte man eventuell die Sache für beweisen und dann für . Wäre dies sinnvoll? Es wäre echt klasse, wenn ihr mir etwas unter die Arme greifen könntet! Danke schon mal im Voraus! |
||||||
21.01.2018, 09:17 | IfindU | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube Was mit gleichen Einträgen gemeint ist: Man kann die Ecken Hypercube als Vektoren darstellen. So kann man auffasen, und . Und ich mag die Idee mit Induktion. Man muss bloss ein wenig aufpassen. |
||||||
21.01.2018, 14:04 | TiMauzi | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube
Kannst du das bitte noch einmal ausführlicher erklären? Was sind denn nun genau die "gleichen Einträge"? |
||||||
21.01.2018, 15:37 | IfindU | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube Jede Ecke ist durch einen Vektor beschrieben. Sei beispielsweise . Dann könnte Startpunkt und Zielpunkt sein. Keine Komponente ist gleich. Wäre der Zielpunkt nun stattdessen , so ist der letzte Eintrag bei Start- und Zielpunkt jeweils . Hier gibt es also einen gleichen Eintrag. |
||||||
21.01.2018, 16:37 | TiMauzi | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube
Okay, in der Vorlesung haben wir die Definition mit Vektoren umgangen sondern von 0-1-Kombinationen gesprochen (weil in Zusammenhang mit Kombinatorik), aber das macht inhaltlich ja keinen Unterschied und ist daher trotzdem schon mal verständlich!
Worauf genau spielst du da an? |
||||||
21.01.2018, 16:58 | IfindU | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube
Bei meiner ersten Induktion hatte ich implizit angenommen, ein Eintrag beim Start- und Zielpunkt wäre gleich. Was mehr ein Fehler meinerseits als ein mathematisches Problem darstellt |
||||||
Anzeige | ||||||
|
||||||
21.01.2018, 17:05 | TiMauzi | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube
Kannst du mir einen Tipp für einen Ansatz geben? |
||||||
21.01.2018, 17:17 | IfindU | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube Du wolltest es doch per Induktion machen. Meine Vorstellung dazu war zu identifizieren. Dann ist . Falls Start- und Endpunkte beide in liegen, so bekommt man sofort per Induktion disjunkte Wege. Man muss sich dann noch einen weiteren basteln. Was nicht schwer ist, weil alle Wege bisher den letzten Eintrag 0 haben. Also nimmt man sich einen Weg mit Einträgen hinten 1. Ähnlich wenn nicht Start- und Endpukt in liegen. |
||||||
21.01.2018, 17:26 | TiMauzi | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube
Was genau soll sein? Diese Darstellung ist mir neu |
||||||
21.01.2018, 17:28 | IfindU | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube Das sollte die Definition sein: . Besser wäre: Sei der Startpunkt mit . Dann definiert man . |
||||||
21.01.2018, 17:39 | TiMauzi | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube
Also kurz zusammengefasst: Der Ansatz ist, die Anzahl der Pfade für einen Hypercube beispielsweise der 2. Dimension (also ein Quadrat) zu nehmen (was 2 Pfade wären) und dann quasi eine Dimension hinzuzufügen, in der dann der jeweils zusätzliche Pfad liegt? Gut, das wäre dann einleuchtend. An welcher Stelle könnte man dann die genannte Fallunterscheidung einbauen? |
||||||
21.01.2018, 17:52 | IfindU | Auf diesen Beitrag antworten » | ||||
RE: Beweis um den Hypercube Versuche doch einfach den Beweis zu führen. Irgendwann wird sie sich anbieten. Oder du findest einen Beweis ohne Fallunterscheidung, was auch schön ist. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|