Beweis um den Hypercube

21.01.2018, 00:11

TiMauzi

Beweis um den Hypercube

Meine Frage:
Hallo liebe Leute! smile

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 $\begin{eqnarray*} Q_k \end{eqnarray*}$ gehen. Es soll bewiesen werden, dass für je zwei Knoten $\begin{eqnarray*} xy \end{eqnarray*}$ des Hyperwürfels mindestens $\begin{eqnarray*} k \end{eqnarray*}$ 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 $\begin{eqnarray*} 2^d \end{eqnarray*}$ Knoten und $\begin{eqnarray*} d \cdot 2^{d-1} \end{eqnarray*}$ 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 $\begin{eqnarray*} Q_1 \end{eqnarray*}$ beweisen und dann für $\begin{eqnarray*} Q_{n+1} \end{eqnarray*}$ . Wäre dies sinnvoll?

Es wäre echt klasse, wenn ihr mir etwas unter die Arme greifen könntet! Danke schon mal im Voraus! smile

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 $\begin{eqnarray*} Q_1 = \{ 0,1 \} \end{eqnarray*}$ auffasen, $\begin{eqnarray*} Q_2 = \{ (0,0), (1,0), (0,1), (1,1)\} = \{0,1\} \times\{0,1\} \end{eqnarray*}$ und $\begin{eqnarray*} Q_k = \operatorname*{\times}_{l=1}^k \{ 0, 1\} \end{eqnarray*}$ .

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

Zitat:

Original von IfindU
Was mit gleichen Einträgen gemeint ist: Man kann die Ecken Hypercube als Vektoren darstellen. So kann man $\begin{eqnarray*} Q_1 = \{ 0,1 \} \end{eqnarray*}$ auffasen, $\begin{eqnarray*} Q_2 = \{ (0,0), (1,0), (0,1), (1,1)\} = \{0,1\} \times\{0,1\} \end{eqnarray*}$ und $\begin{eqnarray*} Q_k = \operatorname*{\times}_{l=1}^k \{ 0, 1\} \end{eqnarray*}$ .

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 $\begin{eqnarray*} k = 3 \end{eqnarray*}$ . Dann könnte Startpunkt $\begin{eqnarray*} ( 0, 0, 1) \end{eqnarray*}$ und Zielpunkt $\begin{eqnarray*} (1,1, 0) \end{eqnarray*}$ sein. Keine Komponente ist gleich. Wäre der Zielpunkt nun stattdessen $\begin{eqnarray*} (1,1,1) \end{eqnarray*}$ , so ist der letzte Eintrag bei Start- und Zielpunkt jeweils $\begin{eqnarray*} 1 \end{eqnarray*}$ . Hier gibt es also einen gleichen Eintrag.

21.01.2018, 16:37

TiMauzi

Auf diesen Beitrag antworten »

RE: Beweis um den Hypercube

Zitat:

Original von IfindU
Jede Ecke ist durch einen Vektor beschrieben. Sei beispielsweise $\begin{eqnarray*} k = 3 \end{eqnarray*}$ . Dann könnte Startpunkt $\begin{eqnarray*} ( 0, 0, 1) \end{eqnarray*}$ und Zielpunkt $\begin{eqnarray*} (1,1, 0) \end{eqnarray*}$ sein. Keine Komponente ist gleich. Wäre der Zielpunkt nun stattdessen $\begin{eqnarray*} (1,1,1) \end{eqnarray*}$ , so ist der letzte Eintrag bei Start- und Zielpunkt jeweils $\begin{eqnarray*} 1 \end{eqnarray*}$ . Hier gibt es also einen gleichen Eintrag.

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! Freude

Zitat:

Original von IfindU
Und ich mag die Idee mit Induktion. Man muss bloss ein wenig aufpassen.

Worauf genau spielst du da an? geschockt

21.01.2018, 16:58

IfindU

Auf diesen Beitrag antworten »

RE: Beweis um den Hypercube

Zitat:

Original von TiMauzi
Worauf genau spielst du da an? geschockt

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 Big Laugh

21.01.2018, 17:05

TiMauzi

Auf diesen Beitrag antworten »

RE: Beweis um den Hypercube

Zitat:

Original von IfindU
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 Big Laugh

Kannst du mir einen Tipp für einen Ansatz geben? verwirrt

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 $\begin{eqnarray*} \widetilde Q_{k-1} = Q_{k-1} \times \{ 0 \} \end{eqnarray*}$ zu identifizieren. Dann ist $\begin{eqnarray*} \widetilde Q_{k-1} \subset Q_k \end{eqnarray*}$ . Falls Start- und Endpunkte beide in $\begin{eqnarray*} \widetilde Q_{k-1} \end{eqnarray*}$ liegen, so bekommt man sofort per Induktion $\begin{eqnarray*} k-1 \end{eqnarray*}$ 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 $\begin{eqnarray*} \widetilde Q_{k-1} \end{eqnarray*}$ liegen.

21.01.2018, 17:26

TiMauzi

Auf diesen Beitrag antworten »

RE: Beweis um den Hypercube

Zitat:

Original von IfindU
Du wolltest es doch per Induktion machen. Meine Vorstellung dazu war $\begin{eqnarray*} \widetilde Q_{k-1} = Q_{k-1} \times \{ 0 \} \end{eqnarray*}$ zu identifizieren. Dann ist $\begin{eqnarray*} \widetilde Q_{k-1} \subset Q_k \end{eqnarray*}$ . Falls Start- und Endpunkte beide in $\begin{eqnarray*} \widetilde Q_{k-1} \end{eqnarray*}$ liegen, so bekommt man sofort per Induktion $\begin{eqnarray*} k-1 \end{eqnarray*}$ 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 $\begin{eqnarray*} \widetilde Q_{k-1} \end{eqnarray*}$ liegen.

Was genau soll $\begin{eqnarray*} \widetilde Q_{k-1} \end{eqnarray*}$ sein? Diese Darstellung ist mir neu geschockt

21.01.2018, 17:28

IfindU

Auf diesen Beitrag antworten »

RE: Beweis um den Hypercube
Das sollte die Definition sein: $\begin{eqnarray*} \widetilde Q_{k-1} = Q_{k-1} \times \{ 0 \} \end{eqnarray*}$ .

Besser wäre: Sei $\begin{eqnarray*} S \in Q_k \end{eqnarray*}$ der Startpunkt mit $\begin{eqnarray*} S = ( s_1, s_2, \ldots, s_k) \end{eqnarray*}$ . Dann definiert man $\begin{eqnarray*} \widetilde Q_{k-1} = Q_{k-1} \times \{ s_k\} \end{eqnarray*}$ .

21.01.2018, 17:39

TiMauzi

Auf diesen Beitrag antworten »

RE: Beweis um den Hypercube

Zitat:

Original von IfindU
[...] Dann ist $\begin{eqnarray*} \widetilde Q_{k-1} \subset Q_k \end{eqnarray*}$ . Falls Start- und Endpunkte beide in $\begin{eqnarray*} \widetilde Q_{k-1} \end{eqnarray*}$ liegen, so bekommt man sofort per Induktion $\begin{eqnarray*} k-1 \end{eqnarray*}$ disjunkte Wege. Man muss sich dann noch einen weiteren basteln. [...] Also nimmt man sich einen Weg mit Einträgen hinten 1.

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.

Neue Frage »

Antworten »

Beweis um den Hypercube

Verwandte Themen