www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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


Alle Foren
Status vor 1h 07m 7. Diophant
UAnaR1FunkStetig/Stetigkeit im Nullpunkt
Status vor 2h 07m 2. Diophant
DeuGramm/Bindewörter _weil
Status vor 15h 06m 4. angela.h.b.
STrigoFktn/Cosinus und Arc Cosinus
Status vor 16h 28m 8. matux MR Agent
SPhy/Formel für Widerstand
Status vor 1d 13h 16m 1. Prospekthuellen
UStoc/Galton-Watson mit max. Höhe
^ Seitenanfang ^
www.vorhilfe.de