# BD 23.03.2021
Na rozgrzewkę pokaż, jak przepisać zapytanie $P_7 (x, y)$ używając wyłącznie perspektyw
$P_2 (x, y)$ i $P_3 (x, y)$ .

$P_7 (x, y) = (\exists{y_1, y_2}) P_2(x, y_1) \land P_2(y_1, y_2) \land P_3(y_2, y)$

## Zadanie 1
Michał Dymowski
Załóżmy, że mamy zapytanie koniunkcyjne $\phi (x,y)$ zbudowane z $P_3,P_4$ i równoważne $P_5$.
Zbudujemy graf w którym dla pewnej pary wierzchołków (x,y) formuła $\phi (x,y)$ jest spełniona, ale nie leżą one w odległości 5 od siebie.
Konstrukcję grafu zaczynamy od stworzenia wierzchołków $x,y$, oraz po jednym wierzchołku dla każdego kwantyfikatora (będzie on odpowiadał symbolowi wiązanemu przez ten kwantyfikator).
Zbiór wierzchołków stworzonych do tej pory nazwę $Z$.
Dla każdego atomu $\phi$, który (zawsze) jest postaci $P_{3,4}(\alpha_k,\alpha_j)$ dodaję do grafu odpowiednio 2,3 nowe wierzchołki i łączę je krawędziami tak, aby powstała ścieżka $\alpha_k \rightarrow \alpha_j$ długości odpowiednio 3,4.
Na mocy konstrukcji z jednej strony formuła jest spełniony dla wierzchołków (x,y), a z drugiej strony oba te wierzchołki należą do $Z$ więc ich odległość jest nieujemną kombinacją 3 i 4, więc nie może być równa 5.
Przykłady:

Michał Hetnar
zapytanie koniunkcyjne to takie które używa tylko $\exists$ i $\land$ i formuł atomowych w tym przypadku $P_4(x,y)$ i $P_3(x,y)$

jeżeli zwiążemy dowolne dwa takie atomy $\exists y_1(P_{3/4}(x,y_1)\land P_{3/4}(y_1,y))$ otrzymamy formuły atomowe o ścieżece wiekszej niż 5

jeżeli zwiążemy dowolne dwa takie atomy $\exists y_1(P_{3/4}(x,y_1)\land P_{3/4}(y,y_1))$ formuła atomowa nie mówi nic o ścieżce z x do y (x-3/4->$y_1$<-3/4-y) (jest sprzeczna dla grafu x->a->b->c->d->y)

jeżeli zwiążemy dowolne dwa takie atomy $\exists y_1(P_{3/4}(y_1,x)\land P_{3/4}(y_1,x))$ formuła atomowa nie mówi nic o ścieżce z x do y(jest sprzeczna dla grafu x->a->b->c->d->y) wiec nie zrobimy zniej $\land$ zapytania o $P_5$

każde kolejne wiązanie ma do dyspozycji nowe atomy które opisują dłużą scieżkę albo już wykluczają jakieś przypadki, albo nie opisują ścieżki.Więc za pomocą tych kwantyfikatorów nie jesteśmy wstanie zrobić zapytania mo wszystkie ścieżki dł 5

## Zadanie 2
Karol Machoś

$P_5(a,b)\Leftrightarrow \exists c(P_4(a,c)\land \forall d(P_3(d,c)\implies P_4(d,b))$

#### Lemat:

$\exists c(P_4(a,c)\land P_1(c,b))\Leftrightarrow \exists c(P_4(a,c)\land\forall d(P_3(d,c)\implies P_4(d,b)))$

#### Interpetacja:
W przypadku zapisanej przez nas formuły, z warunku $P_4(a,c)$ wynika, że musi istnieć conajmniej jedno takie $d$ (leżące na ścieżce $P_4(a,c)$) w którym zachodzi $P_3(d,c)$. Zatem $P_1(c,b)$ będzie zachodzić wtedy i tylko wtedy gdy dla takich $d$ będzie zachodzić również $P_4(d,b)$.

Zatem zapisana przez nas formuła jest równoważna formule:
$$P_5(a,b)\Leftrightarrow \exists c(P_4(a,c)\land P_1(c,b))$$

Piotr Piesiak

$$
P_5(x,y) = (\exists a)(P_4(x,a) \land (\forall b)(P_3(b,a) \implies P_4(b,y)))
$$

digraph {
    edge [dir=none]
    x,y [fillcolor="cadetblue1:chocolate1"; style=filled]
    a,b [color = green; style = filled]
    x -> b;
    b -> c;
    c -> d;
    d -> a;
    a -> y;
    {rank = same x; b;c;d;a;y}
}

digraph {
    edge [dir=none]
    x,y,y1 [color = red; style=filled]
    a,b,b1 [color = green; style = filled]
    
    x -> b;
    b -> c;
    c -> d;
    d -> a;
    a -> y;
    b1 -> c1;
    c1 -> d1;
    d1 -> a;
    b2 -> b1;
    b2 -> b3;
    b3 -> b4;
    b4 -> y1;
    {rank = same x; b;c;d;a;y}
    {rank = same b1; c1;d1;}
    {rank = same b2;b3;b4;y1}
}

## Zadanie 3

#### Maciej Zientara
a)
G ma jeden wierzchołek v z pętelką
funkcja h zamienia wszystkie wierzchołki G' na v

