Podręcznik

Grafem prostym (niezorientowanym) nazywamy parę G = (V, E), gdzie V jest niepustym skończonym zbiorem wierzchołków, a E jest skończonym zbiorem krawędzi – nieuporządkowanych par różnych elementów ze zbioru V [1.18]. Przykład grafu podany jest na rys. 1.2. Jest to graf, w którym zbiór wierzchołków V = {<i>v</i>₁, <i>v</i>₂, <i>v</i>₃, <i>v</i>₄, <i>v</i>₅, <i>v</i>₆} oraz zbiór krawędzi E = {(<i>v</i>₁,<i>v</i>₆), (<i>v</i>₂,<i>v</i>₃), (<i>v</i>₂,<i>v</i>₄), (<i>v</i>₂,<i>v</i>₅), (<i>v</i>₂,<i>v</i>₆), (<i>v</i>₃,<i>v</i>₄), (<i>v</i>₃,<i>v</i>₆), (<i>v</i>₅,<i>v</i>₆)}.

Dowolny podzbiór wierzchołków, w którym każde dwa wierzchołki są połączone krawędzią nazywamy kliką. Klikę, która nie jest zawarta w żadnej istotnie innej klice, nazywamy maksymalną. Najliczniejszą klikę w danym grafie nazywamy największa kliką. Klikami dla grafu z rys. 1.2 są następujące zbiory:

V = {<i>v</i>₂, <i>v</i>₃, <i>v</i>₄}, V = {<i>v</i>₂, <i>v</i>₃, <i>v</i>₆}, V = {<i>v</i>₂, <i>v</i>₅, <i>v</i>₆}.

Zbiorem niezależnym nazywamy dowolny zbiór wierzchołków, które nie są sąsiednie w danym grafie. Analogicznie określamy pojęcie maksymalnego zbioru niezależnego. Przykłady zbiorów niezależnych dla grafu z rys. 1.2: 

V = {<i>v</i>₁,<i>v</i>₄, <i>v</i>₅}, V = {<i>v</i>₁, <i>v</i>₃, <i>v</i>₅}, V = {<i>v</i>₄, <i>v</i>₆}, V = {<i>v</i>₁, <i>v</i>₂}.

Rys.  1.2. Przykład grafu

Obliczanie klik nie jest zadaniem łatwym. Można się zastanawiać jak obliczyć maksymalne kliki w grafie podanym na rys. 1.3.

Rys.  1.3. Przykład grafu

Dlatego problem obliczania maksymalnych klik warto sprowadzić do problemu obliczania maksymalnych klas zgodności definiowanych dla danej relacji zgodności. Najpierw zdefiniujemy ważne pojęcie iloczynu kartezjańskiego.

Iloczynem kartezjańskim zbiorów A i B, oznaczanym A × B nazywamy zbiór wszystkich par uporządkowanych (a, b), takich że pierwszy element pary należy do zbioru A (a Î A), natomiast drugi do B (b Î B), czyli:

A × B = {(<i>a</i>,<i>b</i>): <i>a</i> </span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:Symbol"><span style="color:black">Î</span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black"> <i>A</i>, <i>b</i> </span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:Symbol"><span style="color:black">Î</span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black"> <i>B</i>}

Relacją nazywamy dowolny podzbiór iloczynu kartezjańskiego zbiorów A, B. Typowe własności relacji na zbiorze A (czyli A × A) są definiowane następująco:

• zwrotność: $\forall\ a\in\ A:aRa$
• symetria:  $\forall\ a,b\in\ A:aRb(bRa$
• przechodniość:  $\forall\ a,b,c\in\ A:aRb,\ bRc\ (bRc$

Najważniejszymi relacjami stosowanymi w syntezie logicznej są relacje równoważności i zgodności.

Relację, która jest zwrotna i symetryczna nazywamy relacją zgodności. Relacja zgodności jest również nazywana relacją nierozróżnialności. Relacja zgodności klasyfikuje elementy zbioru w nierozłączne podzbiory zwane Systemem zbiorów (więcej na ten temat w rozdz. 1.4).

Szczególnym przypadkiem relacji zgodności jest relacja równoważności. Relacja równoważności jest relacją zwrotną, symetryczną i przechodnią. Relacja równoważności dzieli zbiór A na rozłączne podzbiory, co w konsekwencji prowadzi do pojęcia podziału (zbioru) tworząc bardzo użyteczny w syntezie logicznej rachunek podziałów omawiany w następnym rozdziale.

Własności relacji zgodności pokrywają się z intuicyjnym rozumieniem zgodności:

a) każdy element jest zgodny z samym sobą,

b) jeśli element v₁ jest zgodny z v₂, to również v₂ jest zgodny z v₁,

c) jeśli v₁ jest zgodny z v₂ oraz v₂ jest zgodny z v₃, to z tego nie wynika, że v₁ jest zgodny z v₃.

Relacja zgodności umożliwia wprowadzenie pojęcia Maksymalnych Klas Zgodności (MKZ).

Zbiór par określających relację zgodności nazywa się zbiorem par zgodnych. Pary zgodne umożliwiają wyznaczenie maksymalnych zbiorów zgodnych.

Zbiór V = {<i>v</i>₁,</span><span style="line-height:150%"><span style="font-family:Symbol">¼</span></span><span style="line-height:150%">,<i>v_p</i>} nazywamy maksymalnym zbiorem zgodności (maksymalną klasą zgodności), jeżeli każda para v_i, v_j wzięta z tego zbioru jest zgodna oraz nie istnieje żaden inny zbiór elementów zgodnych V’, zawierający V. Maksymalne zbiory zgodne są odpowiednikiem klik w grafie prostym.

Z powyższego wynika, że w celu obliczania klik metodą maksymalnych klas zgodności należy:

1. Zapisać pary SPRZECZNE (v_i, v_j), (v_k, v_l), (v_p, v_q), w postaci koniunkcji dwuskładnikowych sum (v_i + v_j)(v_k + + v_l)(v_p, + v_q) ¼
2. Koniunkcję dwuskładnikowych sum przekształcić do minimalnego wyrażenia boolowskiego typu suma iloczynów v_iv_jv_k + v_pv_qv_rv_s +…

Wtedy MKZ są uzupełnieniami zbiorów reprezentowanych przez składniki iloczynowe tego wyrażenia.

W podobny sposób możemy sformułować algorytm obliczania Maksymalnych Zbiorów Niezależnych (MZN).

1. Zapisać pary zgodne (v_i, v_j), (v_k, v_l), (v_p, v_q), ¼w postaci koniunkcji dwuskład­nikowych sum (v_i, + v_j)(v_k, + v_l)(v_p, + v_q) ¼
2. Koniunkcję dwuskładnikowych sum przekształcić do minimalnego wyrażenia boolowskiego typu suma iloczynów v_iv_jv_k + v_pv_qv_rv_s +…

Wtedy MZN są uzupełnieniami zbiorów reprezentowanych przez składniki iloczynowe tego wyrażenia.