Diskussion:Schnitt (Graphentheorie)

Meiner Meinung wird im Artikel die Beziehung zwischen der Darstellung eines Schnittes durch Kanten und der Darstellung als Partition der Knoten nicht ganz klar. Insbesondere im ersten Absatz des Artikels fehlt der Hinweis auf die Partition.

Warum die Darstellung als Partition wichtig ist: In nicht zusammenhängenden Graphen ist die Darstellung als Kanten nicht eindeutig, insbesondere induziert der triviale - leere - Schnitt durch eine leere Kantenmenge k! Schnitten in Partitionen (k Anzahl der Zusammenhangskomponenten).

Hat hierzu noch jemand eine Meinung?

Gruß Benutzer:Purestorm

Vor allem kommt es hierbei zu falschen Aussagen. Im Abschnitt "Zusammenhang und minimale Schnitte" wird behauptet, dass sich durch das Entfernen der Kanten eines Schnittes die Anzahl der Zusammenhangskomponenten erhöht. Das stimmt z.B. dann nicht, wenn der Schnitt leer war (d.h. keine Kanten entfernt werden). Für zusammenhängende Graphen klappt es mit der obigen Definition nicht, weil da X leer oder X=V genau so schief gehen. MatthiasWalter 19:51, 15. Nov. 2011 (CET)

Schnitt = Menge aus Knoten oder Kanten?

In der ersten Zeile wird ein Schnitt als Menge von Kanten bezeichnet: Ein Schnitt bezeichnet in der Graphentheorie eine Menge von Kanten eines Graphen G = (V,E),

Dann bei der Definition wird ein Schnitt stets als 2-Tupel von zwei Mengen von Knoten angegeben. Letztere Definition ist mir auch geläufig. Jemand sollte diese Inkonsistenz beseitigen. :-)

Öhm? :) Eine Kante ist ja nix anderes als eine zwei-elementige Menge von Knoten. Und ein Schnitt ist halt eine Menge von Kanten, wobei für die beiden Knoten, aus denen eine Kante besteht, besondere Bedingungen gelten. Ich sehe da keine Inkonsistenz, aber vielleicht habe ich auch dich oder die Graphentheorie falsch verstanden. ;) Schau auch mal zur Definition von Knoten und Kanten. --Ollie B Bommel 08:01, 28. Jul. 2008 (CEST)

Laut Buch von Cormen (e.a) Seite 659 ists tatsächlich eine Zerlegung in Knotenmengen. Der Grund dürfte aber eher die angenehmere Handhabung für weitergehende Beweise sein, als eine prinzipielle Festsetzung. Polopower 14:18, 6. Aug. 2008 (CEST)

Der erste Absatz ist falsch! Ein Schnitt ist eine Partition der KNOTEN-Menge des Graphen. (X, V\X) ist der Schnitt, daraus ergibt sich dann, welche Kanten den Schnitt kreuzen. X kann eine beliebige Teilmenge der Knotenmenge sein - daraus ergibt sich alles weitere. Wenn man umgekehrt mit der Kantenmenge beginnt zu definieren, kriegt man Schwierigkeiten, denn nicht jede Kantenmenge im Graphen ist ein Schnitt! ich korrigiere dies mal. Graf Alge 03:00, 23. Sep. 2014 (CEST)