fbpx

Dzisiejszym tematem jest wprowadzenie do grafów, czyli konstrukcji matematycznych, które są szalenie istotne z perspektywy programisty i całego programowania. Często jednak poznajemy je przez przypadek lub podczas studiów technicznych, zapominając zupełnie o podstawach programowania i tego, że grafy stosujemy w informatyce niemal na każdym kroku — i to zupełnie nieraz nieświadomie.

Odpowiem w tym wpisie na następujące pytania:

  • Czym jest graf?
  • Jakie mamy rodzaje grafów?
  • Właściwości i definicje wokół grafów
  • Gdzie w informatyce wykorzystujemy grafy?

Temat mimo matematycznych podstaw jest przyjemny, dlatego 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…


Wprowadzenie do grafów — czym jest graf?

Grafy to ważne narzędzie matematyczne, które swoją przydatność „sprzedała” informatyce. Od układów elektronicznych, po sieci komputerowe, struktury danych i na bazach danych kończąc.

Wyobraź sobie graf jako pewną skończoną ilość wierzchołków i łączących je linii, zwanych w matematycznym żargonie krawędziami. Najszybciej skojarzysz sobie graf z przedstawioną chwilę wcześniej siecią komputerową. Komputery, routery czy switche będą wierzchołkami, kable pomiędzy tymi urządzeniami będą krawędziami. 

Podobnie rzecz ma się z układami elektronicznymi. Kondensatory, rezystory czy tranzystory to nasze wierzchołki, a ścieżki lub przewody między nimi to krawędzie.

Poniżej przykład jednego z nieskończonej ilości grafów. Składa się on z pięciu wierzchołków i czterech krawędzi.

Przykładowy graf składający się z pięciu wierzchołków i czterech krawędzi.

Z definicji możemy powiedzieć, że powyższy graf jest grafem prostym oraz nieskierowanym. Prostym, ponieważ nie zawiera pętli oraz wielokrotnych krawędzi. Pętla, czyli krawędź wychodzi z tego samego wierzchołka, do którego wchodzi. Krawędź wielokrotna natomiast to połączenie dwóch wierzchołków więcej niż jedną krawędzią.

Dodatkowo jest to graf nieskierowany, ponieważ nie ma określonych kierunków krawędzi. Możemy sobie te krawędzie wyobrazić, jako drogę dwukierunkową, gdzie możemy z jednego do drugiego wierzchołka podróżować w dwie strony. Gdyby chociaż jedna z krawędzi prowadziła w określony sposób z jednego punktu do drugiego, to już wtedy mamy do czynienia z grafem skierowanym. Zobacz, jak wygląda graf skierowany na rysunku poniżej.

Graf skierowany

Od razu dla rozjaśnienia zobacz poniżej, jak wygląda graf skierowany, który nie jest grafem prostym. Zawiera podwójną krawędź oraz jedną pętlę. 

Grafy puste, cykliczne, liniowe i kołowe

Podstawowe grafy, czyli proste, skierowane i nieskierowane mamy za sobą. Czas na nieco bardziej szczegółowe. Wyobraź sobie, że graf to komputery i sieć komputerowa. Komputer to wierzchołek, kable internetowe to krawędzie łączące komputery.

Komputer niepodłączony do sieci jeszcze może nam się przydać. Możemy zagrać w grę, zaprojektować grafikę czy programować. Z samych kabli łączących komputery raczej aż takiego pożytku nie mamy. Grafy bez takich połączeń (bez krawędzi) nazwiemy grafem pustym. Zobacz rysunek poniżej.

Kolejną wariacją grafów są grafy cykliczne. Sama nazwa już mówi wiele. Jest to taki graf, który jest niejako zamknięty. Z jednego punktu wychodzimy i do niego wracamy jedną, określoną ściśle drogą. Zobacz rysunek poniżej.

Trzecim w tym akapicie grafem jest graf liniowy. Tu też wiele mówi nam nazwa. Wystarczy, że z grafu cyklicznego zabierzemy jedną krawędź i tak powstanie nam linia złożona z wierzchołków i krawędzi. Zobacz rysunek poniżej.

Kolejnym grafem jest graf kołowy. Powstaje on z połączenia grafu pustego złożonego z jednego wierzchołka z grafem cyklicznym. Wystarczy w środek dać graf pusty i połączyć ten wierzchołek z każdym wierzchołkiem grafu cyklicznego i gotowe. Zobacz na rysunku poniżej.

