fbpx

Cześć, wracam do Ciebie dziś z kolejnym tematem matematycznym. We wpisie numer 31 przedstawiłem Ci podstawowe aspekty związane z teorią grafów. Czułem lekki niedosyt i postanowiłem dopisać drugą część, gdzie poruszę bardziej zaawansowane aspekty grafów. Mogą one być ciekawym dopełnieniem w programistycznym portfolio.

Uważam, że teorię grafów powinien znać każdy programista i cieszę się, że poznajesz grafy właśnie na moim blogu.

W dzisiejszym wpisie poruszę temat:

  • kolorowania grafów
  • grafów eulerowskich i hamiltonowskich
  • przepływu w sieciach
  • łańcuchów Markowa
  • kostek

Jak widać, sporo ciekawie brzmiących pojęć. 

Zaczynajmy!

Zatrzymaj się!


Książka „Programistą być” to obowiązkowa pozycja dla każdego zainteresowanego programowaniem!

Jest to zdecydowanie najlepsza na polskim rynku książka na temat programowania! Zyskasz przewagę w branży IT i osiągniesz dużo jako deweloper.

Z książki dowiesz się między innymi o tym:

  • Czy matematykastudia techniczne i język angielski są konieczne do tego, by rozpocząć pracę jako programista?
  • Gdzie szukać informacji o programowaniu i w jaki sposób się uczyć?
  • Jak znaleźć pierwszą pracę i w jaki sposób rozwijać swój programistyczny potencjał?
  • Czym na co dzień zajmuje się programista?
  • Czy każdy może zostać programistą?

I wiele, wiele więcej…


Zaawansowane aspekty grafów — Kolorowanie grafów

Pokolorować graf możemy na trzy sposoby. Po pierwsze, kolory możemy przypisać do wierzchołków grafu. Po drugie analogicznie możemy pokolorować krawędzie. Ostatnim, trzecim sposobem jest pokolorowanie ścian grafu, czyli pól, które powstały na skutek połączenia wierzchołków za pomocą krawędzi. 

Kolorowanie wierzchołków

Na pierwszy ogień idzie kolorowanie wierzchołków. To najczęściej rozważany przypadek, jeśli chodzi o kolorowanie grafów. Jeśli mamy graf, który nie ma pętli, to powiemy, że jest on k-kolorowalny. Dla nas istotne są dwie rzeczy. Po pierwsze, nie możemy pokolorować wierzchołków, które są ze sobą połączone krawędzią. Drugim aspektem, który będzie odnosić się do całego zagadnienia kolorowania grafów, jest liczba chromatyczna. Jest to minimalna liczba kolorów niezbędnych do pokolorowania grafu. Zobacz rysunek poniżej, który jest pokolorowany prawidłowo, ponieważ żadne dwa wierzchołki sąsiadujące ze sobą nie mają tego samego koloru. Liczba chromatyczna w tym przypadku wynosi 4, ponieważ nie da się tego grafu pokolorować w mniej niż cztery kolory. Trzy kolory nie da rady, dwa tym bardziej. O jednym kolorze możemy zapomnieć. 

Kolorowanie wierzchołków

Kolorowanie krawędzi

Drugim, lecz nieco mniej popularnym sposobem na pokolorowanie grafu jest kolorowanie krawędzi. Podobnie jak z wierzchołkami, tu też musimy pamiętać o jednej rzeczy. Krawędzie wchodzące do tego samego wierzchołka muszą mieć różne kolory. Zobacz, że na pierwszy rzut oka w tym przypadku mamy liczbę chromatyczną równą pięć. Czy uda Ci się tak ustawić kolory, by obniżyć tę liczbę do czterech i pozbyć się jednej barwy z grafu?

Kolorowanie krawędzi

Kolorowanie map

Ostatnia z trzech możliwości kolorowania. Kolorowanie map to nic innego jak kolorowanie ścian utworzonych z połączenia wierzchołków oraz krawędzi. Ściany niejako wewnątrz grafu nazwiemy ścianami skończonymi. Każdy graf posiada również ścianę nieskończoną, czyli taką, która jest wokół grafu.

Analogia do map wzięła się stąd, że mapy, które znamy z atlasów geograficznych, są zawsze pięknie pokolorowane. Sąsiednie kraje nie mogą mieć tego samego koloru, ponieważ ciężko byłoby je odróżnić. 

Z tego problemu wynikło zagadnienie nazwane zagadnieniem czterech barw. Wynika z niego, że każdą mapę jesteśmy w stanie pomalować czterema tylko kolorami. Twierdzenie o czterech barwach jest jednym z ważniejszych twierdzeń w świecie grafów. Pozwól jednak, że nie będę Cię męczył dowodami i całością twierdzenia, bo jest to zbyt obszerny temat, a blog ten dotyczy programowania, niezaawansowanych aspektów matematyki. 

