Blüte < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen!
Ich habe eine Frage zu einer Blüte in einem Graphen, bzw. zu deren Wurzel.
Eine Blüte ist wie folgt definiert:
Sei G ein Graph und M ein Matching in G. Eine Blüte in G bzgl. M ist ein faktorkrtitischer Teilgraph C von G mit $M [mm] \cap [/mm] E(C) = [mm] \frac{|V(C)|-1}{2}$. [/mm] Der nicht von $M [mm] \cap [/mm] E(C)$ überdeckte Knoten von C heißt die Basis von C.
Dabei ist ein faktorkritischer Graph:
Ein Graph G heißt faktorkritisch, falls $G-v$ ein perfektes Matching für jedes $v [mm] \in [/mm] V(G)$ besitzt.
Ich verstehe das mit der Basis der Blüte nicht. Also wenn G z.B. ein perfektes Matching enthält, dann kann es doch gar keine Wurzel geben, weil das perfekte Matching ja alle Knoten überdeckt. Und wenn das Matching z.B. zwei Knoten nicht überdeckt, welcher ist dann die Wurzel?
Vielen Dank schonmal.
LG Nadine
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Mi 05.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
