---
# System prepended metadata

title: pog4

---

# pog4

## Zadanie 1
![](https://i.imgur.com/SCPLbzU.png)

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?

![](https://i.imgur.com/wsuZPI0.jpg)
~Czarek

<!-- info -->
![](https://i.imgur.com/nHdeMRc.png)
## Zadanie 2
![](https://i.imgur.com/7QYNUB5.png)
T(x) := E(n, x)
T(x) := E(m, x)
T(x) := T(y), E(y, x)

## Zadanie 3
![](https://i.imgur.com/mSNOfZj.png)
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
![](https://i.imgur.com/CpBKem6.png) 
T(x, y) := E(n, x), E(n, y)
T(x, y) := E(x, a), E(y, b), T(a, b) 

## Zadanie 5
![](https://i.imgur.com/rmmGanw.png)

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 -->
![](https://i.imgur.com/iGHOJvE.png)

## Zadanie 6
![](https://i.imgur.com/0R78bGh.png)
Chyba się nie da ale nwm

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

![](https://i.imgur.com/HRIUN4G.png)

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.
![](https://i.imgur.com/3Tk7FIB.png)
![](https://i.imgur.com/mEg2V3V.png)

### Można robić tak

![](https://i.imgur.com/Ziu24sP.png)
!!!
![](https://i.imgur.com/uAXQelN.png)

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
![](https://i.imgur.com/uyX2D6i.png)
nie zachodzi ckd

## Zadanie 7
![](https://i.imgur.com/mkyj0V5.png)
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
![](https://i.imgur.com/4LP9p0l.png)
Chyba też się nie da 

![](https://i.imgur.com/Ziu24sP.png)
!!!
![](https://i.imgur.com/uAXQelN.png)

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
![](https://i.imgur.com/zqIpueK.png)
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
![](https://i.imgur.com/MMaU3Ow.png)
