matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieHyperwürfel teilen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Graphentheorie" - Hyperwürfel teilen
Hyperwürfel teilen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Hyperwürfel teilen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:59 Do 18.01.2018
Autor: sven1

Hallo,

kennt sich jemand mit Hyperwürfel aus, bzw. weiß was das ist in der Graphentheorie?

In dieser PDF ist das sehr einfach, schnell und gut erklärt, falls jemand Interesse hat:
[]Hyperwürfel PDF
Ich beziehe mich im Folgenden auf der Notation mit der Hamming Distanz, also insbesondere sind Kapitel 5 und 6 (eigentlich nur 6.1-6.3 einschließlich) von Nöten bzw. interessant (5-6 Seiten). Die Kapitel davor sind möglicherweise spannend um zu verstehen was ein Hyperwürfel ist, aber die PDF ist ja relativ kurz, das geht zügig.

Ich frage mich wie ich einen Hyperwürfel in zwei [mm] $\pm$ [/mm] gleich große Stücke teilen kann. Es hat gewisse Ähnlichkeiten zu der Frage, die ich mit dem Quader gestellt habe, jedoch hier fehlt mir jeglicher Ansatz, wie ich das überhaupt teilen könnte für beliebige Dimensionen $n$. Geschweige vom Beweis.

Beste Grüße und Danke.

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Hyperwürfel teilen: Antwort
Status: (Antwort) fertig Status 
Datum: 18:12 Fr 19.01.2018
Autor: Al-Chwarizmi


> Ich frage mich wie ich einen Hyperwürfel in zwei [mm]\pm[/mm]
> gleich große Stücke teilen kann. Es hat gewisse
> Ähnlichkeiten zu der Frage, die ich mit dem Quader
> gestellt habe, jedoch hier fehlt mir jeglicher Ansatz, wie
> ich das überhaupt teilen könnte für beliebige
> Dimensionen [mm]n[/mm]. Geschweige vom Beweis.


Hallo sven1

ich denke, dass du definieren solltest, was man hier unter
"Stücken" des Hyperwürfels verstehen soll.
Was willst du halbieren - ein Volumen ?
Dann müsstest du bedenken, dass z.B. der 4D-Hyperwürfel
der Kantenlänge a  auch ein vierdimensionales Volumen
vom Betrag  [mm] a^4 [/mm]  hat.

Den 4D-Hyperwürfel könntest du z.B. in zwei zueinander
kongruente 4D-Hyperquader zerlegen, welche jeweils die
paarweise zueinander senkrecht stehenden Kantenlängen
a, a, a, a/2  haben.

LG ,   Al-Chwarizmi



Bezug
                
Bezug
Hyperwürfel teilen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:22 Sa 20.01.2018
Autor: sven1

Alles klar, bist du mit Graphentheorie etwas bewandert?

Wir betrachten im folgenden einen Hyperwürfel. Als Graph ist der $n$ dimensionale Hyperwürfel mit der folgenden Knotenmenge $V:= [mm] \{0,1\}^n$ [/mm] und Kantenmenge $E := [mm] \{ (v,w) | v,w \in V \mbox{ und } |v-w|_H = 1 \}$ [/mm] definiert.
Also wir haben Knoten (Ecken), die als Tupel mit $n$ Einträgen beschrieben werden, und eine Kante zwischen zwei Knoten exisitiert genau dann, falls die Hamming Distanz zwischen diesen beiden Knoten genau $1$ beträgt.
Die Hamming Distanz wird wie folgt definiert:
Für $v := [mm] (v_1,v_2,\ldots, v_n), w:=(w_1,w_2,\ldots,w_n) \in [/mm] V$ ist [mm] $|v-w|_H [/mm] := | [mm] \{ j \in \{1,2,\ldots,n\} | v_j \not= w_j \} [/mm] |$.
Also die Hamming Distanz zwischen zwei Knoten ist die Anzahl der Stellen im Tupel, wo die Einträge von $v$ und $w$ sich unterscheiden, also $|(1,0,0) - [mm] (0,1,0)|_H [/mm] = 2$ zum Beispiel.

