Matching und Vertex Cover < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:47 Mi 24.01.2007 | | Autor: | Bastiane |
Hallo zusammen!
Ich habe eine kurze Frage zu etwas aus der Vorlesung:
Es sind definiert:
[mm] \nu(G):=max [/mm] # eines Matchings
[mm] \tau(G):=min [/mm] # eines Vertex Cover
Warum gilt nun für einen beliebigen Graphen: [mm] \nu(G)\le\tau(G)? [/mm] An Beispielen sehe ich das, weiß aber nicht, wie man sich das allgemein vorstellt. Und auch, dass es kein "=" ist (im Allgemeinfall), ist mir klar. Aber wieso es [mm] \le [/mm] ist, weiß ich nicht.
Vielleicht kann mir das jemand erklären?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
Hallo Frau B.,
also prinzipiell kann man sich das doch darüber klar machen, was ein Matching ist und wie man eventuell von dem zu einem (nicht sonderlich guten) Vertex Cover kommt. Also versuche mit einem Matching VC zu approximieren und schau Dir die Implikationen über die Approximationsgüte an, denke etwas weiter und sei Glücklich, dass Du hoffentlich einsiehst, warum Deine Aussage stimmt.
Wenn das jetzt mehr Fragezeichen bei Dir produziert als vernichtet hat, kannst Du auch gerne in mein Zimmer kommen es Dir erklären lassen, dann musst Du aber selber die Antwort hier schreiben :p
--
[mm] $t^2$
[/mm]
|
|
|
| |
|
Liebe Chris,
nimm ein Maximum Matching M. Die Kanten von M sind paarweise knotendisjunkt. Ein Vertex Cover muss ja insbesondere aus jeder Kante von M mindestens einen Knoten enthalten.
Lieben Gruss,
Mathias
ps. Die Darstellung von [mm] t^2 [/mm] hat durch Nennung unnötig vieler Begriffe, die mit der Frage nicht unmittelbar zu tun haben,
die Situation nicht unbedingt geklärt.
|
|
|
|