Grafy pełne, dwudzielne oraz drzewa

Czas na ostatnią grupę grafów, które z perspektywy programisty będą nas szczególnie interesować. Grafem pełnym nazwiemy taki graf, w którym każda para wierzchołków jest połączona krawędzią. Czyli każdy wierzchołek łączy się ze wszystkimi innymi wierzchołkami. Zobacz rysunek grafu pełnego poniżej.

Graf dwudzielny to graf złożony z dwóch zbiorów wierzchołków, niech to będzie zbiór A i zbiór B. Zbiory te są rozłączne, czyli nie zawierają wspólnych wierzchołków. Teraz połączmy ze sobą dwa zbiory za pomocą krawędzi i tak otrzymany graf nazwiemy grafem dwudzielnym. Znając też definicję grafu pełnego, możemy też stworzyć graf dwudzielny pełny, gdzie wszystkie wierzchołki zbioru A będą połączone ze wszystkimi wierzchołkami zbioru B. Zobacz rysunek poniżej przedstawiający graf dwudzielny.

Ostatnią grupą grafów, którą dziś przedstawię, a zarazem najbardziej istotną z perspektywy programisty są grafy, które są drzewami. W dużym skrócie drzewa to takie grafy, które są spójne, czyli z każdego wierzchołka możemy przejść do dowolnego innego po krawędziach. Grafy w tej właśnie postaci są wykorzystywane w bazach danych czy jako struktury danych, ale o tym w bardziej technicznym wpisie w przyszłości.

Przykład drzewa zobacz na obrazku poniżej.

Wprowadzenie do grafów — definicje

Dobrze, poznaliśmy zbiór kilku podstawowych grafów, wiemy też, czym jest wierzchołek oraz krawędź. Ale to dopiero początek, grafy mają całą masę właściwości i definicji, które teraz chcę Ci przedstawić.

Trzecim ważnym pojęciem obok wierzchołka i krawędzi jest pojęcie stopnia wierzchołka. Stopień wierzchołka to liczba krawędzi, których końcem jest ten sam wierzchołek. Zobacz na ostatni obrazek powyżej przedstawiający drzewo. Czerwony wierzchołek jest stopnia drugiego, ponieważ ma dwie krawędzie dołączone do niego. Dwa kolejne wierzchołki są stopnia trzeciego i ostatnie cztery, na samym dole są stopnia pierwszego.

Trasa, cykl i droga

Bardzo ważnymi pojęciami są trasa, droga oraz cykl. Trasą nazwiemy linię, po której przedostajemy się z jednego wierzchołka do drugiego. Droga natomiast to trasa, w której nie występuję dwa razy ten sam wierzchołek. Cykl natomiast to taka trasa, która zaczyna i kończy się w tym samym wierzchołku. Aby lepiej to zrozumieć, zobacz obrazek poniżej. Odpowiednio kolorami oznaczona jest:

  • trasa (1 -> 2 -> 6 -> 1 -> 7)
  • droga ( 5 -> 6 -> 7 -> 8)
  • cykl (3 -> 4 -> 5 -> 3)

Planarność grafu, izomorfizm i spójność grafów

Zacznę od planarności. Możemy powiedzieć, że graf jest planarny wtedy, gdy możemy narysować graf na powierzchni bez przecięć. Planarność grafów odgrywa dużą rolę w wielu problemach. Wyobraź sobie sytuacje, gdzie trzeba pokolorować mapę odpowiednimi kolorami, tak by Państwa sąsiednie były pokolorowane innymi kolorami. Jeśli połączymy Państwa, które będą wierzchołkami krawędziami w taki sposób, by nie powstały przecięcia, to możemy powiedzieć, że da się pokolorować taką mapę czterema kolorami. Jest to wstęp do twierdzenia o czterech barwach, ale jest to zaawansowany aspekt grafów, którego nie będę bardziej rozszerzał w tym wpisie.

Izomorfizm odnosi się do dwóch osobnych grafów. Wyobraź sobie graf G1 oraz G2. Są one izomorficzne wtedy, gdy wierzchołki i krawędzie grafu G1 są identycznie połączone ze sobą jak w grafie G2. Czasem dwa inaczej wyglądające na rysunku grafy są identyczne, jeśli chodzi o połączenie. Zobacz grafikę poniżej.