Ich möchte nun eine Menge $S [mm] \subseteq [/mm] V$ finden, sodass $V [mm] \backslash [/mm] S$ in zwei "Teile" getrennt wird. Diese Teile sind zusammenhängende Graphen [mm] $G_1$ [/mm] und [mm] $G_2$, [/mm] aber es gibt keine Verbindung, d.h. keine Kante von [mm] $G_1$ [/mm] nach [mm] $G_2$ [/mm] und umgekehrt, also mathematisch geschrieben soll die disjunkte Vereinigung von [mm] $G_1$ [/mm] und $G_$ genau $V [mm] \backslash [/mm] S$ betragen, d.h. $V [mm] \backslash [/mm] S = [mm] G_1 \overset{.}{\cup} G_2$. [/mm]
Im Prinzip ist das ja kein Problem so ein $S$ zu finden, aber ich stelle bestimmte Anfoderungen an die Graphen [mm] $G_1$ [/mm] und [mm] $G_2$, [/mm] ich möchte nämlich dass sie ungefähr gleich groß sind. Sagen wir jetzt der Einfachheit halber, dass sie sich nur um 2-3 Knoten unterscheiden dürfen, also $|| [mm] G_1 [/mm] | - [mm] |G_2| [/mm] | [mm] \le [/mm] 3$.

Zusammenfassend kann man also sagen, dass ich einen "Separator" finden möchte, der den Graph in zwei Teilgraphen separiert, die ungefähr die gleiche Größe haben. Das ganze aber im Hyperwürfel betrachtet. Ich möchte das "induktiv" machen, also als erstes den ganzen Hyperwürfel in 2 Teilgraphen der gleichen Größe teilen, dann die 2 Teilgraphen in der gleichen Art und Weise teilen sodass ich 4 Teilgraphen der gleichen Größe habe, danach 8 etc. also man erhält immer $2$-er Potenzen.
Am Anfang ist es denke ich klar was man als Separator wählt und zwar
$S := [mm] \{ v \in V | | v - (0,0, \ldots, 0)|_H = n/2 \}$, [/mm] damit teile ich den Hyperwürfel in zwei Teilgraphen der gleichen Größe, aber wie gehe ich dann weiter fort?
Dann müsste ich ja einen Knoten aus $S$ nehmen und weitere Knoten dazu um den zu einen Separator zu erweitern, der die jeweiligen beiden Teilgraphen wieder in zwei "gleich große" Teile separiert, sodass ich $4$ "gleichgroße" Teilgraphen habe.
Aber welche Knoten muss ich zu $S$ hinzufügen um den gewünschten Separator zu finden?

Ich habe jetzt eigt. alle theorethischen Grundlagen eingeführt um es zu verstehen. Ich hoffe es reicht aus, sonst meldet euch gerne, möglicherweise habe ich was vergessen. :(

Danke auf jeden Fall schonmal.

Beste Grüße
Sven

Bezug
                        
Bezug
Hyperwürfel teilen: Antwort
Status: (Antwort) fertig Status 
Datum: 16:10 Sa 20.01.2018
Autor: Al-Chwarizmi


> Alles klar, bist du mit Graphentheorie etwas bewandert?

Naja, vor (vielen) Jahren habe ich mich damit sogar sehr
ausführlich beschäftigt, insbesondere auch mit dem (damals
noch zu lösenden) "Vierfarbenproblem". Auch zu Hamming-
Distanzen und deren Optimierung für ein Codierungssystem
habe ich (für eine Industriefirma) eine Arbeit verfasst.

So wie mir scheint, geht es bei deiner Frage im Prinzip um
den (schrittweisen, induktiven) Aufbau der "Hyperwürfel-Graphen".
Mit so etwas wie "Volumina" hat dies kaum zu tun.

Der HW  [mm] H_0 [/mm]  besteht aus einem einzigen Knoten A und
einer leeren Kantenmenge.

Daraus gewinnt man den "eindimensionalen" HW  [mm] H_1 [/mm] , indem
man zur Knotenmenge A einen "Klon"  A'  erzeugt. Die
Vereinigung von A und A'  ergibt die Knotenmenge von [mm] H_1. [/mm]
Die Kantenmenge von [mm] H_1 [/mm]  erhält man als Vereinigungsmenge
der Kantenmengen von beiden Teilgraphen und zusätzlich
je einer Kante von jedem Knoten von A zum entsprechenden
"Zwillings-" Knoten in A'.

[mm] H_1 [/mm] hat demzufolge genau zwei Knoten (nennen wir sie A und B)
und eine einzige Kante zwischen diesen beiden Punkten. Graphisch
hat man also eine einfache Strecke [mm] \overline{AB}. [/mm]

[mm] H_2 [/mm] erhält man aus [mm] H_1 [/mm] nach derselben Methode. Insgesamt haben
wir dann in [mm] H_2 [/mm]  4 Knoten und 1+1+2=4 Kanten.
Graphisch:  ein Quadrat mit seinen 4 Ecken und 4 Kanten.

Was du also mit "S" (oder "Separator") bezeichnest, scheint einfach
die Menge jener [mm] 2^n [/mm] Kanten zu sein, welche die Knoten eines Hyperwürfels [mm] H_n [/mm]
mit ihren jeweiligen "Zwillingsknoten" in [mm] H_n' [/mm]  verbinden.

Wie du nun deine ganzen Überlegungen im Detail formulieren
sollst, musst du dir natürlich noch zurechtlegen.

LG ,   Al-Chw.


Bezug
                                
Bezug
Hyperwürfel teilen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:24 So 21.01.2018
Autor: sven1

Jaein, also mit der Aussage zum Aufbau des Hyperwürfels hast du vollkommen recht. So kann man den auch einführen. Mit Volumina hat das alles in der Tat recht wenig zu tun, aber habe das einfach so "umformuliert" sodass andere Personen eventuell auch mit überlegen können.

Du beschreibst einen Separator, der jedoch aus Kanten besteht ($S [mm] \subseteq [/mm] E$), ich benötige einen Knoten Separator, also wo $S [mm] \subseteq [/mm] V$.
Ehrlich gesagt habe ich gar nicht an den induktiven Aufbau aus Hyperwürfeln gedacht, weil mein betreuender Professor das anders, also mit Tupeln der Länge $n$ [mm] ($\{0,1\}^n$) [/mm] und der Hamming Distanz, eingeführt hat. Das ist ein bisschen blöd zu visualisieren und deswegen war mir nicht ganz klar wie man es trennt. :)

