# pog4

## Zadanie 1

Załóżmy że d(a,b) zwraca nam odległość pomiędzy punktami a i b

Baza i = 1
Dodajemy tylko bezpośrednie więc d(a, b) = 1

Izba
Załóżmy, że dla $T^{i} \ d(a, b) \leq 2^{i-1}$. Pokażmy dla $T^{i+1}$
Weźmy dwie dowolne ścieżki z $T^{i}$ takie, że d(a,b) i d(c, d) są maksymalne w $T^{i}$. Wtedy
$d(a, b) + d(c, d) \leq 2^{i-1} + 2^{i-1} \leq 2^{i}$
Więc chyba śmiga?

~Czarek

<!-- info -->
## Zadanie 2
T(x) := E(n, x)
T(x) := E(m, x)
T(x) := T(y), E(y, x)

## Zadanie 3
N(x) := E(n, x)
M(x) := E(m, x)
N(x) := N(y), E(y, x)
M(x) := M(y), E(y, x)
F(x) := M(x), N(x)

## Zadanie 4
T(x, y) := E(n, x), E(n, y)
T(x, y) := E(x, a), E(y, b), T(a, b)

## Zadanie 5

P(x,y) = istnieje ścieżka od x do y
Q(x,y) = relacja T z zadania 4go.

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

Q jak wyżej

T(x,y) :- Q(x,z), P(z,y)

wyjaśnienie: wiemy, że mamy wierzchołki x i z o równej odległości od n. Jeśli istnieje ścieżka od z do y, to możemy stworzyć ściężkę od n do y przez z. Wówczas istnieją ścieżki (n,x) i (n,y) o różnych długościach.

<!-- info -->

## Zadanie 6
Chyba się nie da ale nwm

Spróbuję jebnąć dowodzik formalny, ale możliwe, że się wyjebę (~czarek):


Musielibyśmy móc przedstawić nasz program Datalogu w algebrze relacji, a zapytanie o pary wierzchołków które nie posiadają ścieżki między sobą nie jest bezpiecznym zapytaniem (uzależnione od dziedziny), więc nie da się przedstawić go w algebrze relacji, a tym samym nie istnieje poprawny program w Datalogu który moglibyśmy utworzyć.

Pzdr.

### Można robić tak

!!!

Jeśli się okazało, że w kolejnej iteracji programu jednak istnieje ścieżka od $x$ do $y$, to nie zajdzie $T^n \subseteq T^{n+1}$.

#A - B - C - D
na początku (ścieżki dł 1) ans:
A-C
A-D
B-D
(ścieżki dł 2) ans:
A-D
nie zachodzi ckd

## Zadanie 7
T(x, y, c) := E(x, y, c)
T(x, y, c) := T(x, z, c), T(z, y, c)
K(x, y) := T(x, y, c)

## Zadanie 8
Chyba też się nie da

!!!

Analogicznie do 6go, jeśli w iteracji $n$ mamy parę wierzchołków $(x,y)$ (czyli wszystkie ścieżki pomiędzy nimi były multikolorowe do tego momentu), to możliwe, że w $n+1$ iteracji znajdziemy ścieżkę jednokolorową, czyli $(x,y)$ nie będzie w $T^{n+1}$, czyli nie zajdzie $T^n \subseteq T^{n+1}$.

## Zadanie 9
T(x, y, c) := E(x, y, c)
T(x, y, c) := T(x, z, c), T(z, y, c)
D(x, y, $c_{1}, c_{2}$) := T(x, z, $c_{1}$), T(z, y, $c_{2}$)
D(x, y, $c_{1}, c_{2}$) := D(x, z, $c_{1}, c_{2}$), D(z, y, $c_{1}, c_{2}$)
Ans(x, y) := D(x, y, $c_{1}, c_{2}$)
Ans(x, y) := T(x, y, c)

## Zadanie 10