Zaawansowane aspekty grafów — Grafy eulerowskie i hamiltonowskie

Czas na dwa specyficzne grafy. Graf eulerowski i graf hamiltonowski to grafy od nazwiska Eulera oraz Hamiltona. Tych dwóch matematyków światowej sławy bardzo przyczyniło się do rozwoju teorii grafów.

Graf eulerowski

Zacznijmy od grafu eulerowskiego. W skrócie jest to taki graf, w którym znajduje się cykl Eulera. Cykl Eulera natomiast to taki cykl, w którym przechodzimy przez wszystkie krawędzie grafu dokładnie jeden raz. Zagadnienie, które jest popularne w kontekście grafów eulerowskich to tak zwany problem mostów królewieckich. Więcej o tym problemie pisałem w sekcji ciekawostek we wpisie numer 10.

Z cyklu Eulera wynika bardzo ciekawe twierdzenie. Aby można było zbudować taki cykl w grafie, to liczba wierzchołków nieparzystego stopnia musi wynosić 0 lub 2. 

W programowaniu wykorzystuje się algorytm ˙Fleury’ego, który służy do szukania cykli Eulera w grafie. Zastosowań tego algorytmu i cykli eulerowskich jest wiele. Najczęściej możemy przeczytać o zastosowaniu w urządzeniach o nazwie ploter i do optymalnego wycinania w papierze elementów. Przy cyklach Eulera mówimy również o problemie chińskiego listonosza. W 1962 roku chiński matematyk ´
Mei-Ko Kwan sformułował następujący problem:

Listonosz roznosząc listy, musi przejść przez wszystkie ulice w swojej dzielnicy co najmniej jeden raz i wrócić na pocztę. Ponieważ jest człowiekiem leniwym, chciałby mieć jak najkrótszą do przejścia trasę. Znalezienie takiej trasy jest problemem, który nazwano problemem chińskiego listonosza.

Oczywiście kolejnym dużym problemem, podobnym do wspomnianego wyżej jest problem komiwojażera, który również bazuje na cyklach Eulera. Więcej o tym problemie wspominam w kolejnym, 46 wpisie.

Graf hamiltonowski

Drugim, jeszcze ciekawszym przykładem grafu jest graf hamiltonowski. Jest to graf stojący w opozycji do grafu eulerowskiego, ponieważ w tym przypadku liczy się taka ścieżka, która przechodzi przez wszystkie wierzchołki dokładnie jeden raz. Ścieżką taką nazwiemy ścieżką Hamiltona. Od strony programowania problem ten jest trudnym zagadnieniem. Nie ma bowiem żadnego algorytmu, który w 100% rozwiązuje ten problem. 

Znów odwołam się do problemu komiwojażera, który również jest podawany jako przykład problemu do rozwiązania z pomocą ścieżki Hamiltona. Im więcej wierzchołków w grafie, tym złożoność czasowa algorytmu rośnie. 

Zaawansowane aspekty grafów — Przepływ w sieciach

Bardzo ważnym tematem we współczesnym świecie informatyki jest tak zwany przepływ w sieciach. Mówimy tu o współczesnych systemach logistycznych, projektowaniu sieci komputerowych czy sieci telefonicznych lub energetycznych.

W takim przypadku projektuje się sieci tak, by były, jak najbardziej wydajne. By kurier przewiózł jak najwydajniej paczki, by ruch w sieci był optymalny czy ułożenie sieci energetycznych było jak najtańszym kosztem i przy jak najmniejszych stratach.

Przepustowość sieci odnosi się do digrafów, czyli grafów skierowanych. We wpisie numer 31 poruszałem temat grafów skierowanych bardziej szeroko.

Przepływ w grafie liczy się od wejścia (źródła) do ujścia. Zobacz obrazek poniżej.

Przepływ w sieci

Z perspektywy przepływu w sieci interesuje nas twierdzenie o maksymalnym przepływie i minimalnym przekroju. Problem z tym twierdzeniem jest taki, że pozwala znaleźć przepływ i przekrój dla małego grafu (sieci). Z natury jednak sieci na przykład powiązań logistycznych są gigantyczne, dlatego nie da się bezpośrednio wskazać, chociażby maksymalnego przepływu. 

Wyjaśnię jeszcze, czym jest przepływ maksymalny oraz przekrój minimalny. Przepływ maksymalny to taki, gdzie wartość przepływu (wartość łączna wag krawędzi) jest najwyższa. Wyznaczenie takiego przepływu pozwoli nam dowieźć najwięcej paczek do miast na mapie, przepuścić najwięcej bitów przez sieć w najkrótszym czasie lub przesłać energię elektryczną z jak najmniejszą stratą.