Nichtsdestotrotz könnte ich nun dem Separator einen Knoten von der Kante hinzufügen, die du beschrieben hattest. Das mache ich dann für jede Kante, dann habe ich einen Knoten Separator. Und da ich ja wiederum kleinere Hyperwürfel erhalte kann ich das gleiche induktiv durchführen und damit den Separator $S$ in jedem Schritt vergrößern bzw. erweitern.

Also habe ich beispielsweise [mm] $H_n$ [/mm] gegeben für ein $n [mm] \in \IN$, [/mm] dann konstruiere ich [mm] $S_1$ [/mm] auf die bereits besprochene Methode. Daraus ergeben sich zwei [mm] $H_{n-1}$, [/mm] die nun durch [mm] $S_1$ [/mm] voneinander "geteilt" werden, dann separiere ich beide [mm] $H_{n-1}$ [/mm] und füge die Knoten jeweils [mm] $S_1$ [/mm] hinzu und erhalte ein [mm] $S_2$, [/mm] dass den ursprünglichen Hyperwürfel [mm] $H_n$ [/mm] in vier Hyperwürfel [mm] $H_{n-2}$ [/mm] teilt. Führt man das induktiv fort, dann erhält man [mm] $S_{n-1}$, [/mm] dass den ursprünglichen Hyperwürfel [mm] $H_n$ [/mm] in [mm] $2^{n-1}$ [/mm] Hyperwürfel [mm] $H_{n-(n-1)} [/mm] = [mm] H_1$ [/mm] separiert.

Danke das hilft mir an sich schon mal viel weiter. Jetzt muss ich das noch auf meine Problemstellung übertragen und die Theorie, die ich in meiner Arbeit eingeführt habe.

Bezug
                                        
Bezug
Hyperwürfel teilen: Separator nur aus Kanten
Status: (Antwort) fertig Status 
Datum: 13:47 So 21.01.2018
Autor: Al-Chwarizmi


> Du beschreibst einen Separator, der jedoch aus Kanten
> besteht ([mm]S \subseteq E[/mm]), ich benötige einen Knoten
> Separator, also wo [mm]S \subseteq V[/mm].


Hallo Sven,

nach der []Definition , die ich bei Wikipedia
gefunden habe, kann ein Separator durchaus auch nur aus
Kanten bestehen.
Der von mir vorgeschlagene Separator ist in dem Sinne
ein "minimaler" Separator, dass er einen Hyperwürfel
der Dimension n+1 exakt in zwei kongruente Hyperwürfel
der Dimension n aufspaltet. Das Wegnehmen dieser
Verbindungskanten ist dazu notwendig - aber jede
zusätzliche Entfernung irgendeines Knotens würde
wenigstens einen der HW zerstören.
Bei einem konkreten HW einer Dimension n (mit n≥2) gibt
es natürlich verschiedene (aber zueinander isomorphe)
Möglichkeiten, einen solchen Separator auszuwählen.

LG ,   Al-Chw.

Bezug
                                                