Ostatnią z trójki definicji jest spójność grafu. Spójność zachodzi wtedy, gdy z dowolnego jednego wierzchołka możemy przejść do dowolnego innego. O spójności była już mowa w przypadku drzew. Każde drzewo jest grafem spójnym. W przeciwnym razie graf jest niespójny. Spójność grafu można zbadać algorytmem DFS, o którym pisałem już na tym blogu.

Macierze

Jedno z ciekawszych zagadnień, jeśli chodzi o grafy i bardzo potrzebna w zrozumieniu podczas pisania algorytmów opartych na grafach.

Reprezentacja macierzowa z perspektywy komputera to wygodna i czytelna forma reprezentacji grafu. Dla człowieka naturalnie bardziej czytelny będzie rysunek, gdzie wierzchołki połączone są krawędziami. Zwłaszcza przy dużych grafach, przechowanie informacji o nim w pamięci komputera będzie bardziej wydajne za pomocą macierzy.

Macierz sąsiedztwa

Macierz sąsiedztwa to macierz N x N, gdzie wierzchołki są oznaczone od 1 do N. Wyraz o indeksach A oraz B jest równy liczbie krawędzi łączących wierzchołek A z wierzchołkiem B. Najlepiej zobrazuje Ci to rysunek poniżej.

Pierwszy wiersz w macierzy dotyczy wierzchołka 1 – łączy się on z 2 oraz 4, dlatego mamy zapis 0101. Zera są tam, gdzie nie ma połączenia, czyli nie łączy się z samym sobą oraz z trzecim wierzchołkiem.

Drugi wiersz w macierzy dotyczy wierzchołka 2 – łączy się on z 1, 3 oraz 4, dlatego mamy zapis 1011. Zero jest tam, gdzie nie ma połączenia, czyli nie łączy się z samym sobą.

Trzeci wiersz w macierzy dotyczy wierzchołka 3 – łączy się on z 2 oraz 4, dlatego mamy zapis 0101. Zera są tam, gdzie nie ma połączenia, czyli nie łączy się z samym sobą oraz z pierwszym wierzchołkiem.

Czwarty wiersz w macierzy dotyczy wierzchołka 4 – łączy się on z 1, 2 oraz 3, dlatego mamy zapis 1110. Zero jest tam, gdzie nie ma połączenia, czyli nie łączy się z samym sobą.

Macierz incydencji

Dobrze, skoro w macierzy sąsiedztwa patrzymy na wierzchołki, tak analogicznie w macierzy incydencji interesują nas krawędzie. Jeśli krawędzie oznaczymy zbiorem liczb od 1 do M, to macierz będzie mieć wymiar N x M. Wyraz o indeksach A i B jest równy 1, jeśli wierzchołek A jest incydentny (połączony) z krawędzią B. Równy natomiast 0 w przeciwnym przypadku. I tym razem zerknijmy na rysunek poniżej.

Pierwszy wiersz w macierzy dotyczy wierzchołka 1 – jest incydentny z krawędzią 1 oraz 4, dlatego mamy zapis 10010. Zera są tam, gdzie krawędź nie łączy się z wierzchołkiem.

Drugi wiersz w macierzy dotyczy wierzchołka 2 – jest incydentny z krawędzią 1, 2 oraz 5, dlatego mamy zapis 11001. Zera są tam, gdzie krawędź nie łączy się z wierzchołkiem.

Trzeci wiersz w macierzy dotyczy wierzchołka 3 – jest incydentny z krawędzią 2 oraz 3, dlatego mamy zapis 01100. Zera są tam, gdzie krawędź nie łączy się z wierzchołkiem.

Czwarty wiersz w macierzy dotyczy wierzchołka 4 – jest incydentny z krawędzią 3, 4 oraz 5, dlatego mamy zapis 00111. Zera są tam, gdzie krawędź nie łączy się z wierzchołkiem.

Wprowadzenie do grafów — gdzie w informatyce wykorzystujemy grafy?

Bazy danych i struktury

Myśląc o grafach jako strukturach danych, miej na uwadze to, że struktury takie są najbardziej skomplikowanymi strukturami w programowaniu. Jest to jednak jedna z najlepszych opcji do przechowywania relacji między danymi. Wykorzystują to między innymi grafowe bazy danych, takie jak Neo4j, OrientDB czy Amazon Neptune. O grafowych bazach danych napiszę osobny artykuł, ponieważ jest to potężny temat.

 

