O uogólnieniach kolorowań grafów
Wykład Wojciecha Przybyszewskiego, Maraton wykładowy z Deltą [15 grudnia 2022 r.]
Posłuchaj wykładu w formie podcastu:
Zapraszamy na kolejny wykład w ramach grudniowego wydarzenia „Maraton wykładowy z Deltą”, podczas którego można usłyszeć o informatyce, matematyce, fizyce oraz astronomii.
Co to jest graf?
Graf to matematyczny obiekt, który składa się z wierzchołków (punktów) połączonych krawędziami (liniami). Grafy są powszechnie wykorzystywane w informatyce, naukach społecznych, logistyce, fizyce i wielu innych dziedzinach, ponieważ pozwalają one na reprezentację różnych zależności między elementami. W grafie wyróżnia się wiele pojęć, takich jak stopień wierzchołka (liczba krawędzi, które z nim są połączone), ścieżka (sekwencja wierzchołków połączonych krawędziami) i cykl (ścieżka, która zaczyna i kończy się w tym samym wierzchołku). Grafy mogą być skierowane lub nieskierowane, zależnie od tego, czy krawędzie mają określony kierunek.
Stopień wierzchołka
Stopień wierzchołka w grafie to liczba krawędzi, które z nim są incydentne (czyli kończą się i zaczynają w danym wierzchołku). Stopień wierzchołka jest jednym z podstawowych pojęć w teorii grafów i może być stosowany do wielu zadań, takich jak znajdowanie cykli w grafie, wyznaczanie minimalnego drzewa rozpinającego, czy wykrywanie mostów i punktów artykulacji w grafie.
W grafach nieskierowanych stopień wierzchołka jest równy liczbie krawędzi wychodzących z danego wierzchołka, natomiast w grafach skierowanych stopień wierzchołka to suma liczby krawędzi wychodzących z wierzchołka (zwana indegree) oraz liczby krawędzi wchodzących do wierzchołka (zwana outdegree).
Stopień wierzchołka jest ważnym pojęciem w wielu algorytmach grafowych i może być stosowany do analizy struktury grafów oraz do rozwiązywania problemów w różnych dziedzinach, takich jak informatyka, matematyka, fizyka czy biologia.
Graf planarny
Graf planarny to graf, który może być narysowany na płaszczyźnie w taki sposób, że krawędzie się nie przecinają (poza wierzchołkami, w których się stykają). Innymi słowy, graf planarny to taki graf, który może być przedstawiony na płaskiej powierzchni bez skrzyżowań krawędzi.
Przykładami grafów planarnych są grafy prostych figur geometrycznych, takie jak kwadraty, trójkąty czy koła oraz ich kombinacje. Ważnym pojęciem związanym z grafami planarnymi jest twierdzenie Eulera, które mówi, że dla każdego spójnego grafu planarnego liczba wierzchołków, krawędzi i ścian (obszarów ograniczonych przez krawędzie grafu) spełnia zależność: V – E + F = 2, gdzie V oznacza liczbę wierzchołków, E – liczbę krawędzi, a F – liczbę ścian.
Grafy planarne są stosowane w wielu dziedzinach, takich jak projektowanie obwodów elektrycznych, teoria sieci, kartografia czy informatyka. W analizie grafów planarnych wykorzystywane są specjalne algorytmy, takie jak algorytm wstawiania wierzchołka czy algorytm usuwania wierzchołka, które umożliwiają modyfikowanie grafów planarnych zachowując ich planarność.
Wojciech Przybyszewski – doktorant w Instytucie Informatyki, na Wydziale Matematyki, Informatyki i Mechaniki UW
