Definition Knotenüberdeckung < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:24 Mi 03.01.2007 | | Autor: | snIP3r |
Hallo zusammen!
Ich verstehe die Definition einer Knotenüberdeckung nicht so ganz!
Definition Knotenüberdeckung:
Ist jede Kante aus E(G) mit einem
Punkt aus U [mm] \subseteq [/mm] V(G) inzident, so nennt
man U Überdeckung von E (bzw.
Knotenüberdeckung von G).
Die Definition stammt hieraus (Seite 4): http://www2.informatik.hu-berlin.de/~iwas/matching.pdf
Aber das Bild rechts daneben verwirrt mich ein wenig. In der Definition wird von jeder Kante aus G gesprochen. Aber die Kante v1-v7 ist nicht dabei, alle anderen schon. Und weder V1 noch V7 sind Teil der Überdeckung.
Kann mir das vllt. jemand erklären??
Danke und Gruss
snIP3r
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo snIP3r!
> Ich verstehe die Definition einer Knotenüberdeckung nicht
> so ganz!
>
> Definition Knotenüberdeckung:
> Ist jede Kante aus E(G) mit einem
> Punkt aus U [mm]\subseteq[/mm] V(G) inzident, so nennt
> man U Überdeckung von E (bzw.
> Knotenüberdeckung von G).
>
> Die Definition stammt hieraus (Seite 4):
> http://www2.informatik.hu-berlin.de/~iwas/matching.pdf
>
> Aber das Bild rechts daneben verwirrt mich ein wenig. In
> der Definition wird von jeder Kante aus G gesprochen. Aber
> die Kante v1-v7 ist nicht dabei, alle anderen schon. Und
> weder V1 noch V7 sind Teil der Überdeckung.
Hehe, ich glaube, dein Problem ist gar keins. Du verstehst das schon richtig, nur ist die Darstellung etwas ungünstig. Und zwar stellen nicht die schwarzen Knoten die Knotenüberdeckung dar, sondern die "weißen". Ich finde das sehr ungünstig und habe auch zuerst überlegt, welche Knoten denn jetzt die Überdeckung sein sollen, aber anders macht es keinen Sinn. Und da in den anderen Beispielen alle Knoten immer schwarz sind, sind wohl hier die "normalen" Knoten ebenfalls schwarz, und die ausgewählten für die Knotenüberdeckung sind eben "anders gefärbt". Damit dürfte sich dein Problem gelöst haben, aber du kannst dem Schreiber des Skripts ja mal sagen, dass das so etwas ungünstig ist. 
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:46 Mi 03.01.2007 | | Autor: | snIP3r |
Danke fuer die schnelle Antwort!! Genau das ist auch das Problem eines Buches das ich lese und immer auf die falschen Knoten gesehen habe!!!
Jetzt denke ich ist mein Verstaendnis wieder hergestellt ;)
Greets
snIP3r
|
|
|
|
