Md9

[ Pobierz całość w formacie PDF ]
.� �Dowód przez indukcje ze wzgledu na wymiar kostki.zawiera droge Hamiltona� � �zawiera droge Hamiltona z do.składa sie z dwóchZałóżmy, że � �zhiperkostek.Droga w zaczyna sie w punkcie.W pierszej hiperkostce (tej�0 na poczatku każdego wierzchołka) przechodzi do , potem kraw� � do� edzia�i w drugiej hiperkostce (tej z 1 na poczatku każdego wierzchołka) w odwrotnym kierunkudo.Cykl Hamiltona w tworzy tak zwany kod Graya.Jest to ciag wszyskich elemen-�towych ciagów bitów, każdy wystepuje raz, każde dwa kolejne różnia sie jednym bitem� � � �oraz ostatni ciąg różni się jednym bitem od pierwszego.1.13 Rozgłaszanie wiadomościGraf może przedstawiać sieć połaczeń.Wierzchołki sa agentami, a kraw�� edzieto łacza, którymi agenci moga sie komunikować.Wyobrazmy sobie, że jeden agent posia-� � �da jakaś wiadomość, która chce przekazać wszystkim innym agentom w sieci.Reguły sa� � �nastepujace.Komunikacja odbywa sie synchronicznie w taktach.W każdym takcie każdy� � �agent może przekazać wiadomość jednemu swojemu sasiadowi.�Powyższy problem nazywa sie problemem rozgłaszania.Poniżej pokażemy, że można�go bardzo efektywnie rozwiazać, jeżeli graf jest hiperkostka.B� traktować� � edziemyciag bitów jako przedstawienie dwójkowe liczby naturalnej.�28 Rozdział 1.Grafy (nieskierowane)Rysunek 1.14: HiperkostkaNajpierw prześledzmy działanie tego protokułu na hiperkostce (rysunek 1.14).Załóżmy, że wierzchołek jest żródłem wiadomości.W pierwszym takcie przeka-zuje on ja do wierzchołka.Zauważmy, że po pierwszym takcie wiadomość jest�znana wierzchołkom o numerach mniejszych od 2 i, że te wierzchołki tworza hiperkostke� �wymiaru 1.W drugim takcie przekaże wiadomość do wierzchoł-wierzchołekka , a wierzchołek do.Po drugim takcie wiadomość znaja�wierzchołki numerach mniejszych od 4 i tworza � wymiaru 2.W trzecimo � one hiperkostketakcie przekazuje wiadomość do , do , do, a do.Tak wiec po trzech taktach wszystkie wierzchołki w�znaja wiadomość.�Protokół rozsyłania wiadomości w hiperkostceNa poczatku wiadomość ma wierzchołek.�Powtarzaj dlaw -tym takcie każdy wierzchołek przekazuje wiadomość do wierzchołka.Aby pokazać poprawność tego protokołu, pokażemy przez indukcje, że po -tymtakcie wiadomość jest znana wszystkim wierzchołkom o numerach mniejszych od.Przed pierwszym taktem wiadomość jest znana wierzchołkom o numerach mniejszychod , czyli wierzchołkowi 0.Załóżmy, że przed -tym taktem wiadomość jest znana1.14.Zbieranie informacji 29�wszystkim o numerach od.S to dokładnie wierzchołkiwierzchołkom mniejszych a�postaci , gdzie (jeżeli to jest pustym ciagiem).W-tym takcie każdy taki wierzchołek przekaże wiadomość do , czyli po-tym takcie wiadomość beda znały wszystkie wierzchołki, które maj pierwszych� � a na�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 doinnego grafu, który zawiera hiperkostke.�1.14 Zbieranie informacjiHiperkostka jest także wygodna struktura do zbierania informacji, gdy chcemy do jed-� �nego wierzchołka zebrać informacje od wszystkich wierzchołków.Informacje te należyprzesyłać w odwrotnym kierunku niż w protkóle rozsyłania.Zakładamy, że przesyłane�informacje sa łaczone w pakiety i wierzchołek może przesłać w jednym takcie cały pakiet� �zawierajacy kilka informacji.�Protokół zbierania wiadomości w hiperkostcePowtarzaj dlaw -tym takcie każdy wierzchołek postaci , gdzieprzesyła swój pakiet do wierzchołka ,Przykład 1.43 Prześledzmy działanie tego protokułu na hiperkostce (rysunek 1.14).W pierwszym takcie wierzchołek przekazuje swoją wiadomość do , wierzchołekdo , wierzchołek do , a wierzchołek do.W drugim takcie wierzchołek przekazuje zebrane wiadomości (swoją i te, kt.oreotrzymał 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 PlotkowaniePlotkowanie polega na tym, że na poczatku każdy wierzchołek ma jakaś wiadomość i� �chce ja rozesłać do wszystkich innych wierzchołków w grafie.�Znajac protokoły do zbierania i rozsyłania wiadomości możemy zaprojektować proto-�kół plotkowania, który najpierw zbiera wszystkie informacje do jednego w� a nastepnieezła, �rozsyła je do wszystkich wierzchołków.1.16 Zadania1.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 relacja równoważności.�6.Narysuj wszystkie grafy ze zbiorem wierzchołków.Które z nich sa�izomorficzne?7.Narysuj możliwie jak najwiecej nieizomorficznych grafów z czterema wierzchoł-�kami.8.Narysuj dwa nieizomorficzne grafy z ta sam� (możliwie jak najmniejsza) liczba� a � �wierzchołków.9.Narysuj dwa nieizomorficzne drzewa z ta sam� (możliwie jak najmniejsza) liczba� a � �wierzchołków.10.Narysuj dwa nieizomorficzne grafy z ta sam� (możliwie jak najmniejsza) liczba� a � �wierzchołków i ta sam� liczba kraw�� a � edzi.11.Narysuj dwa nieizomorficzne grafy, które maja ta sam� liczba wierzchołków stop-� � a �nia , dla każdego.12.Zastosuj algorytm przeszukiwania grafu w głab (wszerz) do grafów z rysunków 1.1�i 1.10.13.Zkonstruuj drzewa spinajace dla grafów z rysunków 1.1 i 1.10.�14.Korzystajac z drzew spinajacych z poprzedniego zadania, znajdz zbiór cykli funda-� �mentalnych dla grafów.15.Zmodyfikuj algorytm przeszukiwania grafu wszerz tak, aby wyznaczał on takżedrzewo spinajace (złożone z tych kraw� którymi przeszedł algorytm).Zastosuj� edzi,ten algorytm do grafów z rysunków 1.1, 1.7 i 1.10.16.Sprawdz, które grafy przedstawione na rysunkach w tym rozdziale posiadaja cykl�(lub droge) Eulera.�17.Sprawdz, które grafy przedstawione na rysunkach w tym rozdziale posiadaja cykl�lub droge Hamiltona.�18.Zastosuj algorytm kolorowania z nawrotami do grafu z rysunku 1.7.19.Znajdz graf, dla którego heurystyka przedstawiona w podrozdziale o kolorowaniugrafów nie znajduje optymalnego kolorowania.20.Narysuj hiperkostke.Wskaż w niej cykl Hamiltona.Prześledz na niej protokół�rozsyłania wiadomości.1.17.Problemy 311.17 ProblemyOto algorytm konstrukcji minimalnego drzewa spinajacego dla grafu�: (1) edzizaczynamy od zbioru wszystkich kraw� grafu , (2) sortujemykraw� według długości, od najdłuższej do najkrótszej (3) dla każdej kraw�edzie edziusuwamy ja z , jeżeli jej usuniecie nie rozspójnia grafu.� �Udowodnij poprawność tego algorytmu.Zastosuj powyższy algorytm do grafu z rysunku 1.9a.Niech bedzie dowolnym grafem z wagami kraw� , a� edzidowolnym minimalnym drzewem spinajacym.Pokaż, że dla dowolnego wierzchołka�do należa te kraw� wychodzacych z , które maja najkrótsze wagi, to znaczy,� edzie �� edziamijeżeli i sa dwiema kraw� przyległymi do takimi, że oraz , to [ Pobierz całość w formacie PDF ]

download @ ebook @ pdf @ pobieranie @ do ÂściÂągnięcia

Tematy