# BD 30.03.2021

## zad.1
### Piotr Piesiak
Z wykładu wiemy, że jeśli zapytanie koniunkcyjne jest spełnione w danej bazie danych, to równoważnie kanoniczna baza danych (indukowana przez to zapytanie) jest homomorficzna do tej bazy danych. Tzn. $D |= Q \iff \exists h: D^Q \rightarrow D$. Stwórzmy zatem zapytanie koniunkcyjne zawierające wszystkie krawędzie z grafu G. Wtedy $D^Q = G$. Będzie ono miało postać $Q(x_1, x_2, ... , x_n) :- E(x_1, x_i),E(x_j,x_z)\ldots$.

Z zadania 5 listy 3, wiemy że istnienie homomorfizmu między grafem G, a kliką 3 wierzchołkową jest równoważne 3- kolorowalności grafu G. Wystarczy zatem sprawdzić czy zapytanie Q będzie spełnione w bazie danych postaci $K_3$. Wtedy z lematu i poprzedniej listy, graf G będzie 3-kolorowalny.

Czas ewaluacji takiego zapytania to $O(3^n)$, gdzie n to rozmiar zapytania (ograniczony).

### Maurycy Borkowski
Stwórzmy zapytanie $Q$ biorąc krawędzie z grafu $G$ jako składowe zapytania. Oczywiście kanoniczna baza zapytania $Q$ to będzie $G$: $G = D^Q$

A bazę weźmy $D = K_3$

Z lematu z wykładu wiemy, że $Q$ jest spełnione w $D$ wtw. gdy istnieje homomorfizm $h: D^Q \rightarrow D$

Dodatkowo wiemy z L3Z5, że stwierdzenie czy graf jest 3 kolorowalny jest równoważne stwierdzeniu czy istnieje homomorfizm w klikę $K_3$ z badanego grafu.

$Q$ spełnione w $D (= K_3)$ $\overset{lemat}{\iff}$ istnieje $h: D^Q \rightarrow D = K_3$ $\overset{L3Z5}{\iff}$ $D^Q = G$ 3-kolorowalny

## zad.2
dla $2^i$ nie jest to prawda, ale dla $2^{i-1}$ już tak

### Jonatan Hrynko
Teza indukcyjna $T^n$ = $E \cup E^2 \cup \dots \cup E^{2^{n-1}}$

baza indukcji n = 1:
$T^1 = E$, czyli ścieżki długości $1 = 2^0 = 2^{1-1}$

krok indukcji:
dla każdego i < n mamy, że $T^i$ = $E \cup E^2 \cup \dots \cup E^{2^{i-1}}$
T(X, Y) :- T(X, Z), T(Z, Y)
zatem $T^n = \{(x, y) : E(x, y) ∨ \exists z (T^{n-1}(x, z) ∧ T^{n-1}(z, y))\}$
czyli w $T^n$ mamy wszystkie ścieżki długości 1, oraz ścieżki długości od 2 do $2\cdot2^{n-2} = 2^{n-1}$

### Michał Hetnar
$T^{n+1}=((a,b): E(a,b) \lor \exists z(T^n(a,z) \land T^n(z,b)) )$
$T^1$=E(a,b)=ściezka dł 1
dla n =1 2^n-1 =2^0 = 1
$B^n$-ścieżka dł n
$$T^n= B^{2pow(n-1)} \lor ... \lor B^1 $$
$T^{n+1}=((a,b): E(a,b) \lor \exists z((B(a,z)^{2pow(n-1)} \lor ... \lor B^1 ) )\land( B(z,b)^{2pow(n-1)} \lor ... \lor B^1) )$