Jeśli mówimy o przekroju minimalnym, to jest to przekrój o najmniejszej przepustowości. Przekrój natomiast jest to zbiór krawędzi, które mają najmniejszą wagę. W przykładzie powyżej będą to wszystkie krawędzie z wagą równą 1.

Zaawansowane aspekty grafów — Łańcuchy Markowa

Opowiedziałem Ci nieco o przepływach w sieciach, to teraz czas na podobny temat. Również oparty na grafach skierowanych. Badania nad łańcuchami Markowa są popularne w genetyce i statystyce. Ważną rolę odegrały również w socjologii. 

Cały łańcuch Markowa opiera się na procesie Markowa, czyli prawdopodobieństwie zdarzeń występujących po sobie. Łańcuch Markowa przedstawiony w postaci grafu wyglądać może tak jak na obrazku poniżej.

Wyobraźmy sobie, że powyższy łańcuch jest drogą. Startujemy z centralnego punktu i prędzej czy później dotrzemy do lewego lub prawego skraju. Pod warunkiem, że będziemy losowo przesuwać się, raz w prawo, raz w lewo, a innym razem zakręcimy się w miejscu i wrócimy do miejsca, z którego wyruszyliśmy. Do tego możemy przyjąć założenie, że co minutę zmieniamy miejsce. Mamy więc trzy opcje:

  • prawo;
  • lewo;
  • kółko, pozostajemy w miejscu;

Całością zadania w tym przypadku będzie policzenie, w której minucie najprawdopodobniej dojdziemy do celu, jakim jest lewa albo prawa strona. Do takich obliczeń właśnie bardzo przydają się grafy i właśnie łańcuch Markowa.

Zaawansowane aspekty grafów — Kostki

Kolejnym ciekawym elementem grafów są kostki. Jest to specyficzny graf regularny nazywany kostką. Kostkę można sobie zwizualizować jako graf, który jest niejako przestrzenny. Każdy wierzchołek w takim grafie odpowiada ciągom połączonych z nią krawędzi. Wyobraź sobie sześcienną kostkę, którą narysujemy na płaskiej powierzchni. Może ona wyglądać tak, jak na rysunku poniżej.

Kostka

Jak możesz zauważyć, kostka ta jest trójwymiarowa, więc możemy ją nazwać 3-kostką. Ogólnie kostki mają pewien przedrostek przed myślnikiem, który mówi o ilości wymiarów. Spokojnie możemy mieć 1-kostkę, która będzie dwoma wierzchołkami połączonymi linią lub 2-kostka będąca kwadratem na płaszczyźnie.

Zauważ też, że każdy wierzchołek kostki jest zapisany 0 i 1, więc bardzo przypomina to liczby binarne.

Zobacz zdjęcie poniżej.

Dwie kostki

Zaawansowane aspekty grafów — Podsumowanie

Jak widzisz świat matematyki i zaawansowane aspekty grafów to ogromna przestrzeń możliwości. Jako programista musisz znać grafy, by być lepszym specjalistą. Nawet jeśli nigdy ich nie użyjesz, to ich znajomość poszerzy Twoje horyzonty i pozwoli patrzeć na przykład na struktury danych i algorytmy z nieco innej perspektywy.

Ja do czasów studiów magisterskich o grafach wiedziałem niewiele. Dziś jestem w tym świecie zauroczony i polecam zgłębiać temat jeszcze mocniej, bo, mimo że jest to zagadnienie mocno matematyczne, to potrafi dać wiele frajdy. 

Moim zadaniem w tym wpisie i poprzednim, gdzie wprowadzałem Ciebie w podstawy grafów, było zaszczepienie tematu. Celowo nie skupiałem się mocno na matematycznej stronie i napisałem te artykuły najbardziej przyjaznym językiem, na jaki było mnie w tym momencie stać!

Daj znać, co myślisz o teorii grafów.

Newsletter

Nie przegap i dołącz już dziś do 815 osób będących w tym Newsletter! Otrzymuj co niedzielę o godzinie 20 listę kilku ciekawych tematów, które miałem okazję obserwować w mijającym tygodniu.

Tematy będą głównie techniczne, ale czasami pojawi się coś, co może wprowadzi Cię w stan zadumy i zmusi do dyskusji w szerszym gronie. Zero spamu!

Autor

Programista .NET i Python. Autor książki "Programistą być".

Napisz komentarz

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.

Programistą być to przewodnik po programistycznym świecie, który każdy zainteresowany programowaniem powinien przeczytać!

X