www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 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
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - Rechteck (Grid) halbieren
Rechteck (Grid) halbieren < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rechteck (Grid) halbieren: Beweisidee
Status: (Frage) beantwortet Status 
Datum: 22:33 Di 01.08.2017
Autor: TriMan

Hallo zusammen,

ich habe vielleicht eine blöde und recht einfach zu lösende Aufgabe, aber ich komme einfach nicht drauf. Vielleicht könnt ihr mir einen kleinen Denkanstoß geben, das würde mir reichen. :)

Ich stelle mir die Frage wie man ein Rechteck am besten halbiert. Ich denke die intuitive Antwort ist möglicherweise auch die Richtige. Ich würde sagen, dass man  bezüglich der längsten Seite des Rechtecks in der Mitte halbiert durch eine Gerade. Aber ich kriege es einfach nicht bewiesen, dass es keinen anderen kürzeren Separator bzw. Trenner gibt. Vielleicht ist auch die Annahme falsch.

In Graphentheorie ausgedrückt: Wenn ich ein $n [mm] \times [/mm] m$ Grid habe und $n > m$, also mehr Zeilen als Spalten habe, dann würde ich bei [mm] $\bruch{n}{2}$ [/mm] das Grid in 2 ca. gleich große Stücke teilen, je nachdem ob $n$ gerade oder ungerade ist. Also mein Separator bzw. Trenner $S$ wäre definiert als $S := [mm] \{(\bruch{n}{2},1), (\bruch{n}{2},2), \ldots, (\bruch{n}{2},m)\}$. [/mm]

Auf diese Teilaussage beruhen einige andere Beweise von mir, ich hoffe nur dass meine Annahme nun nicht falsch ist.

Also stimmt das die Aussage überhaupt? Wenn ja, wie könnte ich beweisen, dass es keinen kürzeren geben kann? Habe es schon über Induktion versucht, sah vielversprechend aus, aber anscheinend bin ich einfach zu dumm..

Besten dank schon jetzt einmal!

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

        
Bezug
Rechteck (Grid) halbieren: Antwort
Status: (Antwort) fertig Status 
Datum: 00:50 Mi 02.08.2017
Autor: leduart

Hallo
ist deine Frage nach der kürzesten Teilstrecke? und willst du wieder Rechtecke, oder zumindest kongruente Teilstücke. dann ist das die einzige Lösung .
Aber was du genau willst ist unklar, warum ist die Teilung der kürzeren Seite nicht erlaubt?
Gruß leduart

Bezug
                
Bezug
Rechteck (Grid) halbieren: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:33 Mi 02.08.2017
Autor: TriMan

Ne, die Erklärung mit dem Rechteck sollte nur zur vereinfachten Darstellung dienen. Die Erläuterungen bezüglich der Graphentheorie sind das eigentliche Problem. Ich möchte einen möglichstes kleinen Separator für ein rechtwinkliges Grid, wir können auch annehmen, dass es ein $n [mm] \times [/mm] (2n)$ Grid ist, finden, der das Grid aber in zwei gleich große "Sub"-Grids bzw. Stücke separiert/teilt. Ich behaupte, dass dieser Separator der, den ich als $S$ definiert habe, ist. Jedoch fehlt mir der Beweis warum das der kleinstmöglichste ist. Mit kleinstmöglichste meine ich bzgl. der Anzahl Knoten von $S$, also hier $|S| = m$ bzw. in dem Grid $n [mm] \times [/mm] (2n)$ ist $|S| = n$.

Zu zeigen wäre, dass es keinen Separator $S'$ gibt mit $|S'| < m$ bzw. $|S'| < n$, der das grid "halbiert", also wo di resultierenden "Sub"-Grids oder Teilgraphen ca. die Hälfte der Knoten des ursprünglichen Graphen haben.

Bezug
                        
Bezug
Rechteck (Grid) halbieren: Antwort
Status: (Antwort) fertig Status 
Datum: 11:44 Mi 02.08.2017
Autor: leduart

Hallo
Wenn du ein rechteckiges Grid teilen willst, z. B. n*2n, bekommst du pro Rechteck im Inneren einen zusätzlichen Knoten, egal wie du teilst das 2 am Rand.
wenn du also die kurze Seite teilst bekommst du n+2 neue Knoten, wenn du die lange teilst, 2n+2 also mehr.
oder habe ich dich falsch verstanden.
durch eine Zeichnung ist die Anzahl der neuen Knoten leicht zu sehen, dazu muss n ja nicht groß sein?
Gruß ledum

Bezug
                                
Bezug
Rechteck (Grid) halbieren: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:28 Mi 02.08.2017
Autor: TriMan

Ja, ca. Also hier https://de.wikipedia.org/wiki/Datei:Grid_separator.svg sieht man zum Beispiel einen Grid Separator für $5 [mm] \times [/mm] 8$. Okay, ist kein $n [mm] \times [/mm] 2n$ Grid, aber vielleicht gibt es die Idee weiter. In der Zeichnung ist nur ein Separator gekennzeichnet $S$. Ich suche jedoch einen Separator, der minimal (bezüglich der Anzahl der Knoten, wie du bereits geschrieben hast) ist und dessen Teilgraphen bzw. "Sub"-Grids (hier $A$ und $B$) ca. gleich groß sind. Wären jetzt hier $9$ anstatt $8$ Spalten gewesen, dann wäre $S$ genau, die $5$ Spalte gewesen, also ca. wie hier eingezeichnet. Vielleicht zur Einfachheit betrachten wir nur Grids der Größe $n [mm] \times [/mm] 2n$ wo $n$ ungerade ist. Warum (Beweisidee) ist dann der intuitive Separator der kleinste? Also wenn man sich in dem Link das Grid anschaut und bei $A$ einfach noch eine Spalte hinzufügt stellt sich mir die Frage warum $S$ dann der minimalste ist. Also klar, mir ist es auch logisch etc. aber ich suche einen Beweis dazu. Ich kann das ja nicht einfach so annehmen. :(

Bezug
                                        
Bezug
Rechteck (Grid) halbieren: Antwort
Status: (Antwort) fertig Status 
Datum: 09:43 Do 03.08.2017
Autor: donquijote

Hallo, folgende Überlegung:
Angenommen, es gibt einen aus weniger als n Knoten bestehenden Separator. Dann gibt es mindestens eine Zeile und n+1 Spalten, die keinen zum Separator gehörenden Knoten enthalten. Diese bilden einen aus [mm]n*(n+1)+n-1=n^2+2n-1[/mm] Knoten bestehenden zusammenhängenden Teilgraphen, der komplett in einer der Mengen A oder B liegen muss.

Bezug
                                                
Bezug
Rechteck (Grid) halbieren: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:31 Do 03.08.2017
Autor: TriMan

Oh, ja klasse, das ist genau das was ich gesucht habe. Ich verstehe nicht wieso mir das nicht eingefallen ist, das ist mir nun furchtbar peinlich.

Die Zeile verbindet alle Spalten miteinander, somit ist es zusammenhängend. Und dieser resultierender Teilgraph ist $> [mm] n^2$, [/mm] also mehr als 50% der Knoten des ursprünglichen Graph, also teilt der Separator den ursprünglichen Graph nicht in zwei gleichgroße Teilgraphen. Widerspruch. Also muss der Separator $S$ mit $|S| = n$, der die Seitenmitten der längsten Seiten des Grids miteinander verbindert, der Minimalste sein. Besten Dank!

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


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]