$T^{n+1}=((a,b): E(a,b) \lor (B(a,b)^{2pow(n)} \lor ... \lor B^2 )$
$T^{n+1}=((a,b): B(a,b)^{n} \lor B(a,b)^{2pow(n)} \lor ... \lor B^2 \lor B^1)$

## zad.3.1
Maciej Zientara
T(x,y) = E(x,y)
T(x,y) = E(x,z), T(z,y)

WWSS = wszystkie wierzchołki spójnej składowej

dom(T(n,x)) $\cup$ dom(T(m,x))
WWSS zawierającej n
zsumowane z WWSS zawierającej m

Krzysztof Wiśniewski

## zad.3.2
Krzysztof Łyskawa
$Q() :- T(x)$
$T(x) :- R(x), S(x)$
$S(x) :- E(n, x)$
$S(x) :- E(y, x), S(y)$
$R(x) :- E(m, x)$
$R(x) :- E(y, x), R(y)$

Adam Turowski

$T(y)$ - do wierzchołka $y$ istnieje ścieżka z $n$ i $m$
$T(y)$ $:-$ $E(n, y), E(m, y)$
$T(y)$ $:-$ $E(n, y), E(m, z), N(z, y)$
$T(y)$ $:-$ $E(n, z), E(m, y), N(z, y)$
$T(y)$ $:-$ $E(n, z), E(m, x), N(z, y), N(x, y)$

$N(x, y)$ - istnieje ścieżka z $x$ do $y$
$N(x, y)$ $:-$ $E(x, y)$
$N(x, y)$ $:-$ $E(x, z), N(z, y)$

## zad.3.3
**Treść:** Zwróć pary wierzchołków, do których można dojść z wierzchołka n ścieżkami o tej samej długości.

------
Karol Machoś
**$T(x,y)$ - do wierzchołków $x$ i $y$ prowadzą równej długości ścieżki z $n$**
$T(x, y)$ $:-$ $E(n, x), E(n, y)$
$T(x, y)$ $:-$ $E(n, z), E(n, w), N(z, x, w, y)$

**$N(u,v,p,q)$ - z wierzchołka $u$ istnieje ścieżka do wierzchołka $v$, oraz z wierzchołka $p$ istnieje ścieżka do $q$ i są one równej długośći.**
$N(u, v, p, q)$ $:-$ $E(u, v), E(p, q)$
$N(u, v, p, q)$ $:-$ $E(u, a), E(p, b), N(a, v, b, q)$

-----------

Martyna Firgolska
SAME(X, Y) :- E(n, X), E(n, Y)
SAME(X, Y) :- SAME(A, B), E(A, X), E(B, Y)

## zad.3.4

#### Filip Komorowski

$T(x,y):-E(n,x),E(n,b),P(b,y)$
$T(x,y):-E(n,y),E(n,b),P(b,x)$
$T(x,y):-E(a,x),E(b,y),T(a,b)$

$P(u,w):-E(u,w)$
$P(u,w):-E(u,x),P(x,w)$

#### Łukasz Stasiak

zad4(X,Y) :- edge(n,X), temp(n,Y).
zad4(X,Y) :- edge(U,X), edge(V,Y),zad4(U,V).

temp(A,B) :- edge(A,C), edge(C,B).
temp(A,B) :- edge(A,C), temp(C,B).


## zad.4
**Treść:** Wiadomo, że graf jest 2-kolorowalny wtedy i tylko wtedy gdy nie zawiera cyklu o nieparzystej długości. Napisz zapytanie datalogowe Q() spenione w grafach, które nie są 2-kolorowalne.

----------------------
Martyna Firgolska

ODD(X, Y) :- E(X, Y)
EVEN(X, Y) :- ODD(X, Z), E(Z, Y)
ODD(X, Y) :- EVEN(X, Z), E(Z, Y)

ODDCYCLE() :- ODD(X, X)

------------------------
Karol Machoś

$Q(x)$ $:-$ $N(x, x)$ <- istnieje ściezka o nieparzystej długości z x do x (cykl o nieparzystej długości)

$N(x, y)$ $:-$ $E(x, y)$
$N(x, y)$ $:-$ $E(x, z), P(z, y)$
$P(x, y)$ $:-$ $E(x, z), N(z, y)$

======
szukamy cyklu nieparzystej długości

T(x,y) = E(x,y)
T(x,y) = E(x,a), T(a,b), E(b,y)

uruchamiamy z T(x,x)

## zad.5
**Treść:** 1. Czy można napisać zapytanie datalogowe spełnione wtw gdy w grafie nie ma ścieżki pomiędzy wyróżnionymi wierzchołkami n i m ?
2. Czy można napisać zapytanie datalogowe speanione wtw gdy graf zawiera parzystą liczbę wierzchołków?

### Jonatan Hrynko
1. NIE
Ta własność nie jest zachowywana dla rozszerzenia grafu.
Możemy zrobić zapytanie, które nam zwróci wierzchołki na ścieżce z n do m, ale nie możemy odwrócić tego zapytania.
2. NIE
Załóżmy, że istnieje takie zapytanie Datalogowe, które nam zwraca prawdę wtw. gdy graf zawiera parzystą liczbę wierzchołków. Zapytanie to korzysta z bazy danych krawędzi E(X, Y), zatem jeśli do grafu dodamy wierzchołek izolowany, to zapytanie zwróci taki sam wynik, co dla grafu bez tego dodanego wierzchołka izolowanego, zatem zwraca taki sam wyniki niezależnie od parzystości.

### Maciej Zientara
1)
T(x,y) = E(x,y)
T(x,y) = E(x,z), T(z,y)

dom(T(n,x)) \ dom(T(m,x))

(dostaniemy zbiór pusty, jeżeli jest ścieżka z n do m,
wpp dostaniemy zbiór wierzchołków spójnej składowej z n)

2)
NIE
można sprawdzać parzystość ścieżki, ale graf może mieć
rozgałęzienia nie wchodzące w skład rozpatrywanej ścieżki

np dla drzewa, gdzie mamy korzeń i 5 wierzchołków z nim połączonych
najdłuższa ścieżka ma długość 2 krawędzi ale nie uwzględni przy jej
przechodzeniu pozostałych 4 wierzchołków

## zad.6
-