Rechteck (Grid) halbieren < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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.
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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. :(
|
|
|
| |
|
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.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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!
|
|
|
|
