Co to jest Graf, do czego służy i jakie są jego zastosowania?

Człowiek ma naturalną tendencję do opisywania i porządkowania otaczającego go świata. W tym celu ludzkość wymyśliła wiele pojęć służących do opisu świata materialnego – rzeczywistego między innymi za pomocą różnych parametrów. Zgodnie z tą ideą korzystamy z takich terminów jak wysokość, szerokość, długość, waga, kolor i tak dalej. Za ich pomocą można opisać większość otaczających nas obiektów, jednak ten opis nie odzwierciedla jak poszczególne elementy są ze sobą powiązane oraz czy są od siebie w jakiś sposób zależne, czy też względem siebie uporządkowane. O ile przedstawiając poszczególne przedmioty można za pomocą mowy lub pisma opisać ich relacje pomiędzy sobą to na dłuższą metę jest to czasochłonne. Dlatego w drodze do standaryzacji takich opisów i stworzenia możliwości do sprawnego opisywania zależności pomiędzy elementami powstało pojęcie grafu.

W ramach tego artykułu postaram się Tobie przybliżyć w przystępny sposób, bez zbędnej teorii czym jest graf i jakie ma on zastosowania w dzisiejszym świecie. Zacznijmy w takim razie od początku, czyli od zdefiniowania grafu jako pojęcia.

Definicja Grafu

Graf jest pojęciem matematycznym, a dział zajmujący się ich opisywaniem nazywany jest Teorią Grafów. Graf jest strukturą matematyczną, za pomocą której przedstawia się relacje występujące pomiędzy obiektami.

W takiej reprezentacji każdy graf składa się z dwóch zbiorów. Pierwszy z nich to zbiór wierzchołków, gdzie każdy z nich jest pojedynczym obiektem. Drugi z nich to zbiór krawędzi, a każda z nich opisuje dokładnie jedną relację pomiędzy dwoma obiektami.

Jeszcze bardziej upraszczając jeśli w czasie młodości wykonywałeś zadania w stylu ‚połącz (ponumerowane) kropki’ to tworzyłeś graficzną reprezentację pewnego grafu – tworzonego rysunku. Dobrze jest pamiętać, że każda krawędź, podobnie jak wierzchołek też może mieć przypisaną wartość (na przykład odległość między dwoma punktami).

Przykład reprezentacji graficznej grafu
Przykład reprezentacji graficznej grafu

Kontynuując przykład z łączeniem kropek w grafach istotny jest sposób połączenia pomiędzy poszczególnymi wierzchołkami. Dokładniej w niektórych przypadkach sama kolejność / kierunek łączenia poszczególnych wierzchołków ma znaczenie ponieważ można w ten sposób oddać sposób relacji między obiektami. Dlatego wyróżnia się podstawowe dwa rodzaje grafów: skierowane oraz nieskierowane.

Czym jest graf skierowany?

Graf skierowany to taki, w którym określony jest kierunek przejścia pomiędzy wierzchołkami. Takie grafy stosuje się w przypadkach, gdy kolejność zaistnienia danych obiektów czy też procesów opisywanych ma znaczenie. Innym przypadkiem stosowania grafów skierowanych są sytuacje gdy opisywane są procesy / zmiany nieodwracalne lub możliwość przejścia w jedną stronę jest możliwa a w drugą już nie. W reprezentacji graficznej oznacza się to za pomocą strzałki, której grot jest skierowany do docelowego wierzchołka.

Przykładem zastosowani grafu skierowanego może być opis przepisu na przyrządzenie jajecznicy:

  1. Przygotuj patelnię
  2. Włącz palnik
  3. Dodaj masło
  4. Dodaj rozbite jajka
  5. Mieszaj
  6. Wyłącz palnik
Prezentacja graficzna grafu skierowanego na przykładzie przepisu na jajecznicę
Przykład graficznej prezentacji grafu skierowanego

