\\(SAT\\) steht f\u00fcr das englische\u00a0satisfiability.\u00a0<\/i>Also ein Erf\u00fcllbarkeitsproblem. Es wird gefragt ob eine aussagenlogische Formel erf\u00fcllbar ist (erinnert ihr euch an KNF\/DNF aus der technischen Informatik? Das hier ist nicht weit weg…).<\/p>\n
Da eine Formel nur endlich viele variablen enth\u00e4lt, die nur mit \\(1\\) und \\(0\\) belegt werden k\u00f6nnen, haben wir eine endliche Anzahl an M\u00f6glichkeiten. Wenn wir alle durchprobieren, kommen wir (oder nicht) irgendwann dahin, dass die Formel wahr wird. Haben wir \\(n\\) Variablen, so m\u00fcssen wir im worst case \\(2^n\\) Kombinationen betrachten. Damit ben\u00f6tigen wir f\u00fcr \\(SAT\\) einen Exponentialzeitalgorithmus und diese gelten f\u00fcr die Praxis als unwichtig, steigt der Aufwand f\u00fcr gr\u00f6\u00dfere \\(n\\) doch massiv an. H\u00e4tten wir zu dem Problem einen Polynomialzeitalgorithmus, s\u00e4he die Sache ganz anders aus.<\/p>\n
Aber es gibt einen Lichtblick: Wenn wir nicht jede M\u00f6glichkeit durchprobieren wollen, kann das Pr\u00fcfen einer vorgegebenen L\u00f6sung f\u00fcr \\(SAT\\) in Linearzeit erfolgen. Haben wir \\(n\\) Variablen, so m\u00fcssen wir sie erst kurz belegen und die Formel dann auswerten. Beides geht jeweils in Linearzeit. Damit haben wir schon einmal den ersten Schritt getan: wir haben eine \\(KTM\\) angegeben, die die Hilfseingabe (unsere zu pr\u00fcfende Belegung der \\(n\\) Variablen) auf wahr oder falsch kontrolliert. Okay, haben wir nicht. Aber wir k\u00f6nnten es mit wenig Aufwand (vielleicht reiche ich so eine \\(KTM\\) bei Gelegenheit hier nach) tun. Damit ist der erste Schritt vollbraucht \\(SAT\\in NP\\).<\/p>\n
K\u00fcmmern wir uns nun um den zweiten Schritt, die \\(NP\\)-H\u00e4rte. Aber ohne die Abk\u00fcrzung der Reduktion zu nehmen.\u00a0Das folgende Beispiel basiert auf dem Buch von\u00a0Prof. Dr. Dirk W. Hoffmann<\/a>\u00a0(oben rechts verlinkt).\u00a0Die Credits also ausnahmslos an ihn. Und auch wenn ich mich wie eine kaputte Schallplatte anh\u00f6re: das Buch ist ein Lifesaver f\u00fcr theoretische Informatik und geh\u00f6rt in jedes IT-B\u00fccherregel, daher absolute Kaufempfehlung. Der Herr geh\u00f6rt unbedingt unterst\u00fctzt.<\/p>\n Wir m\u00fcssen hier also beweisen, dass wir ausnahmslos alle<\/strong> Probleme aus \\(NP\\) auf \\(SAT\\) reduzieren k\u00f6nnen. Da wir keines haben, m\u00fcssen wir uns eins basteln, wo einzusehen ist, dass es alle Probleme aus \\(NP\\) „widerspiegelt“ und dieses auf \\(SAT\\) reduzieren. Nehmen wir also ein beliebiges Problem \\(L\\in NP\\) und eine \\(TM\\) namens \\(T\\), die das Problem entscheidet. Wir m\u00fcssen jetzt zeigen, dass wir f\u00fcr jedes Eingabewort \\(\\omega\\) f\u00fcr \\(T\\) eine Formel \\(F\\) konstruieren k\u00f6nnen, f\u00fcr die gilt:<\/p>\n \\(T(\\omega)\\) terminiert im Endzustand \\(\\Leftrightarrow F(\\omega)\\) ist erf\u00fcllbar.<\/p><\/blockquote>\n D.h. nur wenn unsere Maschine mit dem Eingabewort terminiert, so ist auch unsere Formel mit dem gleichen Eingabewort erf\u00fcllbar und andersrum. Wir m\u00fcssen \\(F\\) in polynomieller Zeit konstruieren. Dazu werden zun\u00e4chst Variablen eingef\u00fchrt:<\/p>\n \\(B_{i,k,\\sigma}=1\\) Nach \\(i\\) Schritten, steht an Position \\(k\\) das Zeichen \\(\\sigma\\).<\/p>\n \\(S_{i,S}=1\\) Maschine \\(T\\) befindet sich nach \\(i\\) Schritten im Zustand \\(S\\).<\/p>\n \\(P_{i,k}=1\\) Maschine \\(T\\) befindet sich nach \\(i\\) Schritten auf Bandposition \\(k\\).<\/p><\/blockquote>\n Die Laufzeit der Maschine ist polynomiell durch das Polynom \\(p(n)\\) beschr\u00e4nkt, denn \\(n\\) ist die L\u00e4nge der Eingabe \\(\\omega\\). Die Indizes von \\(i,s\\) liegen also im Intervall \\([0;p(n)]\\). Auch bewegt sich der Schreib-Lese-Kopf maximal \\(p(n)\\) Positionen nach links oder rechts, so dass wir den Bandinhalt auf dem Teilst\u00fcck \\(-p(n),…,p(n)\\) betrachten m\u00fcssen. Der Kopf steht \u00fcber der Position \\(0\\). Ausprobiert wird das an der Sprache \\(L:=\\{\\#^n\\mid n\\in{\\mathbb{N}}\\}\\) mit dem Alphabet \\(\\Sigma=\\{\\#\\}\\).<\/p>\n Diese Sprache wird von einer \\(TM\\) erkannt, die nur zwei Zust\u00e4nde hat. \\(s_0\\) wenn das Zeichen auf dem Band eine \\(\\#\\) ist (Eingabewort \\(\\omega\\in L\\)) und \\(s_1\\) wenn es ein \\(B\\) (Blank) ist.\u00a0Da die Berechnung hier bereits nach einem Schritt endet, ist die Laufzeit der Maschine \\(p(n)=1\\). Wir haben also ein „Problem“, dass in polynomieller Zeit durch die \\(T\\) entschieden werden kann und damit in \\(P\\) liegt (das \\(N\\) ist ja nur das Orakeln der Eingabe). Nun m\u00fcssen wir \\(T\\) nur noch polynomiell in eine \\(SAT\\)-Instanz codieren.<\/p>\n Um den Bandzustand, den Zustand der Maschine und die Position des Lesekopfes als eine Formel zu codieren, werden die oben eingef\u00fchrten Variablen verwendet. Ist z.B. \\(B_{0,1,\\#}=1\\), so befindet sich auf dem Band jetzt auf Position \\(1\\) das Zeichen \\(\\#\\). Durch die oben gemachten Einschr\u00e4nkungen, haben wir \\(12\\) verschiedene Bandvariablen, die wir mit \\(0\\) oder \\(1\\) belegen k\u00f6nnen um den\u00a0Bandzustand<\/strong>\u00a0zu repr\u00e4sentieren (\\(B\\) ist das Blank).<\/p>\n Der\u00a0Zustand<\/strong>\u00a0von \\(T\\) codieren wir mit:<\/p>\n F\u00fcr die\u00a0Kopfposition<\/strong>\u00a0haben wir sechs Variablen:<\/p>\n Mit diesen Variablen haben wir alle Variablen repr\u00e4sentiert, die die Maschine \\(T\\) einnehmen kann.\u00a0Wenn wir die Maschine also in \\(SAT\\) abbilden wollen, sieht die Formel \\(F\\) dann so aus:<\/p>\n Was bedeutet es?<\/p>\n \\(S\\): Startbedingung. Initiale Konfiguration von \\(T\\). Die Maschine befindet sich in \\(s_0\\), das Eingabewort \\(\\omega\\) ist auf dem Band, der Rest ist leer und der Kopf befindet sich auf Position \\(0\\).<\/p>\n \\(R\\): Randbedingungen, die \\(T\\) zu jeder zeit erf\u00fcllen muss, d.h. \\(R=(R_1\\wedge R_2\\wedge R_3)\\) Diese sind:<\/p>\n \\(R_1\\): Maschine befindet sich zu jedem Zeitpunkt in nur einem Zustand<\/p>\n \\(R_2\\): Der Schreib-Lese-Kopf befindet sich immer nur an einer Position.<\/p>\n \\(R_3\\): Es befindet sich nur ein Symbol an jeder Bandstelle zu jedem Zeitpunkt.<\/p>\n \\(T\\): Transitionsbedingungen. In dieser Teilformel werden die m\u00f6glichen Konfigurations\u00fcberg\u00e4nge codiert, d.h.\u00a0\\(T=(T_1\\wedge T_2\\wedge T_3)\\)\u00a0Sie bestehen aus:<\/p>\n \\(T_1\\): Maschine geht in Folgekonfiuration \u00fcber.<\/p>\n \\(T_2\\): Inaktive Maschine, terminiert.<\/p>\n \\(T_3\\): Bandinhalt wird ge\u00e4ndert.<\/p>\n \\(A\\): Akzeptanzbedingung. Hier wird codiert, dass die \\(TM\\) das Wort \\(\\omega\\) dann annimmt wenn es im Endzustand anh\u00e4lt. Der Zustand muss in weniger als \\(p(n)\\) Berechnungsschritten erreicht werden.<\/p><\/blockquote>\n Und nun kommt der Spa\u00df an der Sache. Alle Bedingungen k\u00f6nnen wir als Formel codieren.<\/p>\n Beispiel<\/strong>: nehmen wir an, das Wort \\(\\omega\\) besteht aus \\(\\#\\), d.h. auf dem Band steht \\(B\\# B\\). Die oben in Prosa verfasste Startbedingung, w\u00e4re dann:<\/p>\n \\(S=S_{0,s_0}\\wedge{P_{0,0}}\\wedge{B_{0,-1,B}}\\wedge{B_{0,0,\\#}}\\wedge{B_{0,1,B}}\\)<\/p>\n In Worten ausgedr\u00fcckt: Die Maschine befindet sich nach \\(0\\) Schritten im Zustand \\(s_0\\) (erste Bedingung), der Lesekopf nach \\(0\\) Schritten auf Position \\(0\\) (zweite Bedingung) und auf dem Band steht auf Positionen \\(-1,0,1\\) eben \\(B,\\#,B\\) (dritte, vierte und f\u00fcnfte Bedingung). Und wenn das alles stimmt, die Variablen also alle mit einer \\(1\\) belegt sind, dann evaluiert die Formel \\(S\\) bei Auswertung zu \\(1\\).\u00a0Oh mein Gott! Das ist genau das, was wir f\u00fcr die Maschine \\(T\\) festgelegt und nun in eine Formel gequetscht haben.<\/p>\n Haben wir z.B. ein leeres Wort \\(\\epsilon\\), d.h.\u00a0auf dem Band steht \\(BBB\\), so sieht unsere Startbedingung wie folgt aus:<\/p>\n \\(S=S_{0,s_0}\\wedge{P_{0,0}}\\wedge{B_{0,-1,B}}\\wedge{B_{0,0,B}}\\wedge{B_{0,1,B}}\\)<\/p>\n Gleiches gilt f\u00fcr Rand-, Transitions- und Akzeptanzbedingungen, die wir eben auch als Formel darstellen k\u00f6nnen. Ist nur alles ziemliche Schreibarbeit.\u00a0Wenn die alle erf\u00fcllt sind, evaluiert auch unsere Gesamtformel \\(F\\) (siehe oben) zu einer \\(1\\). Eventuell schreibe ich die kompletten Rand- und Transitionsbedingungen bei Gelegenheit hier nochmal hin.<\/p>\n Wie wir also sehen k\u00f6nnen, k\u00f6nnen wir die Bedingungen f\u00fcr eine Maschine \\(T\\) in eine Formel \\(F\\) quetschen, die genau das tut, was wir wollen. Wir haben also gezeigt, wie eine \\(NTM\\) \\(T\\) polynomiell auf eine aussagenlogische Formel reduziert werden kann, die genau dann erf\u00fcllbar ist, wenn \\(T\\) in einem Endzustand terminiert.<\/p>\n Ein ausf\u00fchrlicher Beweis ist z.B. auch\u00a0hier<\/a>\u00a0zu finden.<\/p>\n Hier entfaltet \\(SAT\\) seinen Charme: wir k\u00f6nnen viele Algorithmen auf \\(SAT\\) zur\u00fcckf\u00fchren, indem wir den Ablauf in die Formel hineincodieren und damit das Problem auf \\(SAT\\) reduzieren. Und was passt hier besser als Beispiel, als \\(3SAT\\)?<\/p>\n Antwort zum Lernziel<\/strong>: wir codieren eine komplette Aussagenlogische Formel in ein Wort f\u00fcr eine Turingmaschine, deren Laufzeit polynomiell beschr\u00e4nkt ist. Die Maschine terminiert nur wenn die aussagenlogische Formel wahr ist. Es ist leicht einzusehen, dass diese initiale Turingmaschine, also praktisch unser \\(NP\\)-vollst\u00e4ndiges Problem (wo leicht einzusehen ist, dass es tats\u00e4chlich in \\(NP\\) liegt), in polynomzeit durch eine Kontroll-Turingmaschine entschieden werden kann.<\/p>\n In die Eingabe dieser Maschine dieses wird dann die zu pr\u00fcfende, aussagenlogische \\(SAT\\)-Formel codiert und von dieser \\(KTM\\) ebenfalls in Polynomzeit entschieden.<\/p>\n Wie f\u00fchrt man eine einfache, polynomielle Reduktion\u00a0\\({}\\leq_{pol}\\)\u00a0\u00a0aus?<\/em><\/p>\n Die Frage bei \\(3SAT\\) ist:<\/p>\n Gibt es eine erf\u00fcllende Bedingung bei \\(n\\) aussagenlogischen Klauseln mit maximal \\(3\\) Literalen (atomare Aussage, z.B. \\(\\neg{A}\\) oder \\(A\\))?<\/em><\/p>\n Damit ist \\(3SAT\\) eine abgeschw\u00e4chte Form von \\(SAT\\). Einschr\u00e4nkung ist, dass die Formel f\u00fcr \\(3SAT\\) in der Konjunktivform (mit \\(\\wedge\\) verkn\u00fcpft) vorhanden sein muss. Um also zu zeigen, dass \\(3SAT\\) ebenfalls \\(NP\\)-hart ist, m\u00fcssen wir \\(SAT\\) auf \\(3SAT\\)\u00a0polynomiell<\/strong>\u00a0reduzieren, formal ausgedr\u00fcckt:<\/p>\n Was wir tun m\u00fcssen, ist also eine allgemeine Formel nehmen und sie so umformen, dass die beliebig viele Klauseln, aber nur drei Literale pro Klausel hat. Das machen wir mit Hilfe von Hilfsvariablen. Haben wir also ein Term in der folgenden Form in KNF mit \\(n\\) Variablen:<\/p>\n F\u00fcr jede Klausel mit \\(n\\) Variablen entstehen \\(n-2\\) neue Klauseln mit \\(n-3\\) neuen Variablen:<\/p>\n Hilfsvariablen? Ja, Hilfsvariablen. Diese Variablen zeigen uns an, welcher Teil aus der zerteilen Klausel das ganze Konstrukt hat wahr werden lassen.<\/p>\n Beispiel<\/strong>? Klar:\u00a0\\((A\\vee\\overline{B}\\vee C\\vee\\overline{D})\\wedge(E\\vee F\\vee G)\\)<\/p>\n Die erste Klausel wandeln wir also um in \\(2\\) Klauseln mit einer neuen Variable. Die zweite Klauseln k\u00f6nnen wir so lassen, da wir da bereits drei Literale drin haben. Nennen wir unsere neue Hilfsvariable also einfach \\(h_1\\). Damit sehen unsere beiden neuen Klauseln nun so aus:<\/p>\n \\((A\\vee\\overline{B}\\vee h_1)\\wedge(C\\vee\\overline{D}\\vee\\overline{h_1})\\)<\/p>\n<\/blockquote>\n Der Trick hierbei ist, dass die Hilfsvariable \\(h_1\\) dann falsch wird, wenn die erste Teilklausel wahr wird und wahr wird wenn die zweite Teilklausel wahr wird.\u00a0Stellen wir doch eine kleine Wertetabelle f\u00fcr den umgeformten Term zusammen, wie wir das auch in der technischen Informatik (Computersysteme 1&2) gemacht haben:<\/p>\n Ich habe Excel etwas vergewaltigt, nehmt mir das nicht \u00fcbel. Die Spalten haben folgende Bedeutung:<\/p>\n Und sie tut genau das gleiche wie die initiale Klausel aus den vier Literalen, die wir umformen wollten: \\((A\\vee\\overline{B}\\vee C\\vee\\overline{D})\\). Lange Rede, kurzer Sinn:<\/p>\n \\((A\\vee\\overline{B}\\vee C\\vee\\overline{D})\\)\u00a0\\(\\Leftrightarrow\\)\u00a0\\(((A\\vee\\overline{B}\\vee h_1)\\wedge(C\\vee\\overline{D}\\vee\\overline{h_1})\\)<\/p>\n<\/blockquote>\n Klauseln mit nur einem Literal bekommen zwei Hilfsvariablen, Klauseln mit zwei Literalen eine, Klauseln mit drei Literalen werden nicht angefasst und Klauseln mit mehr als drei Literalen werden nach dieser Vorgehensweise rekursiv in Klauseln mit drei Literalen umgewandelt.\u00a0Die Anzahl der Literale hat sich also nur linear erh\u00f6ht und wir haben einen Weg gefunden \\(SAT\\) auf \\(3SAT\\) in Polynomzeit zu reduzieren. Nun k\u00f6nnen wir auch \\(3SAT\\) f\u00fcr andere Schweinereien benutzen!<\/p>\n Antwort zum Lernziel<\/strong>: am beispiel von \\(3SAT\\) sehen wir die Reduktion, indem wir eine aussagenlogische Formel so umformen, dass wir zwar beliebig viele Klauseln, aber nur drei Literale pro Klausel haben. Schaffen wir diese Reduktion in Polynomzeit durchzuf\u00fchren, so ist sie uns gelungen.<\/p>\n Angabe einiger NP-vollst\u00e4ndigen Probleme<\/em><\/p>\n Im Skript werden noch weitere Probleme besprochen, die \\(NP\\)-vollst\u00e4ndig sind. Zwei davon sind \\(CLIQUE\\) und \\(IND\\_SET\\). Fangen wir doch zun\u00e4chst mit \\(CLIQUE\\) an. Definition (erneut geklaut aus dem Buch von Hr. Hoffmann):<\/p>\n Graph \\(G\\) mit Knotenmenge \\(V\\) und Kantenmente \\(E\\)<\/p>\n Fragestellung: Existieren \\(n\\) Knoten \\(v_1,…,v_n\\), die paarweise durch eine Kante aus \\(E\\) verbunden sind?<\/p>\n Menge \\(C=\\{v_1,…,v_n\\}\\) mit dieser Eigenschaft hei\u00dft \\(CLIQUE\\) der Gr\u00f6\u00dfe \\(n\\)<\/p><\/blockquote>\n In klaren Worten ist eine \\(CLIQUE\\) eine Menge von Knoten, die alle miteinander verbunden sind.<\/p>\n Beispiel<\/strong>:\u00a0\\(G_1\\) mit<\/p>\n \\(V_1=\\{1,2,3,4,5,6\\}\\) und<\/p>\n \\(E=\\{\\{1,2\\},\\{1,3\\},\\{2,3\\},\\{2,4\\},\\{2,5\\},\\{4,5\\},\\{5,6\\},\\{6,3\\},…\\}\\) (die Kanten in die andere Richtung habe ich aus Faulheit ausgelassen, denkt sie euch einfach dazu)<\/p>\n Hier haben wir Cliquen mit den Knoten \\(\\{1,2,3\\},\\{2,4,5\\},\\{2,3,5\\},\\{3,5,6\\}\\) identifiziert. Um zu beweisen, dass wir eine Clique der Gr\u00f6\u00dfe \\(n\\) gefunden haben, m\u00fcssen wir nur eine geeignete Knotenmenge raten und pr\u00fcfen ob paarweise durch eine Kante verbunden sind. Raten wir z.B. \\(C=\\{1,5,6\\}\\), m\u00fcssen wir auf folgende Kanten pr\u00fcfen: \\(\\{1,5\\},\\{1,6\\},\\{5,1\\},\\{5,6\\},\\{6,1\\},\\{6,5\\}\\). Jaja, ungerichteter Graph, ich wei\u00df: ein vorhandener Weg von \\(A\\) nach \\(B\\) impliziert den Weg von \\(B\\) nach \\(A\\). Aber wir tun uns mit der Pr\u00fcfung aller M\u00f6glichkeiten nicht weh, da dieser sowieso polynomiell beschr\u00e4nkt bleibt. So k\u00f6nnen wir aber auch ungerichtete Graphen in die Betrachtung mit einbeziehen.<\/p>\n Liegen die Kanten also in unserer Menge \\(E\\), so haben wir eine Clique gefunden. Man sieht leicht, dass mit der zu suchenden Cliquen-Gr\u00f6\u00dfe der Aufwand, d.h. die Anzahl der zu pr\u00fcfenden Kanten, quadratisch (\\(n^2\\)) in Abh\u00e4ngigkeit von \\(n\\) zunimmt. Da wir eine L\u00f6sung raten und sie mit quadratischem Aufwand pr\u00fcfen k\u00f6nnen, liegt unsere \\(CLIQUE\\in NP\\) .<\/p>\n Jetzt k\u00fcmmern wir uns um den aufwendigeren Teil, die \\(NP\\)-H\u00e4rte von \\(CLIQUE\\). Dazu reduzieren wir einfach \\(3SAT\\) auf \\(CLIQUE\\). Wir m\u00fcssen also eine Formel \\(M\\) konstruieren, dass gilt:<\/p>\n \\(M\\) ist erf\u00fcllbar \\(\\Leftrightarrow G\\) enth\u00e4lt eine Clique der Gr\u00f6\u00dfe \\(n\\)<\/p>\n Achtung: wir verfolgen den Weg von einer Formel zum Graphen und nicht anders herum. Wir \u00fcberf\u00fchren also eine Formel, die wahr wird wenn sie eine Belegung hat in einen Graphen, der genau bei dieser Belegung eine Clique hat. Machen wir das am besten an einem Beispiel:<\/p>\n Beispiel<\/strong>: \\((A)\\vee(\\neg{A}\\wedge{B})\\vee(\\neg{A}\\wedge{C})\\)<\/p>\n Wie basteln wir uns daraus einen Graphen? Nach folgenden Regeln:<\/p>\n Ganz einfach. Um es deutlicher zu machen, beschriften wir die Knoten mit \\(i,j\\). \\(i\\) ist die Nr. der Klausel und \\(j\\) die Nummer des Literals in der Klausel. Z.B. w\u00e4re der Knoten, der das Literal \\(A\\) in der ersten Klausel beschreibt, beschriftet mit \\((1,1)\\).<\/p>\n\\(B_{0,-1,B},B_{0,-1,\\#},B_{1,-1,B},B_{1,-1,\\#}\\)\n\\(B_{0,1,B},B_{0,1,\\#},B_{1,1,B},B_{1,1,\\#}\\)\n\\(B_{0,0,B},B_{0,0,\\#},B_{1,0,\\#},B_{1,0,\\#}\\)<\/blockquote>\n
\\(S_{0,S_0},S_{0,S_1},S_{1,S_0},S_{1,S_1}\\)<\/blockquote>\n
\\(P_{0,-1},P_{0,0},P_{0,1}\\)\n\\(P_{1,-1},P_{1,0},P_{1,1},\\)<\/blockquote>\n
\\(F=S\\wedge R\\wedge T\\wedge A\\)<\/blockquote>\n
Lernziel 4<\/h2>\n
Reduktion von \\(SAT\\) auf \\(3SAT\\)<\/h3>\n
\\(SAT\\leq_{pol}3SAT\\)<\/blockquote>\n
\\((\\upsilon_{1,1}\\vee\\upsilon_{1,2}\\vee …\\vee\\upsilon_{1,n})\\wedge(\\upsilon_{m,1}\\vee\\upsilon_{m,2}…\\vee\\upsilon_{m,n_{m}})\\)<\/blockquote>\n
\\((\\upsilon_{1,1}\\vee\\upsilon_{1,2}\\vee a_{1,1})\\wedge(\\overline{a_{1,1}}\\vee\\upsilon_{1,3}\\vee a_{1,2})\\wedge …\\wedge(\\overline{a_{1,n-3}}\\vee \\epsilon_{1,n_{1}-1}\\vee\\epsilon_{1,n_{1}})\\)<\/blockquote>\n
\n
![\"wertetabelle\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/wertetabelle.png\")
<\/a><\/p>\n\n
\n
Lernziel 5<\/h2>\n
![\"graph\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/graph.png\")
<\/a><\/p>\n\n
\n
![\"clique\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/clique.png\")
<\/a><\/p>\n![\"cliquewerte\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/cliquewerte.png\")
<\/a><\/p>\n![\"clique_uebung\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/05\/clique_uebung.png\")
<\/a><\/p>\n