Przeskocz do treści

Delta mi!

Loading

O modelowaniu przydziału częstotliwości za pomocą kolorowania grafów

Krzysztof Węsek

o artykule ...

  • Publikacja w Delcie: listopad 2014
  • Publikacja elektroniczna: 31-10-2014
  • Autor: Krzysztof Węsek
    Afiliacja: Wydział Matematyki i Nauk Informacyjnych, Politechnika~Warszawska
  • Wersja do druku [application/pdf]: (286 KB)

Teoria grafów to gałąź matematyki, do której powstania impuls dało liczące sobie już ćwierć tysiąclecia słynne zagadnienie mostów królewieckich, rozwiązane przez Leonharda Eulera. Osobiście lubię patrzeć na matematykę nie tylko jako na zbiór problemów ciekawych samych w sobie, ale również jak na model rzeczywistości, narzędzie pozwalające efektywniej radzić sobie z rzeczywistymi zmartwieniami. Obecnie teoria grafów staje się jednym z najpopularniejszych takich narzędzi, używanym chętnie przez matematyków (na rzecz innych gałęzi tej nauki), informatyków, fizyków, chemików, a nawet socjologów. Niniejszy artykuł ma na celu przedstawienie tego, jak zagadnienie kolorowania grafów służyć może za narzędzie przydatne w przydzielaniu częstotliwości nadajnikom w jednym z modeli sieci radiowej.

obrazek

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!

obrazek

Klasyczne i ułamkowe kolorowanie grafów

Przypomnijmy, że grafem nazywamy parę math gdzie math to zbiór wierzchołków, a math to pewien zbiór par wierzchołków z math 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 math ponumerowanych liczbami math 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 math 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:

Definicja. math-kolorowaniem grafu math nazywamy takie przyporządkowanie wierzchołkom kolorów spośród math kolorów, że każde wierzchołki połączone krawędzią mają różne kolory. Liczbę chromatyczną math definiujemy jako minimalne math dla którego istnieje math-kolorowanie grafu math

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

obrazek

Przykład schematu nadawania długości 3

Przykład schematu nadawania długości 3

obrazek

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

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 math Nadal wymagamy, aby w jednym cyklu pracy każdy nadajnik otrzymał sumarycznie jedną jednostkę czasu, ale tym razem podzielmy cały cykl pracy (ponownie math odcinków) na odcinki długości math Z tego wynika, że każdy nadajnik powinien otrzymać math odcinków, czyli math różnych liczb - sprowadza się to do tzw. ułamkowego kolorowania grafów:

Definicja. math-kolorowaniem grafu math nazywamy takie przyporządkowanie wierzchołkom math-elementowych zbiorów kolorów spośród math kolorów, że każde wierzchołki połączone krawędzią otrzymują rozłączne zbiory. Ułamkową liczbę chromatyczną math grafu math definiujemy jako kres dolny liczb math dla których istnieje math-kolorowanie grafu math

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 math-kolorowanie jest tym samym co math-kolorowanie. Oznacza to, że podejście ułamkowe może dać tylko oszczędność w stosunku do klasycznego kolorowania!

Podkreślmy, że ułamek math 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 math

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 ( math bądź math ) 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).

obrazek

Ten graf wymaga czterech kolorów

Ten graf wymaga czterech kolorów

obrazek

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

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 math istnieje graf, który wymaga więcej niż math 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:

Problem 2. Ile kolorów potrzeba, aby pokolorować (nieskończony) graf math którego wierzchołkami są wszystkie punkty płaszczyzny euklidesowej math a dwa punkty/wierzchołki są połączone krawędzią, jeśli znajdują się w odległości dokładnie 1?

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

obrazek

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

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 math - 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 math grafem math :

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

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 math w klasyczny sposób. Oto najlepszy znany wynik.

Twierdzenie 4 ([1]). Istnieje math-kolorowanie grafu math

Takie kolorowanie daje uniwersalny cykl nadawania długości math

obrazek

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

Twierdzenie 5 ([2]). Istnieje math-kolorowanie grafu math

Takie kolorowanie daje uniwersalny cykl nadawania długości

display-math

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 math co oznacza, że każdy punkt ma math kolorów.

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

Im większe math 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 math można jednak zejść nawet poniżej math

Twierdzenie 6 ([2]). Istnieje ciąg math-kolorowań math taki, że

display-math

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łę!