Ludzie pragną czasami się rozstawać, żeby móc tęsknić, czekać i cieszyć się z powrotem.
Zauważmy, że po pierwszym takcie wiadomość jest
znana wierzchołkom o numerach mniejszych od 2 i, że te wierzchołki tworz¸a hiperkostk¸e
wymiaru 1. W drugim takcie wierzchołek
przekaże wiadomość do wierzchoł-
-
-"
-
-)-
ka
, a wierzchołek
do
. Po drugim takcie wiadomość znaj¸a
wierzchołki o numerach mniejszych od 4 i tworz¸a one hiperkostk¸e wymiaru 2. W trzecim
-
-
-
-
-
-
takcie
przekazuje wiadomość do
,
do
,
do
-)-
-
-
-
-)-
, a
do
. Tak wi¸ec po trzech taktach wszystkie wierzchołki w
znaj¸a wiadomość.
Protokół rozsyłania wiadomości w hiperkostce
Na pocz¸atku wiadomość ma wierzchołek
.
0
-> ?((?(@
Powtarzaj dla
7
(
0
w -tym7
(
takcie każdy wierzchołek
przekazuje wiadomość do wierzchołka
.
0
Aby pokazać poprawność tego protokołu, pokażemy przez indukcje, że po -tym (
takcie wiadomość jest znana wszystkim wierzchołkom o numerach mniejszych od
.
Przed
pierwszym taktem wiadomość jest znana wierzchołkom o numerach mniejszych
-
0
od
, czyli wierzchołkowi 0. Załóżmy, że przed -tym taktem wiadomość jest znana
1.14. Zbieranie informacji
29
7
(
wszystkim wierzchołk
7
7
(
om o numerach mniejszych
(
od
. S¸a to dokładnie wierzchołki
# -A
0
-
postaci
, gdzie
(jeżeli
to
jest 7
(
pustym
(
ci¸agiem). W
0
-
-tym takcie każdy taki wierzchołek przekaże wiadomość do
, czyli po
0
0
-tym takcie wiadomość b¸ed¸a znały wszystkie wierzchołki, które maj¸a( na
pierwszych
bitach zera, czyli wszystkie wierzchołki o numerach mniejszych od
.
Protokół ten (po małych przeróbkach) można także stosowa ć do grafu pełnego lub do innego grafu, który zawiera hiperkostk¸e.
1.14
Zbieranie informacji
Hiperkostka jest także wygodn¸a struktur¸a do zbierania informacji, gdy chcemy do jednego wierzchołka zebrać informacje od wszystkich wierzchołków. Informacje te należy przesył¸ać w odwrotnym kierunku niż w protkóle rozsyłania. Zakładamy, że przesyłane informacje s¸a ł¸aczone w pakiety i wierzchołek może przesłać w jednym takcie cały pakiet zawieraj¸acy kilka informacji.
Protokół zbierania wiadomości w hiperkostce
0
- (?(?(?
Powtarzaj dla
7
(
(
0
-
&-A
w
-tym takcie każdy wierzchołek postaci
7
(
, gdzie
przesyła swój pakiet do wierzchołka
,
Przykład 1.43 Prześledźmy działanie tego protokułu na hiperkostce (rysunek 1.14).
-
W pierwszym takcie wierzchołek
przekazuje swoj ˛
a wiadomość do
, wierzchołek
-
-
-
-
-
-
-
-)-
-
-
do
, wierzchołek
do
, a wierzchołek
do
.
-
W drugim takcie wierzchołek
przekazuje zebrane wiadomości (swoj ˛
a i te, kt.ore
-)-
-
otrzymał w poprzednim takcie) do
, a wierzchołek
do
.
-
W trzecim takcie wierzchołek
przekazuje zebrane wiadomości do
. a wierz-
-
-
-
chołek
do
.
1.15
Plotkowanie
Plotkowanie polega na tym, że na pocz¸atku każdy wierzchołek ma jak¸aś wiadomość i chce j¸a rozesłać do wszystkich innych wierzchołków w grafie.
Znaj¸ac protokoły do zbierania i rozsyłania wiadomości możemy zaprojektować protokół plotkowania, który najpierw zbiera wszystkie informacje do jednego w¸ezła, a nast¸epnie rozsyła je do wszystkich wierzchołków.
1.16
Zadania
1. Ile krawędzi ma graf pełny
?
2. Ile maksymalnie krawędzi może mieć graf z
wierzchołkami?
30
Rozdział 1. Grafy (nieskierowane)
-> ?(?((@
3. Ile jest grafów ze zbiorem wierzchołków
?
4. Ile krawędzi ma dwudzielny graf pełny
?
$
5. Udowodnij, że izomorfizm grafów jest relacj¸a równoważności.
6. Narysuj wszystkie grafy ze zbiorem wierzchołków
3
2
4
. Które z nich s¸a
izomorficzne?
7. Narysuj możliwie jak najwi¸ecej nieizomorficznych grafów z czterema wierzchoł-
kami
3
2
4
.
/
8. Narysuj dwa nieizomorficzne grafy z t¸a sam¸a (możliwie jak najmniejsz¸a) liczb¸a wierzchołków.
9. Narysuj dwa nieizomorficzne drzewa z t¸a sam¸a (możliwie jak najmniejsz¸a) liczb¸a wierzchołków.
10. Narysuj dwa nieizomorficzne grafy z t¸a sam¸a (możliwie jak najmniejsz¸a) liczb¸a wierzchołków i t¸a sam¸a liczb¸a kraw¸edzi.
11. Narysuj dwa nieizomorficzne grafy, które maj¸a t¸a sam¸a liczb¸a wierzchołków stopnia , dla każdego .
12. Zastosuj algorytm przeszukiwania grafu w gł¸ab (wszerz) do grafów z rysunków 1.1
i 1.10.