w grafie G musi być 'więcej' krawędzi niż w grafie G'
to oznacza, że każdy wierzchołek, który miał krawędz w G'
musi też mieć w G, ale nawet jeżeli nie było jakiejś krawędzi w G'
może się ona pojawić w G

b)
izomorfizm - bijekcja będąca homomorfizmem, której funkcja odwrotna też jest homomorfizmem

homomorficznie równoważne grafy nie muszą być izomorficzne

G1 to cykl abc
a b
c

G2 to połączone cykle abc i adc
a b
d c

w ten sposób cykl z G1 -> G2 jest reprezentowany (abc -> abc)
oraz oba cykle z G2 -> G1 (abc -> abc oraz adc -> abc)

grafy homomorficznie równoważne, ale nie izomorficzne

### Krzysztof Wiśniewski


## Zadanie 4
### Krzysztof Łyskawa

Weźmy dwa grafy $G$ i $H$ będące cyklami o parzystej liczbie wierzchołków. Niech $V(G) = \{x_{1}, x_{2}, ..., x_{2m}\}$ i $V(H) = \{y_{1}, y_{2}, ..., y_{2n}\}$ będą zbiorami wierzchołków $G$ i $H$ a $E(G) = \{e_{1}, e_{2}, ..., e_{2m}\}$ i $E(H) = \{e'_{1}, e'_{2}, ..., e'_{2n}\}$ zbiorami krawędzi $G$ i $H$ takimi, że $e_{1} = (x_{1}, x_{2}), e_{2} = (x_{2}, x_{3}), ..., e_{2m} = (x_{2m}, x_{1})$ i $e'_{1} = (y_{1}, y_{2}), ..., e'_{2n} = (y_{2n}, y_{1})$.

Teraz niech $f: V(G) → V(H)$ taka, że $f(x_{2k}) = y_{1}$ i $f(x_{2k-1}) = y_{2}$, gdzie $k \in \{1, 2, ..., m\}$. Wtedy $(\forall e_{i} \in E(G)) f(e_{i}) = e'_{1}$ czyli $f$ jest funkcją homomorficzną z $G$ w $H$.

Analogicznie tworzymy funkcję $g: V(H) → V(G)$, która będzie homomorficzna z $H$ do $G$, czyli pokażemy że dwa dowolne cykle o parzystej liczbie wierzchołków są homomorficznie równoważne

### Jonatan Hrynko

Cykl parzystej długości jest dwudzielny, więc możemy taki graf pokolorować na dwa kolory.
Zauważmy, że istnieje homorfizm z cyklu parzystej długości na graf złożony z dwóch wierzchołków połączonych jedną krawędzią. Po prostu wierzchołki o kolorze 1 mapujemy na wierzchołek 1, a wierzchołki o kolorze 2 na wierzchołek 2. Taki 2-wierzchołkowy graf zawiera się w każdym cyklu długości parzystej.
Konstrukcja homomorfizmów dla grafów $G_1$, $G_2$:
Kolorujemy wierzchołki grafu na dwa kolory, a następnie w każdym z grafów ustalamy dwa wierzchołki $x_i, y_i$ połączone krawędzią, $(x_i, y_i) \in E(G_i)$.
$h_1: G_1 → G_2$,
$h_1(u) = x_2$ if $col_1(u) = col_1(x_1)$ else $y_2$

BSO: $col_1(x_1) = col_1(u)$
$(u, v) \in E(G_1)$
$(h_1(u), h_1(v)) = (x_2, y_2) \in E(G_2)$

$h_2: G_2 → G_1$,
$h_2(v) = x_1$ if $col_2(v) = col_2(x_2)$ else $y_1$

BSO: $col_2(x_2) = col_2(u)$
$(u, v) \in E(G_2)$
$(h_2(u), h_2(v)) = (x_1, y_1) \in E(G_1)$

Zatem $G_1, G_2$ są homomorficznie równoważne

## Zadanie 5

### Adam Turowski

Pokazać że problem kolorowania grafu można sprowadzić do istnienia homomorfizmu pomiędzy dwoma grafami

tzn. istnieją takie grafy $G1$, $G2$, że graf $G$ jest 3-kolorowalny wtw gdy istnieje homomorfizm
$G_1$ $\rightarrow$ $G_2$.

Konstrukcja:
$G_1$ = $G$
$G_2$ = $K_3$

Załóżmy, że kolory odpowiadają liczbom $1, 2, 3$
W $K_3$ mamy 3 krawędzie łączące wierzchołki o kolorach $1, 2, 3$.

#### Implikacja w prawo

Jeśli graf $G$ jest 3-kolorowanlny, to po jego pokolorowaniu nie istnieje krawędź łącząca dwa wierzchołki tego samego koloru. Przyporządkujmy więc każdemu wierzchołkowi w $G_1$ wierzchołek o tym samym kolorze w $K_3$. Żeby pomiędzy dwoma wierzchołkami po takim przyporządkowaniu nie było krawędzi w $K_3$ to musiałyby one być tego samego koloru, ale w $G_1$ są tylko krawędzie łączące wierzchołki róznych kolorów, zatem takie przyporządkowanie jest homomorfizmem.

#### Implikacja w lewo

Jeśli istnieje homomorfizm $G_1$ $\rightarrow$ $G_2$, to znaczy, że w $G_1$ każda krawędź łączy dwa wierchołki różnych kolorów, a to znaczy, że $G_1$ jest 3-kolorowalny.

### Filip Komorowski

digraph{
    edge [dir=none]
    1 -> 2
    2 -> 3
    3 -> 1
    {rank = same 2; 3}
}

Niech $G_1 := G$ , a $G_2 := K_3$.

#### $G$ jest 3-kolorowalny $\implies$ istnieje homomorfizm $h: G_{1} \rightarrow G_{2}$

Załóżmy, że $G$ jest 3-kolorowalny. Wtedy pokolorujmy wierzchołki w grafie $G$ kolorami 1, 2, 3. Teraz możemy utworzyć funkcję h: $G_{1} \rightarrow G_{2}$, taką że przyporządkowujemy wierzchołki o kolorze 1 do wierzchołka 1, o kolorze 2 do wierzchołka 2 oraz o kolorze 3 do wierzchołka 3.

#### Istnieje homomorfizm $h: G_{1} \rightarrow G_{2}$ $\implies$ $G$ jest 3-kolorowalny

Załóżmy, że istnieje homomorfizm $h: G_{1} \rightarrow G_{2}$.
Załóżmy nie wprost, że $G$ nie jest 3-kolorowalny. W takim razie jeśli i tak pokolorujemy graf G używając jedynie 3 kolorów to znajdą się dwa wierzchołki pokolorowane tym samym kolorem, które posiadają miedzy sobą krawędź.
Ale jeżeli istniej homomorfizm $h: G_{1} \rightarrow G_{2}$, a wiemy że $G_{2}$ to klika 3 wierzchołkowa to graf G musi być grafem, którego wierzchołki da się podzielić na 3 grupy, takie że żaden wierzchołek w danej grupie nie ma krawędzi z innym wierzchołkiem w tej samej grupie. Sprzeczność.

Zapisanie grafu G w bazie danch możemy zrobić liniowo względem liczby krawędzi

## Zadanie 6
Martyna Firgolska
**Treść:**
Mówimy, że formuła rachunku zdań jest w postaci 3CNF, gdy jest w
koniunkcyjnej postaci normalnej, a dodatkowo każda klazula zawiera najwyżej 3 zmienne. Przykład formuły 3CNF: $(p ∨ ¬q ∨ r) ∧ (s ∨ ¬r)$.
Rozważmy problem spełnialności formuł rachunku zdań zwany 3SAT: dla danej formuły w postaci 3CNF, rozstrzygnij czy istnieje wartościowanie ją spełniające.
Pokaż, że problem 3SAT można wyrazić jako problem istnienia homomorfizmu pomiędzy bazami danych, tzn. pokaż, że jesli potrafisz rozwiązywać problem
istnienia homomorfizmu to potrafisz także rozwiązywać problem 3SAT.
Twoja konstrukcja powinna działać w czasie wielomianowym.

**Rozwiązanie**
Niech $G_1$ to graf którego wierzchołkami są literały występujące w klauzulach (może być wiele wierzchołków z tym samym literałem) \, i który ma wszystkie krawędzie oprócz krawędzi między literałami z tej samej klauzuli i pomiędzy $p$ i $\neg p$

Niech $G_2$ to graf pełny o ilości wierzchołków równej ilości klauzul.

Niech $\phi$ to formuła w postaci 3CNF (o n klauzulach) Jeśli istnieje wartościowanie spełniające $\phi$ to wtedy w $G_1$ istnieje klika o mocy równej ilości klauzul (n) - znajdziemy ją w ten sposób, że wyróżnimy wszystkie literały(wierzchołki) które w tym wartościowaniu są prawdziwe. Zauważmy, że musi być co najmniej jeden wyróżniony wierzchołek dla każdej klauzuli oraz że jeśli p jest wyróżnione to $\neg p$ nie jest. Zatem mamy przynajmniej n wyróżnionych wierzchołków z których żadne 2 nie są swoimi negacjami i należą do innych klauzul - zatem z definicji grafu $G_1$ tworzą graf pełny.
Zatem istnieje homomorfizm z $G_2$ do $G_1$

Załóżmy że istnieje homomorfizm z $G_2$ do $G_1$ wtedy obraz $G_2$ w tym homomorfizmie musi być podgrafem pełnym $G_1$. Jeśli wszystkie literały z tego podgrafu uznamy za prawdziwe to jest to wartościowanie spełniające $\phi$