Problem nadajników

Nasze rozważania zaczniemy od rzeczywistego zagadnienia. Wyobraźmy sobie, że mamy sieć nadajników/odbiorników radiowych (telefonii komórkowej) - każdy nadajnik ma ograniczony zasięg bezpośredniej komunikacji z innymi nadajnikami. Urządzenia nadające na tej samej częstotliwości mają to do siebie, że mogą się wzajemnie zagłuszać, interferować - tzn. jeśli pewien nadajnik "słyszy" jednocześnie sygnały z dwóch innych, to tak naprawdę nic "nie słyszy". Zakładamy, że stacje znajdujące się w swoim zasięgu (czyli mogące "rozmawiać" bezpośrednio między sobą) szybko uzgodnią nadawanie i nie będą jednocześnie wysyłać wiadomości do wspólnego sąsiada. Problem pozostaje z takimi stacjami, które nie mogą się komunikować bezpośrednio (są poza swoim zasięgiem), ale mają inną stację w swoim wspólnym zasięgu - a zatem mogą się czasem zagłuszać.

Jak można zapobiec zagłuszaniu w takich przypadkach? Możemy przydzielić każdej stacji pewien odcinek czasu (tzw. szczelinę czasową) w taki sposób, aby nadajniki potencjalnie konfliktowe otrzymały rozłączne odcinki czasu. Ale jak to zrobić? Z pomocą przyjdzie nam teoria grafów!

Klasyczne i ułamkowe kolorowanie grafów

Przypomnijmy, że grafem nazywamy parę gdzie to zbiór wierzchołków, a to pewien zbiór par wierzchołków z nazywanych krawędziami. W naturalny sposób przedstawimy konflikty w naszej sieci w postaci grafu: wierzchołki będą odpowiadać nadajnikom, a krawędziami połączymy te nadajniki, które mogą się zagłuszać, tzn. te, które są poza swoim zasięgiem, ale mają inny nadajnik w swoim wspólnym zasięgu. Obok mamy przykład tworzenia grafu konfliktów pewnej sieci - kolorowe linie oznaczają konflikt, czyli krawędź w grafie.

Przyjmijmy w tworzonym modelu, że wszystkie nadajniki są równie ważne, tzn. w ramach cyklu pracy każda stacja ma otrzymać pewną jednostkę czasu dostępnego do nadawania. Nasze pierwsze podejście będzie następujące: jeden cykl nadawania będzie składał się z ponumerowanych liczbami odcinków czasu jednostkowej długości i będziemy starali się tak przydzielić wierzchołkom liczby, aby wierzchołki połączone krawędzią (sąsiedzi w grafie) otrzymały różne odcinki czasu. Im mniejsze dla którego uda się to zrealizować, tym lepiej - cykl nadawania będzie krótszy przy tej samej skuteczności. To, co właśnie opisaliśmy, to tak naprawdę klasyczne zagadnienie kolorowania grafu:

Zatem w naszym podejściu najlepszy przydział szczelin czasowych odpowiada kolorowaniu grafu sieci na kolorów.

Przykład schematu nadawania długości 3

Przykład schematu nadawania długości 2,5 - wyraźna oszczędność

A gdybyśmy podzielili odcinki czasu przydzielane nadajnikom na mniejsze kawałki, powiedzmy długości Nadal wymagamy, aby w jednym cyklu pracy każdy nadajnik otrzymał sumarycznie jedną jednostkę czasu, ale tym razem podzielmy cały cykl pracy (ponownie odcinków) na odcinki długości Z tego wynika, że każdy nadajnik powinien otrzymać odcinków, czyli różnych liczb - sprowadza się to do tzw. ułamkowego kolorowania grafów:

Warto zwrócić uwagę na fakt, że ułamkowa liczba chromatyczna danego grafu jest zawsze nie większa niż liczba chromatyczna - wynika to z faktu, że -kolorowanie jest tym samym co -kolorowanie. Oznacza to, że podejście ułamkowe może dać tylko oszczędność w stosunku do klasycznego kolorowania!

Podkreślmy, że ułamek odpowiada długości jednego cyklu pracy, przy cały czas ustalonej skuteczności jednego cyklu. A zatem dążymy do cyklu pracy długości

Jak znaleźć przydział czasów?

Jak więc możemy znaleźć konkretny schemat nadawania? Niestety, sprawa nie jest łatwa.

Wydaje się, że mogą być dwa podejścia:

I

Obliczeniowe: stosowanie algorytmów kolorowania do konkretnych sieci/grafów;

II

