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
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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

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
StartseiteMatheForenGraphentheorieRechteck (Grid) halbieren
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
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


Alle Foren
Status vor 2h 23m 14. Tipsi
IntTheo/Flächenmaß berechnen
Status vor 3h 01m 4. leduart
Algebra/Gleichung auflösen
Status vor 4h 07m 7. Tipsi
UAnaR1FunkInt/Faltungen abschätzen
Status vor 4h 11m 2. Al-Chwarizmi
z-transformation/z transformation und dann?
Status vor 5h 29m 3. Teekanne3d
UAnaR1FolgReih/Potenzreihe
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]