Dla obranej kolejności wykonywania poszczególnych etapów przepis może być zapisany jako graf skierowany, ze względu na konieczność zachowania kolejności procesów. Warto zwrócić uwagę, że równie dobrze taki przepis mógłby być uproszczonym algorytmem. W pewnym uogólnieniu można przyjąć, że każdy algorytm można opisać za pomocą grafu, co jest częstym przykładem zastosowań grafów w celu ulepszenia, dopracowania, usprawnienia algorytmów lub przedstawienia ich graficznie w sposób uproszczony.

Czym jest graf nieskierowany?

Graf nieskierowany jest przeciwieństwem poprzedniego rodzaju grafu. Stosuje się go, gdy kierunek relacji między obiektami (wierzchołkami) nie jest istotny lub z racji swojej natury jest dwukierunkowy. W taki sposób można opisać na przykład domy przynależące do wskazanej ulicy – tworząc graf miasta w którym poszczególne wierzchołki to zarówno ulice jak i budynki. W takiej strukturze połączenie danej ulicy z budynkiem jest dwukierunkowe i można naturalnie pomiędzy nimi się przemieszczać (co ciekawe rozszerzenie tej struktury o pomieszczenia w budynkach z racji pomieszczeń przechodnich nakazywałoby zastosowanie grafu skierowanego).

Jakie znaczenie ma graf w matematyce – Teoria Grafów

Działem matematyki zajmującym się grafami jest Teoria Grafów. Za jej początek uznaje się rozwiązanie problemu mostów królewieckich przez Leonharda Eulera w 1736 roku natomiast samego Eulera za pracę którą przedstawił jako ojca Teorii Grafów.

Czym był problem mostów królewieckich? Królewiec jest malowniczym miastem położonym nad rzeką Pregoła a w jej rozwidleniach leżą dwie wyspy. Żeby można było bezproblemowo przemieszczać się pomiędzy wyspami i stronami rzeki postawiono nad rzeką 7 mostów. Problem, który próbował rozwikłać Euler był następujący: Czy da się przejść kolejno przez wszystkie mosty w taki sposób aby każdy z nich przekroczyć tylko raz? Euler w ramach swoich rozważań udowodnił, że nie jest to możliwe a także opisał uogólniony problem wskazując jakie warunki muszą być spełnione, aby dało się w ten sposób przejść cały powstały graf.

Rozmieszczenie mostów królewieckich na mapie - wizualizacja pierwszego problemu Teorii Grafów
Rozmieszczenie mostów królewieckich – pierwszy problem teorii grafów

Ludzkość spotyka jednak dużo większe problemy niż to przez które mosty należy przejść. Dlatego w późniejszym czasie dostrzeżono ‚potencjał ekonomiczny’ w rozważaniach Eulera. Na przykład problem komiwojażera, którego celem jest znalezienie najkrótszej, najtańszej lub najszybszej drogi pomiędzy określonymi punktami, przyjmując że zaczyna się ona i kończy w tym samym punkcie. Przełożenie tego problemu na przykład na ilość paliwa, jakie zużyje kurier podczas rozwożenia paczek jest wystarczającym powodem aby dogłębniej analizować tego typu problemy.

Oprócz wspomnianych zastosowań sama teoria grafów stała się przyczynkiem do rozwoju jeszcze innej dziedziny matematyki – topologii. Czym zajmuje się topologia, w skrócie badaniem własności obiektów, które nie ulegną żadnej zmianie nawet gdy się je w sposób znaczący zdeformuje. Nie zgłębiając się w szczegóły można żartobliwie określić, że topologia zajmuje się tym jak nie rozróżniać kubka od obwarzanka.

Graf w informatyce i jego podstawowe zastosowania

Grafy oprócz wcześniej wymienionych zastosowań optymalizacyjnych oraz zastosowań w takich dziedzinach jak elektronika czy też chemia, często są wykorzystywane w informatyce. Warto zwrócić uwagę albo przynajmniej mieć świadomość ich stosowania w sytuacjach z życia codziennego zwłaszcza w świecie technologii internetowych.

Zastosowanie Grafów w drzewie DOM