Uniwersalne: użycie narzędzi teoretycznych do uzyskania uniwersalnych rozwiązań.

W przypadku I problem polega na tym, że nie znamy szybkich algorytmów kolorowania grafów - zarówno w przypadku klasycznego kolorowania, jak i w ułamkowej wersji. Oznacza to, że dla małych grafów znajdziemy optymalne rozwiązanie, ale w przypadku większych grafów optymalne rozwiązanie ( bądź ) jest poza zasięgiem możliwości obliczeniowych dzisiejszych komputerów. Można wtedy stosować tzw. algorytmy przybliżone: takie, które działają w rozsądnym czasie, ale najpewniej nie podadzą nam najlepszego kolorowania, a jedynie jakieś "niezłe" (zazwyczaj używające o wiele większej liczby kolorów niż teoretycznie niezbędna).

Ten graf wymaga czterech kolorów

Siedem kolorów wystarczy (przekątne sześciokątów mają długość

Okazuje się, że w przypadku II można zaproponować tak naprawdę uniwersalną makietę wykorzystującą taką skończoną liczbę kolorów, która zadziała dla każdej, dowolnie skomplikowanej sieci nadajników. Nie jest to oczywiste, bowiem ogólnie dla każdego istnieje graf, który wymaga więcej niż kolorów (i podobnie dla ułamkowej wersji kolorowania). Jednak geometryczne własności układu nadajników upraszczają sytuację.

Kolorowanie płaszczyzny

Przed przedstawieniem wspomnianej makiety przyda się wstęp historyczny. Otóż w latach 60. XX wieku Edward Nelson zadał następujące pytanie:

Być może w pierwszej chwili to zaskakuje, ale taki graf można pokolorować na kolorów. Mimo sporego zainteresowania tym problemem nie udało się poprawić znanego od kilkudziesięciu lat oszacowania

Najoszczędniejsze znane kolorowanie klasyczne (średnica sześciokątów to 1)

Dalszy tok działania będzie taki, że punkty na płaszczyźnie będą oznaczały wszelkie możliwe miejsca, gdzie może znaleźć się nadajnik. Postawmy pytanie: w jakiej odległości mogą się znajdować nadajniki konfliktowe, gdy zasięg każdego nadajnika jest równy 1? Potencjalnie konfliktowa jest każda para nadajników w odległości z przedziału - tylko wtedy nadajniki nie mogą się kontaktować bezpośrednio, ale mogą (choć nie muszą) mieć inny nadajnik we wspólnym zasięgu. Zastąpmy więc graf grafem :

• zbiór wierzchołków to ;
• krawędzią łączymy punkty leżące w odległości z przedziału

Kolorowanie tego grafu będzie stanowiło uniwersalną makietę: wystarczy położyć konkretną sieć na płaszczyźnie makiety, odczytać kolory poprawnego kolorowania tej sieci, a co za tym idzie, poprawny schemat nadawania.

Najpierw więc pokolorujmy w klasyczny sposób. Oto najlepszy znany wynik.

Takie kolorowanie daje uniwersalny cykl nadawania długości

Teraz obejrzymy przykład oszczędności za pomocą ułamkowej wersji kolorowania.

Takie kolorowanie daje uniwersalny cykl nadawania długości

Rysunek wymaga objaśnienia, bo powinien być trójwymiarowy: Wyróżnione pary sześciokątów z liczbami od i do viii to fragmenty kolejnych warstw ułożonych z tych samych stu, ale oczywiście odpowiednio przesuniętych kolorów (te sześciokąty odpowiadają kolorom 1 i 2, a pozostałe są usytuowane względem nich tak, jak na dolnej warstwie) - warstw jest co oznacza, że każdy punkt ma kolorów.

Rozwijając tę metodę, można znaleźć kolejne kolorowania, dążące do wartości (np. dla i otrzymujemy jakość lepszą niż ).

Im większe tym drobniejszy podział cyklu nadawania na kawałki - ale zbyt mocny podział może z technicznych powodów być niemożliwy do zastosowania.

Dla bardziej skomplikowanych figur i naprawdę bardzo dużych można jednak zejść nawet poniżej

Na koniec warto zwrócić uwagę na fakt, iż zastosowanie uniwersalnej makiety nie tylko nie wymaga obliczeń dla każdej nowej sieci, ale nawet działa w przypadku nadajników ruchomych - nie trzeba niczego wyliczać na nowo, wystarczy uwzględniać przesuwanie się nadajników zgodnie z makietą. Czasem teoria ma naprawdę wielką siłę!