2-Knotenüberdeckung < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Eine 2-Knotenüberdeckung ist ein Vektor y Element von Z_+^V, so dass
[mm] y_u [/mm] + [mm] y_v [/mm] >= 2, wobei G=(V,E) ein ungerichteter Graph ist. |
Ich verstehe diese Definition leider nicht. Könnte jemand mir erklären, was eine 2-Knotenüberdeckung eines Graphes bedeutet?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo joerg_sch und erstmal herzlich ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") ,
> Eine 2-Knotenüberdeckung ist ein Vektor y Element von
> Z_+^V, so dass
> [mm]y_u[/mm] + [mm]y_v[/mm] >= 2, wobei G=(V,E) ein ungerichteter Graph ist.
> Ich verstehe diese Definition leider nicht. Könnte jemand
> mir erklären, was eine 2-Knotenüberdeckung eines Graphes
> bedeutet?
Was soll Z_+^V bedeuten?
Soll das [mm]\IZ_+^V[/mm] heißen?
Verbal ist eine 2-Knotenüberdeckung dies:
Eine 2-Knotenüberdeckung ist eine Menge [mm]U[/mm] mit 2 oder mehr Knoten, so dass jede Kante aus E mit mindestens einem Knoten aus U inzidiert.
Es tut natürlich immer auch $V$ als Knotenüberdeckung ...
Wenn nach der minimalen Knotenüberdeckung gefragt ist, so spricht man von der Knotenüberdeckungszahl eines Graphen.
Nimm etwa einen Kreis der Länge 4, also [mm]C=v_1v_2v_3v_4[/mm]
Der hat natürlich mehrere 2-Knotenübedeckungen, aber auch eine minimale mit genau 2 Knoten:
Du kannst als [mm]U[/mm] wählen [mm]\{v_1,v_3\}[/mm] oder [mm]\{v_2,v_4\}[/mm]
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruß
schachuzipus
|
|
|
|
