Graph (3 dim. Gitter teilen) < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:52 Mi 17.01.2018 | | Autor: | sven1 |
Hallo,
ich habe eine Frage zur Graphentheorie.
Man könnte es jedoch auch als geometrisches Problem definieren, vielleicht können es dadurch auch andere verstehen, die sich mit Graphentheorie nicht direkt auskennen. Und zwar möchte ich beweisen, dass wenn ich ein Quader mit den Seitenlängen $n, n, 2n$ habe, dass die Ebene mit der Fläche $n [mm] \cdot [/mm] n$, die bei der Hälfte der längsten Seite ($2n$) sich befindet, die kleinste Fläche besitzt um das Quader in exakt zwei gleich große Teile zu trennen. Das heißt, dass es keine Verbindungsstrecke von dem einen Teil zum jeweils anderen Teil gibt ohne die beschriebene Ebene zu durchqueren. Ich möchte beweisen, dass diese Ebene die kleinste Möglichkeit (flächenmäßig) darstellt.
Nun folgt die Formulierung in der Graphentheorie.
Ich habe ein $n [mm] \times [/mm] n [mm] \times [/mm] 2n, n [mm] \in \IN$ [/mm] Gitter, die Elemente interpretiere ich zur Einfachheit halber mit einem 3 stelligen Tupel, d.h. das Gitter besteht aus den Knoten [mm] $\{(i,j,k) | 1 \le i,j \le n, 1 \le k \le 2n \}$. [/mm] Die Kantenmenge ist genauso definiert, wie man sich ein Gitter vorstellen würde und zwar sind das die direkten Nachbarn (horizontalen, vertikalen und senkrechten Nachbarn).
Ich möchte nun einen Separator finden, also eine Menge von Knoten, die dieses Gitter in [mm] $\pm [/mm] 2$ gleichgroße zusammenhängende Subgraphen teilt, so dass in keinen der beiden resultierenden Subgraphen ein zusammenhängender Graph konstruiert werden kann, der mind. $n [mm] \cdot [/mm] n [mm] \cdot [/mm] n = [mm] n^3$ [/mm] Knoten besitzt. Zusätzlich fordere ich, dass dieser Separator minimal sein soll, d.h. dass es keinen anderen Separator mit weniger Knoten gibt, der die Anforderungen erfüllt.
Ich behaupte, dass der folgende Separator $S$ dies erfüllt.
Sei $S := [mm] \{ (i,j,k) | k = n \wedge i,j \in \{1, \ldots, n \}\}$, [/mm] also die "Ebene" in der Mitte des "Quaders". Es scheint recht logisch zu wirken, da sobald ein Knoten in der "Ebene" fehlt ich einen "Durchgang von der einen Seite zur jeweils anderen Seite habe und dann bestimmt einen Graph konstruieren kann, der mindestens [mm] $n^3$ [/mm] Knoten besitzt, jedoch gelingt mir der Beweis dazu nicht.
Ich habe bereits einen Beweis für den zweidimensionalen Fall gefunden. Zur Einfachheit beschreibe ich es mal "geometrisch", d.h. wenn ich ein Rechteck habe, dass die Gerade, die von dem Mittelpunkt der längsten Seite zum Mittelpunkt der gegenüberliegenden (längsten) Seite, die minimalste Möglichkeit ist das Rechteck in zwei gleichgroße Teile zu separieren. Die Beweisidee war der Ansatz, den ich bereits 2 Zeilen vorher im letzten Absatz eingeführt habe. Ich hatte gezeigt, dass wenn es nicht stimmt ich dann anschließend einen Graphen konstruieren konnte, der mindestens [mm] $n^2$ [/mm] Knoten besaß. Widerspruch.
Ich wäre sehr sehr dankbar, wenn mir vllt. jemand helfen könnte. Denke sehr lange über dieses Problem bereits nach und finde keine richtige Beweisidee.
Beste Grüße
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:41 Do 18.01.2018 | | Autor: | leduart |
Hallo
Graphentheorie kann ich nicht, aber geometrisch ist das klar, jeder Schnitt durch den Quaderder durch Unterseite und Oberseite geht hat dieselbe Höhe n. aber größere Seitenlänge als das Quadrat [mm] n^2
[/mm]
Gruß leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:49 Do 18.01.2018 | | Autor: | sven1 |
Ich verstehe deine Antwort leider nicht richtig. Also sagst du auch, dass die Ebene in der Mitte die minimalste ist? Das Problem ist eher dass ich es nicht beweisen kann, logisch finde ich das auch, aber die Beweisidee finde ich nicht.
|
|
|
| |
|
Hallo,
> Ich verstehe deine Antwort leider nicht richtig. Also sagst
> du auch, dass die Ebene in der Mitte die minimalste ist?
> Das Problem ist eher dass ich es nicht beweisen kann,
> logisch finde ich das auch, aber die Beweisidee finde ich
> nicht.
also mit Graphentheorie kann ich leider auch nicht dienen. Man kann da aber meiner Meinung nach recht einfach argumentieren:
Gehe mal von dieser minimalen Schnittfläche aus. Sie geht durch die 'Mitte' des Quaders und damit durch seinen Schwerpunkt und steht rechtwinklig auf den geschnittenen Quaderkanten. Jede andere solche Schnittebene muss aber wegen der Symmetrieeigenschaften das Quaders ebenfalls durch den Schwerpunkt gehen. Wenn man jetzt überlegt, was das bedeutet, wenn man die Schnittebene aus ihrer idealen Lage heraus 'verdreht', dann ist eigentlich anschaulich klar, dass sich die Schnittfläche nur vergrößern kann. Wenn du z.B. zwei gegenüberliegende Ecken der Schnittfläche fest lässt und die beiden anderen bewegst, dann wird aus dem ursprünglichen Quadrat eine Raute, die eine Diagonale mit dem Quadrat gemeinsam hat, die andere wird länger. Ähnlich kann man argumentieren, wenn man jetzt noch die beiden anderen Punkte verschiebt (dann wird die Form der Schnittfläche allerdings i.a. nur noch ein Parallelogramm sein).
Wenn man es rechnen möchte, würde das meiner Ansicht nach mit einer zweidimensionalen Zielfunktion gehen, die man minimiert.
Gruß, Diophant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:03 Do 18.01.2018 | | Autor: | sven1 |
Danke auf jeden Fall schonmal. Du hast natürlich total recht, aber sowas hilft mir nicht beim "gleichen" Problem graphentheoretisch formuliert. Aber mir ist eben beim Rad fahren eine Idee eingefallen, ich versuche es jetzt nochmal. Ich werde anschließend mal berichten, ob es geklappt hat. :)
|
|
|
|