Bezug
Hyperwürfel teilen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:36 So 21.01.2018
Autor: sven1

Ja genau, es gibt zwei Arten von Separatoren. Knoten oder Kanten Separatoren. Ich benötige nur Knoten Separatoren.

Das stimmt das das Entfernen des Knoten den Hyperwürfel zerstören würde, aber im Kontext meiner Forschung spielt das keine wirkliche Rolle. Ich benötige nicht das Gebilde eines Hyperwürfel, sondern nur dass die Anzahl der Knoten in beiden Teilgraphen, die durch den Separator entstanden sind, (ca.) gleich groß sind. Das wäre hier ja der Fall.

Sorry, dass es zu Verwirrungen kommt, da ich nicht die komplette Theorie meiner Arbeit hier wiedergegeben habe, aber das sind 5-10 Seiten, ich glaube das würde den Rahmen sprengen.
Aber ich glaube du hast mir durch die Erklärung zum induktiven Aufbau des Hyperwürfels sehr geholfen, ich werde sehen ob es hilft und sich gut anwenden lässt. Ich bin aber zuversichtlich.

Im Prinzip möchte ich folgendes machen (ganz unformal hingeschrieben): Ich suche einen Separator für einen Graph, sodass die entstandenen Teilgraphen und der Separator alle "gleich groß" (im Sinne von Anzahl Knoten) sind. Diese Eigenschaft nennt man "isoperimetrisch".

Falls die Teilgraphen "größer" werden, dann wird der Separator "kleiner" und falls der Separator "größer" wird, dann werden die Teilgraphen "kleiner". Man muss genau das Gleichgewicht finden.

Die Aufgabe ist nun einen minimalen isoperimetrischen Separator (im Sinne von Anzahl Knoten) zu finden. Dazu muss man ihn natürlich erst finden und anschließend beweisen, dass er minimal ist. Ich habe dazu mit dem Professor eine neue Theorie ausgearbeitet, die eine wesentlich einfachere Methode zur Beweisführung bietet.

Für 2 und 3 dimensionale Gitter habe ich das Problem zum Beispiel bereits gelöst. Bei Hyperwürfel habe ich noch einige Probleme.
Aber der Prof. hat auch gesagt dass es sehr schwer sein würde das Problem für Hyperwürfel zu lösen. Anscheinend haben da sehr gute Mathematiker Jahrzehnte für gebraucht und die Ausarbeitungen sind sehr kompliziert und richtig lang, aber er hat die Vermutung, dass unsere neue Beweismethode alles "besser" machen kann. Mal sehen. Aber für die Gitter hat es gut geklappt, der Beweis ist dadurch auch schöner und eleganter geworden.

Danke auf jeden Fall!

Bezug
        
Bezug
Hyperwürfel teilen: Antwort
Status: (Antwort) fertig Status 
Datum: 12:51 So 21.01.2018
Autor: HJKweseleit

Die einfachste Mgl.:

Wenn die Eckkoordinaten alle nur die Werte 0 und 1 haben, ersetzt du für eine (einzige) Dimension jede 1 durch den Wert 1/2 (1. Würftelhälfte) und bei der 2. Würfelhälfte für die selbe Dimension jede 0 durch 1/2.

Bezug
                
Bezug
Hyperwürfel teilen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:27 So 21.01.2018
Autor: sven1

Wie meinst du das?

Die Knoten sind Elemente aus [mm] $\{0,1\}^n$, [/mm] also Tupel der Länge $n$, wo jeder Eintrag entweder 0 oder 1 ist. Sorry, verstehe deinen Ansatz nicht. Falls ein Eintrag $1/2$ wäre, dann wäre es kein Knoten mehr. Also zumindest in dieser Definition.

Bezug
                        
Bezug
Hyperwürfel teilen: Antwort
Status: (Antwort) fertig Status 
Datum: 00:41 Mo 22.01.2018
Autor: HJKweseleit

Ich dachte an so etwas - falls es das ist, was du suchst.

[Dateianhang nicht öffentlich]

Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
Bezug
                                
Bezug
Hyperwürfel teilen: keine neuen Knoten !
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:12 Mo 22.01.2018
Autor: Al-Chwarizmi

Hallo HJK,

du hast hier das schön illustriert, was ich in meiner
allerersten Antwort auch gedacht hatte.

Sven sucht aber offensichtlich etwas anderes. Neue
zusätzliche Knoten auf bisherigen Kanten einzuführen
scheint bei der Zerlegung in Teilgraphen und "Separator"
nicht vorgesehen zu sein.

LG ,   Al-Chwarizmi

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]