Algorytmy

Pierwszą myślą, jaką mam, jeśli chodzi o użycie grafów to BFS oraz DFS. Są to algorytmy przeszukiwania grafu w głąb i wszerz. Więcej o nich pisałem w artykule 10 oraz artykule 55. Kolejnym znanym algorytmem jest algorytm Fleury’ego, który pozwala na odszukanie cyklu w grafie eulerowskim. Cykl Eulera jest ścieżką, która przechodzi dokładnie jeden raz przez każdą krawędź grafu i kończy się w wierzchołku, od dana ścieżka się zaczęła. Kolejnym wartym uwagi algorytmem jest algorytm Dijkstry. Służy on do znajdowania najkrótszej ścieżki w grafie.

Jeszcze jednym ważnym zwłaszcza w sieciach komputerowych algorytmie jest Algorytm Bellmana-Forda, który polega na znalezieniu najkrótszej drogi w grafie skierowanym. Na algorytmie Bellmana-Forda bazuje protokół Routing Information Protocol (RIP).

Ale chyba najbardziej popularnym i najczęściej używanym przez nas algorymem jest PageRank. Wymyślony przez twórców Google. To na nim opiera się działanie wyszukiwarki internetowej Google. Cały Internet jest więc ogromnym grafem stron połączonych ze sobą. Algorytm nadaje indeksowanym stronom internetowym określonej wartości liczbowej, oznaczającej ich jakość. Ten algorytm również zasługuje na osobny wpis na tym blogu!

Zastosowania 

Algorytmów tego rodzaju używa się w logistyce, by wyznaczać optymalne trasy dla kurierów, w nawigacjach samochodowych, gdzie istotne jest pokazanie najkrótszej drogi z punktu A do B. Każde skrzyżowanie to wierzchołek grafu, drogi to krawędzie.

Oczywistym użyciem algorytmów grafowych jest sieć komputerowa, chociażby przy trasowaniu. Protokoły takie jak wspomniany RIP czy Open Shortest Path First (OSPF) opierają się na wspomnianych algorytmach.

Całą szeroką gamą zastosowań grafów są sieci społecznościowe. Powiązania między ludźmi, zainteresowaniami, umiejętnościami czy nastrojem są właśnie stworzone w grafie. Wszystkie wymienione elementy traktowane są jako wierzchołki grafu, a powiązania to krawędzie.

W systemie operacyjnym natkniemy się na wykres alokacji zasobów, w którym każdy proces i zasoby są traktowane jako wierzchołki. Krawędzie są pobierane z zasobów do przydzielonego procesu lub z procesu żądającego do żądanego zasobu. Jeśli doprowadzi to do powstania cyklu, nastąpi impas.

Jak widać, niemal każda dziedzina informatyki i programowania ma w sobie coś z grafów. Nie możesz przejść obok tak ważnego tematu obojętnie!

Wprowadzenie do grafów — Podsumowanie

Artykuł mający kilkanaście grafik i około 2000 słów porusza jedynie ułamek całego tematu, jakim są grafy w informatyce i matematyce. Ludzie robią doktoraty z tych tematów, więc jest się czego uczyć. Chciałem nakreślić podstawy podstaw oraz pokazać, jak ważna jest nawet mała znajomość teorii grafów. 

Grafy otaczają nas na każdym kroku. Uważam, że każdy programista powinien się z nimi zapoznać. Jeśli chcesz, to polecę Ci świetną książkę, z której czerpałem wiedzę podczas nauki grafów na studiach magisterskich. Książka Wprowadzenie do teorii grafów jest idealna, jeśli artykuł rozbudził Twój apetyt na więcej zagadnień.

Na grafy zwróciłbym jeszcze uwagę od strony algorytmów, ponieważ pojawiają się one na rozmowach o pracę w dużych korporacjach. Jeśli chcesz pracować nad nowinkami w firmach takich jak Google, Amazon, Microsoft czy Apple, to temat grafów jest tam jednym z najważniejszych zagadnień. Nikogo nie będzie interesować, czy umiesz konkretny język programowania lub framework. Ludzi w takich firmach interesuje Twoja znajomość algorytmiki i grafów właśnie!

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