15.04.2010

Porządkowanie wierzchołków grafów trójkątnych drogą obliczeń lokalnych

Podstawowym zagadnieniem w obliczeniach lokalnych jest możliwość uzyskaniu globalnego efektu końcowego drogą obliczeń lokalnych. Obliczenie lokalne określone jest na ogół dla grafów o z góry ograniczonych rozmiarach (zazwyczaj będących otoczeniami pojedynczych wierzchołków), a następnie przedłużane tożsamościowo do grafów o dowolnych rozmiarach.

Grafem trójkątnym jest graf, w którym każdy cykl jest albo trójkątem, albo zawiera przekątną; grafy takie zasługują na specjalną uwagę, gdyż ich klasa zawiera zarówno drzewa (nie zawierające cykli) jak i grafy zupełne (zawierające wszystkie możliwe cykle). Referat dotyczy jednego z zagadnień istotnych dla obliczeń lokalnych w grafach trójkątnych, a mianowicie ustalaniu kolejności wszystkich wierzchołków grafów trójkątnych drogą porządkowania ich podgrafów lokalnych.

We wcześniejszych pracach podano szereg istotnych własności obliczeń lokalnych na grafach trójkątnych, np. istnienie sprawiedliwej elekcji lidera, możliwość konstrukcji drzewa rozpinającego, redukcji lub ekspansji grafów z zachowaniem podstawowych własności. Algorytm uporządkowania wierzchołków drogą lokalnych uzgodnień był podany jedynie dla drzew; tematem niniejszego referatu jest rozszerzenie zakresu działania tego algorytmu na wszelkie grafy trójkątne i tym samym rozwiązanie ostatniego z podstawowych zagadnień dotyczących obliczeń lokalnych dla grafów trójkątnych. Istotnym okazuje się tutaj właściwe przyjęcie klasy lokalnych podgrafów. W odróżnieniu od dotychczasowych publikacji dotyczących lokalności, jako lokalne podgrafy przyjęto tu domknięte sąsiedztwo pojedynczej krawędzi. Uzyskany algorytm okazuje się w ten sposób naturalnym uogólnieniem algorytmu dla drzew, w których lokalnym pografem jest pojedyńcza krawędź.