Implikationsgraph, starke Zusammenhangskomponenten

Aufrufe: 41     Aktiv: 11.06.2021 um 10:03

0



Hallo, ich muss folgende Aufgabe lösen und komme nicht darauf, wie man das Prinzip der Induktion hier anwenden soll. Was ich mir denke, ist, dass wohl die Formel (!a => b) => (!b => a) ein grundsätzlicher Ansatz wäre.
gefragt

Punkte: 14

 

Kommentar schreiben

1 Antwort
1
Um zu zeigen, dass $\overline L$ eine starke Zusammenhangskomponente ist, musst du zeigen, dass $\overline L$ stark zusammenhängend ist und jede Übermenge nicht stark zusammenhängend ist.

Beginnen wir damit, dass $\overline L$ stark zusammenhängend ist. Das heißt, wir müssen zu zwei beliebigen Knoten in $\overline L$ einen Pfad angeben. Seien, dem Hinweis folgend, $\bar l$ und $\bar{l'}$ zwei Knoten in $\overline L$ mit $l,l'\in L$ und wir wollen einen Pfad von $\bar{l'}$ nach $\bar l$ finden. Da $L$ stark zusammenhängend ist, gibt es einen Pfad von $l$ nach $l'$, sagen wir $(k_0=l,k_1,\ldots,k_{n-1},k_n=l')$ sei die Abfolge der Knoten in diesem Pfad. Jetzt zeigen wir per Induktion über $n$, dass $(\bar k_n=\bar{l'},\bar k_{n-1},\ldots,\bar k_1,\bar k_0=\bar l)$ ein Pfad in $\bar L$ ist. Für $n=0$ ist die Aussage klar, dann ist $\bar l=\bar{l'}$ und der Pfad ist trivial. Gelte nun für jeden Pfad der Länge $n$ in $L$, dass es einen Pfad durch die negierten Knoten in umgedrehter Reihenfolge gebe, und sei $(k_0,\ldots,k_{n+1})$ ein Pfad der Länge $n+1$ in $L$. Dann ist $(k_0,\ldots,k_{n})$ ein Pfad der Länge $n$, auf diesen können wir also die Induktionsvoraussetzung anwenden und erhalten einen Pfad $(\bar k_n,\ldots,\bar k_0)$ in $\bar L$. (Vielleicht fällt dir auf, dass wir bis jetzt noch überhaupt keine Eigenschaft dieses speziellen Graphen verwendet haben, alles bis jetzt gilt für jeden Graphen und ist sozusagen nur das (zugegebenermaßen etwas umständliche) "Setup" für das jetzt folgende, viel kürzere Argument, das den Beweis verfollständigt.) Jetzt musst du nur noch begründen, dass du $\bar k_{n+1}$ davor hängen kannst, also dass es eine Kante von $\bar k_{n+1}$ nach $\bar k_n$ gibt. Das kannst du entweder mit der von dir erwähnten logischen Formel machen (wenn du in einer vorigen Aufgabe schon gezeigt hast, dass der Graph tatsächenlich die Implikationen beschreibt) oder auch einfach mit der Definition der Kanten im Graph.

Zum Schluss musst du dann noch zeigen, dass es keine größere stark zusammenhängende Menge gibt. Das geht am besten per Widerspruch: Angenommen, $M\supsetneq\bar L$ wäre stark zusammenhängend. Nach obigem Argument ist dann auch $\overline M$ stark zusammenhängend. Was kannst du über den Zusammenhang von $\overline M$ und $L$ aussagen? Wie kommst du dadurch zu einem Widerspruch?
Diese Antwort melden
geantwortet

Punkte: 9.96K
 

Kommentar schreiben