Gegeben ist ein Graph ´G = (V, E)´.
Eine Überdeckung von ´G´ ist eine Menge ´V' sube V´ derart, dass ´{v,v'} nn V' != O/´ für alle Kanten ´(v, v') in E´ gilt.
Der Graph ´G´ heißt ´k´-knotenfärbbar, wenn es eine Abbildung ´phi : V -> {1, 2, …, k}´ derart gibt, dass ´phi(x) != phi(y)´ für alle Kanten ´(x, y) in E´ gilt.
(Wenn man ´k´ verschiedene Farben anstelle einer ´k´-elementigen Teilmenge von ´NN´ verwendet, so wird gefordert, dass durch eine Kante verbundene Knoten unterschiedlich gefärbt sind.)
Gegeben sei der Graph ´G = (V, E)´ mit ´V = {1,2,3,4,5,6,7,8,9,10,11}´, ´E = {(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), ´´(1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 4), (2, 10), (3, 5), (3, 7), ´´(3, 9), (3, 11), (4, 6), (5, 7), (5, 9), (5, 11), (6, 8), ´´(7, 9), (7, 11), (8, 10), (9, 11)}´
Bestimme folgende Zahlen:
- Maximale Zahl ´k´, für die es eine Clique aus ´k´ Elementen gibt
- Minimale Zahl ´k´, für die ´G´ ´k´-knotenfärbbar ist,
- Minimale Zahl ´k´, für die eine Überdeckung aus ´k´ Elementen existiert
Gib eine Transformation des Cliquenproblems auf das Überdeckungsproblem:
Gegeben: Graph ´G = (V, E)´, ´r in NN´, Frage : Gibt es eine ´r´-elementige Überdeckung von ´G´?
Teil 1.1
Wenn ´r´ Knoten eine Clique bilden, so hat jeder dieser Knoten mindestens den Grad ´r − 1´, da er mit allen anderen Knoten der Clique verbunden ist. Nur der Knoten ´1´ hat einen Grad ´>= 6´. Folglich ist eine Clique aus mehr als ´6´ Knoten nicht möglich. Einen Grad ´>= 5´ haben die Knoten ´1, 3, 5, 7, 9, 11´. Man erkennt durch Durchmustern aller Paare, dass diese Knoten tatsächlich eine Clique bilden. Damit ist die maximale Größe einer Clique in ´G´ durch ´6´ gegeben.
Teil 1.2
Da in einer Clique jeder Knoten mit jedem Knoten verbunden ist, müssen alle Knoten einer Clique mit unterschiedlichen Farben gefärbt werden. Aus 1.1 wissen wir, dass ´1, 3, 5, 7, 9, 11´ eine Clique bilden. Diese werden also alle unterschiedlich gefärbt. Wir ordnen nun ´2´ die gleiche Farbe wie ´3´ zu, da die Kante ´(2,3)´ nicht existiert. Aus gleichem Grund können wir ´4´ und ´5´, ´6´ und ´7´, ´8´ und ´9´ und ´10´ und ´11´ mit gleicher Farbe versehen. Somit reichen 6 Farben.
Formal ist die Abbildung folgendermaßen definiert:
´phi(1) = 1, phi(2) = phi(3) = 2, ´´phi(4) = phi(5) = 3, phi(6) = phi(7) = 4,´ ´phi(8) = phi(9) = 5, phi(10) = phi(11) = 6´
Die minimale Zahl für eine Färbung ist also 6.
Teil 1.3
Man betracht die Kanten ´(2,4)´, ´(4,6)´, ´(6,8)´, ´(8,10)´ und ´(10,2)´. In der Überdeckung ´V´ muss für jede dieser Kanten mindestens ein Knoten in ´V´ sein. Da jeder Knoten in nur zwei Kanten vorkommt, würde man mit ´2´ Knoten nur vier Kanten erfassen. Daher benötigt man mindestens drei dieser Knoten, z.B. ´2, 6, 10´. Die Elemente ´1,3,5,7,9,11´ bilden eine Clique. Nimmt man nur ´4´ Elemente der Clique in die Überdeckung, so wird die Kante zwischen den beiden Knoten der Clique, die nicht in ´V´ liegen, nicht erfasst. Daher müssen fünf Elemente der Clique benutzt werden, z.B. ´1,3,5,7,9´. Durch Durchmustern aller Kanten erkennt man, dass ´1,2,3,5,6,7,9,10´ tatsächlich eine Überdeckung bilden. Damit ist ´8´ die minimale Anzahl von Knoten für eine Überdeckung.
Teil 2
Die Transformation ´tau´ des Cliquenproblems (gegeben durch den Graphen ´H = (V, E)´ und die Zahl ´k´) auf das Überdeckungsproblem ist durch ´tau(H) = H'´ und ´tau(k) = #(V) − k´ gegeben. Dies folgt daraus, dass folgende Aussage gilt:
´U sube V´ ist genau dann eine Clique in ´H´, wenn ´V setminus U´ eine Überdeckung von ´H'´ ist.
Es soll diese Aussage nun bewiesen werden: Sei zuerst ´U´ eine Clique. Dann gibt es in ´H'´ keine Kante zwischen Elementen aus ´U´. Damit muss für jede Kante ´(v,v') in E'´ auch ´v !in U´ oder ´v' !in U´ gelten. Damit ist ´v´ oder ´v' in V setminus U´. Somit bildet ´V setminus U´ eine Überdeckung. Sei nun ´C´ eine Überdeckung von ´H'´. Dann gibt es nach Definition der Überdeckung keine Kante ´(u,u')´ mit ´u !in C´ und ´u' !in C´. Somit sind alle Paare ´(u,u')´ mit ´u,u' !in C´ keine Kante in ´H'´. Damit ist aber ´(u, u')´ für ´u, u' !in C´ eine Kante in ´H´. Daher bildet ´V setminus C´ eine Clique in ´H´.
HPI, 2014-06-12, Theoretische Informatik 2, Blatt 9, Aufgabe 3
2014-07-23 08:33:16 UTC
2014-07-23 08:33:38 UTC