Schnitte < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:09 Sa 10.11.2012 | | Autor: | Pacapear |
Hallo zusammen!
Ich habe eine Frage zu Schnitten. Und zwar geht es um die Anzahl kantendisjunkter Schnitte.
Also ein Schnitt ist ja die Menge aller Kanten zwischen zwei Knotenmenge X und [mm] V(G)\X, [/mm] wobei G der ganze Graph ist.
Wenn ein Schnitt nun alle Kanten zwischen diesen beiden Knotenmengen beinhaltet, wie kann es dann mehrere kantendisjunkte Schnitte zwischen diesen beiden Knotenmengen geben?
Das würde ja heißen, dass jeder dieser kantendisjunkten Schnitte nur einen Teil der Kanten zwischen X und [mm] V(G)\X [/mm] enthalten kann, aber das widerspricht doch der Definition, dass ein Schnitt ALLE Kanten zwischen den Knotenmengen enthält.
Vielen Dank schonmal.
LG Nadine
|
|
| |
|
> Hallo zusammen!
>
> Ich habe eine Frage zu Schnitten. Und zwar geht es um die
> Anzahl kantendisjunkter Schnitte.
>
> Also ein Schnitt ist ja die Menge aller Kanten zwischen
> zwei Knotenmenge X und [mm]V(G)\X,[/mm] wobei G der ganze Graph
> ist. ![[haee]](/images/smileys/haee.gif "[haee]")
>
> Wenn ein Schnitt nun alle Kanten zwischen diesen beiden
> Knotenmengen beinhaltet, wie kann es dann mehrere
> kantendisjunkte Schnitte zwischen diesen beiden
> Knotenmengen geben?
>
> Das würde ja heißen, dass jeder dieser kantendisjunkten
> Schnitte nur einen Teil der Kanten zwischen X und [mm]V(G)\X[/mm]
> enthalten kann, aber das widerspricht doch der Definition,
> dass ein Schnitt ALLE Kanten zwischen den Knotenmengen
> enthält.
>
> Vielen Dank schonmal.
>
> LG Nadine
Hallo Nadine,
in Wikipedia liest man:
Ein Schnitt bezeichnet in der Graphentheorie eine
Menge von Kanten eines Graphen G=(V,E), die zwischen
zwei Mengen von Knoten bzw. zwischen einer Menge
[mm] X\subset [/mm] V und der Restmenge [mm] V\backslash [/mm] X liegt.
Nun ist mir nicht klar, für welche beiden Mengen genau
du nun den Schnitt betrachten willst.
Wenn du für die zweite Menge wirklich die Menge V aller
im Graph G vorhandenen Knoten nehmen willst, dann
wird aus dem Schnitt von X und V die Menge sämtlicher
Kanten des Subgraphen, der aus G entsteht, wenn man
aus ihm alle Knoten entfernt, die nicht in X enthalten sind
sowie alle Kanten, welche mit solchen Knoten inzident
waren.
Das ist aber möglicherweise nicht, was du gemeint hast.
Gib darum die eigentliche Aufgabe genauer an !
LG
Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:40 So 11.11.2012 | | Autor: | Pacapear |
Hallo!
> in Wikipedia liest man:
>
> Ein Schnitt bezeichnet in der Graphentheorie eine
> Menge von Kanten eines Graphen G=(V,E), die zwischen
> zwei Mengen von Knoten bzw. zwischen einer Menge
> [mm]X\subset[/mm] V und der Restmenge [mm]V\backslash[/mm] X liegt.
Ich habe etwas tiefer gelesen bei Wikipedia (unter Definition):
Für einen ungerichteten Graphen G=(V,E) mit einer Menge [mm] X\subset [/mm] V wird der Schnitt [mm] E(X,V\backslash [/mm] X) definiert als: [mm] E(X,V\backslash X)=\{(u,v)\in E:u\in X,v\in V\backslash X\}. [/mm] Er umfasst also alle Kanten aus E für die gilt, dass ein Endknoten in der Teilmenge X liegt und der andere in der Menge der übrigen Knoten. Diese Kanten liegen also sozusagen "zwischen" den beiden Teilmengen der Knoten.
So haben wir das auch definiert. Eine Knotenmenge X, die Restknotenmenge [mm] V(G)\backslash [/mm] X, der Schnitt sind alle Kanten dazwischen.
> Gib darum die eigentliche Aufgabe genauer an !
Ich habe keine Aufgabe, ich arbeite gerade meine Vorlesungsmitschrift für eine Prüfung durch. Da gehts gerade um T-Joins und T-Schnitte. Dabei ist ein T-Schnitt ein Schnitt nach obiger Definition mit [mm] |X\cap [/mm] T| ungerade für eine gerade Knotenmenge T aus G.
Und irgendwann kommt dann eine Aussage, dass die minimale Kardinalität eines T-Joins (spezielle Kantenmenge) gleich der maximalen Anzahl von kantendisjunkten T-Schnitten ist (für bipartite Graphen).
Und ich frage mich jetzt, wie es in einem Graphen mehrere kantendisjunkte T-Schnitte geben kann, wenn ein Schnitt nach Definition bereits alle möglichen Kanten zwischen den zwei "Schnittmengen" enthält, wo ich also noch disjunte Kanten hernehmen kann.
LG Nadine
|
|
|
| |
|
> Hallo!
>
> > in Wikipedia liest man:
> >
> > Ein Schnitt bezeichnet in der Graphentheorie eine
> > Menge von Kanten eines Graphen G=(V,E), die zwischen
> > zwei Mengen von Knoten bzw. zwischen einer Menge
> > [mm]X\subset[/mm] V und der Restmenge [mm]V\backslash[/mm] X liegt.
>
> Ich habe etwas tiefer gelesen bei Wikipedia (unter
> Definition):
>
> Für einen ungerichteten Graphen G=(V,E) mit einer Menge
> [mm]X\subset[/mm] V wird der Schnitt [mm]E(X,V\backslash[/mm] X) definiert
> als: [mm]E(X,V\backslash X)=\{(u,v)\in E:u\in X,v\in V\backslash X\}.[/mm]
> Er umfasst also alle Kanten aus E für die gilt, dass ein
> Endknoten in der Teilmenge X liegt und der andere in der
> Menge der übrigen Knoten. Diese Kanten liegen also
> sozusagen "zwischen" den beiden Teilmengen der Knoten.
>
> So haben wir das auch definiert. Eine Knotenmenge X, die
> Restknotenmenge [mm]V(G)\backslash[/mm] X, der Schnitt sind alle
> Kanten dazwischen.
>
> > Gib darum die eigentliche Aufgabe genauer an !
>
> Ich habe keine Aufgabe, ich arbeite gerade meine
> Vorlesungsmitschrift für eine Prüfung durch. Da gehts
> gerade um T-Joins und T-Schnitte. Dabei ist ein T-Schnitt
> ein Schnitt nach obiger Definition mit [mm]|X\cap[/mm] T| ungerade
> für eine gerade Knotenmenge T aus G.
>
> Und irgendwann kommt dann eine Aussage, dass die minimale
> Kardinalität eines T-Joins (spezielle Kantenmenge) gleich
> der maximalen Anzahl von kantendisjunkten T-Schnitten ist
> (für bipartite Graphen).
>
> Und ich frage mich jetzt, wie es in einem Graphen mehrere
> kantendisjunkte T-Schnitte geben kann, wenn ein Schnitt
> nach Definition bereits alle möglichen Kanten zwischen den
> zwei "Schnittmengen" enthält, wo ich also noch disjunkte
> Kanten hernehmen kann.
>
> LG Nadine
Guten Tag Nadine !
wir haben bis jetzt nur von T-Schnitten gesprochen. Nun
bringst du aber auch noch sogenannte "T-Joins" ins Spiel.
Ich denke, dass du dich jetzt zunächst auch noch genauer
mit deren Definition befassen solltest.
Da mir selber diese Begriffe auch nicht (bzw. nicht mehr)
geläufig sind, muss ich dies ebenfalls tun, damit ich zu
dieser Diskussion ev. noch etwas beitragen kann. Im
Augenblick habe ich aber dafür nicht die Zeit ...
Könntest du vielleicht die interessierende Stelle aus dem
Skript noch etwas ausführlicher zitieren ?
LG, Al
|
|
|
| |
|
Hallo!
> Könntest du vielleicht die interessierende Stelle aus dem
> Skript noch etwas ausführlicher zitieren ?
Also es geht um folgende Aussage:
Sei G ein bipartiter Graph und $T [mm] \subset [/mm] V(G)$ so, dass ein T-Join existiert. Dann ist die minimale Kardinalität eines T-Joins gleich der maximalen Anzahl von kanten-disjunkten T-Schnitten.
Und da frage ich mich halt, wie viele T-Schnitte (bzw. "normale" Schnitte) es zu einer festen Knotenmenge in einem Graphen geben kann?
Etwas weiter in der Vorlesung geht es um s-t-Schnitte. Die haben wir definiert als eine Menge [mm] $\delta^+(X)$ [/mm] (im gerichteten Graph) bzw. [mm] \delta(X) [/mm] (im ungerichteten Graph) für $X [mm] \subset [/mm] V(G)$ mit $s [mm] \in [/mm] X$ und $t [mm] \notin [/mm] X$.
Hier geht es jetzt darum, denjenigen s-t-Schnitt mit minimaler Kapazität zu finden, wenn man alle Kanten mit endlichen Kapazitäten ausstattet. Und auch hier frage ich mich wieder, wie viele solcher s-t-Schnitte es überhaupt gibt.
Wir haben hier ein Beispiel: der [mm] K_{3,3}, [/mm] bei dem alle Kapazitäten 1 sind. Und da haben wir, dass die minimale Kapazität eines s-t-Schnittes 3 ist für alle s und t.
Mir ist irgendwie gar nicht klar, wie ich diese s-t-Schnitte finde, um dann den mit minimaler Kapazität zu suchen. Wie ich z.B. die Menge X wählen muss, die s, aber nicht t, enthält. Muss man das für alle möglichen X machen, und das auch für alle möglichen s-t-Kombinationen, um alle Schnitte zu erhalten? Ich weiß echt nicht, wie ich da rangehen muss.
LG Nadine
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 So 16.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