Struktura pojedynczej strony internetowej jest mniej lub bardziej uporządkowana. Elementy najwyższego rzędu (rodzice) zawierają elementy podrzędne (dzieci), natomiast one posiadają swoje elementy i tak dalej. W celu uporządkowania takich struktur powstał model DOM (Document Object Model). W uproszczeniu działa on jak rosyjskie matrioszki, w większej matrioszce jest mniejsza a w niej następna, z drobną różnicą, że każda matrioszka może mieć nieskończenie wiele podlegających jej matrioszek. Dzięki przedstawieniu tej struktury za pomocą grafu na przykład nieskierowanego, można w łatwy sposób odnosić się do konkretnych elementów a także decydować, który z nich ma być wczytany jako pierwszy a które później. Z pomocą przeglądarki ze struktury DOM danej strony internetowej można zaprezentować gotowy widok strony, którą chciał zobaczyć użytkownik.

Przykład DOM (Document Object Model) jako zastosowania grafu na przykładzie strony wp.pl
Przykład zastosowania DOM jako grafu na stronie wp.pl

Zastosowanie Grafów w strukturze strony internetowej

Zazwyczaj strona internetowa ma więcej niż jedną podstronę. Większość z nich jest połączona pomiędzy sobą aby można było płynnie przechodzić z jednej na drugą (na przykład za pomocą menu). Każde takie połączenie jest realizowane za pomocą linku, który ze swojej natury działa jednokierunkowo, dlatego każdą strukturę strony można opisać za pomocą grafu skierowanego.

Dlatego przedstawianie połączeń między podstronami w danej domenie jest realizowane w ten sposób między innymi w celu przejścia pomiędzy wszystkimi zasobami na stronie. Realizuje się to w celu odnalezienia ewentualnych błędów na wszystkich podstronach, albo zebrania wszystkich tytułów stron występujących na stronach.

Przykład zastosowania grafu do przedstawienia struktury strony internetowej
Przykład zastosowania grafu do prezentacji struktury strony internetowej

W bardziej globalnej skali można w ten sposób zbierać dane dotyczące wszystkich stron internetowych jakie istnieją, o ile będzie się miało wystarczająco dużo zasobów i mocy obliczeniowej.

Inne przypadki wykorzystania i stosowania grafów

Grafy same w sobie stosowane są także w innych dziedzinach i płaszczyznach życia. Popularny ostatnio Map Minding, do prezentowania map myśli jest też procesem tworzenia i rysowania grafu. Projektowanie wszelkiego rodzaju procesów zachodzących w firmach, opracowywanie nowych cykli obiegu dokumentów i rozbijanie ich na pomniejsze elementy aby znajdować punkty krytyczne, które można poprawić to też swojego rodzaju zastosowania teorii grafów i grafów samych w sobie.

W kontekście samego SEO, pozycjonowania stron internetowych grafy mają niebagatelne znaczenie, ponieważ cały internet teoretycznie da się opisać za pomocą jednego wielkiego grafu albo sieci wielu podgrafów. Mając taką strukturę można względem ustalonych parametrów segregować poszczególne strony, czyli wyniki wyszukiwania, co jest celem w samym sobie wszystkich wyszukiwarek internetowych. Dlatego też zainteresowanie grafami przez świat pozycjonowania jest dość duże, ze względu, że algorytmy Google je wykorzystujące segregują wyniki na konkretne zapytania. Tak samo opieka nad odpowiednio dużym serwisem nie byłaby możliwa jeśli nie dało by się w relatywnie krótkim czasie sprawdzić wszystkich zasobów strony internetowej.

Jeśli pojęcie grafów było Tobie wcześniej obce, mam nadzieję, że chociaż trochę odpowiedziałem na pytanie czym są i do czego są stosowane. Masz też teraz świadomość jak szerokie zastosowania one posiadają i być może kolejne znajdziesz w rzeczach, które sam realizujesz.

1 Odpowiedź

  1. Dominika pisze:

    Dobre pomysły pewnie wykorzystam coś u siebie.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *