Grafy, a raczej próby wykazania się w czymś, w czym nie warto się wykazywać

Znowu notka po dwóch tygodniach i dodatkowo spowodowana tymi samymi czynnikami. Dzisiaj jednak będzie bez przepraszających wstępnych, gdyż prawdopodobnie po pierwsze są już one nudne dla Was, a po drugie – patrz punkt piewszy (nie, to nie pętla).

Chciałem jednak nieco rozpisać się o strukturach, które musieliśmy przebadać na przedmiot Algorytmy i Struktury Danych, a mianowicie o grafach. W tym miejscu chciałem zadeklarować, iż nie chcę umieszczać tutaj wszystkich definicji i tym podobnych rzeczy – na to przyjdzie czas, jak zdecyduję się na ukazanie ocenionych już wtedy (mam nadzieję) raportów algorytmicznych, które będzie można spacyfikować i krytykować. Wypada jednak jakąś cząstkę teorii zawrzeć ku temu, o czym chcę napisać. Polecam zatem ten oto link, w którym dobrze są rozpisane reprezentacje grafu w komputerze i podstawowe informacje. Jedynymi zmianami oznaczeń jakiej dokonałem w swoich rozważaniach są:

• Ilość wierzchołków to nie V tylko n
• Ilość krawędzi to nie E tylko m
• Lista sąsiedztwa nazywa się listą incydencji
• Będą używane następujące skróty – macierz sąsiedztwa to MS, lista krawędzi to LK, macierz incydencji to MI, a lista incydencji to LI. Ułatwi to późniejszą prezentację wyników

Zagadnienie, na którym chciałbym się skupić, można by było zacząć od zdania, które napisał NOWIESZ (pozdrawiam i przepraszam jeśli naruszyłem jakiekolwiek prawa autorskie):

Liczbę wierzchołków będę oznaczać przez V (i numerować 1..V), a liczbę krawędzi przez E. Oczywiście V²>=E. Grafy, w których E=V² nazywamy pełnymi, E jest trochę mniejsze od V² - gęstymi, a dużo mniejsze - rzadkimi.

Można jednak wprowadzić dodatkową wielkość, a mianowicie współczynnik nasycenia. Jest to wartość z przedziału [0, 1], która określa jaki procent wszystkich możliwych krawędzi znajduje się w grafie o n wierzchołkach. Im graf bardziej gęsty, tym współczynnik ten jest większy, a zatem istnieje więcej połączeń pomiędzy wierzchołkami. Można zatem ten podział wykazać tak:

• Grafy pełne – współczynnik nasycenia jest równy 1.
• Grafy gęste – współczynnik nasycenia mieści się w przedziale [0,5; 1).
• Grafy rzadkie – współczynnik nasycenia jest mniejszy niż 0,5.

Generalnie, interesuje nas złożoność pamięciowa (w skrócie ZP) oraz dwa rodzaje operacji – sprawdzenie, czy pomiędzy danymi dwoma wierzchołkami istnieje krawędź (innymi słowy, czy są one do siebie incydentne) (w skrócie S,CPDDWIK(IS,CSODSI)) oraz wyszukanie wszystkich incydentnych wierzchołków do danego (w skrócie WWIWDD). Te trzy zagadnienia oraz ich teoretyczną, asymptotyczną szybkość działania dla poszczególnych reprezentacji można przedstawić następująco:

	ZP	S,CPDDWIK(IS,CSODSI)	WWIWDD
MS	O(n2)	O(1)	O(n)
LK	O(m)	O(m)	O(m)
MI	O(nm)	O(m)	O(m)
LI	O(n+m)	O(n)	O(1)

Warto by było jednak w jakiś sposób porównać te wartości. Dlatego, dla przedstawionych wcześniej rodzajów grafów (pełny, gęsty i rzadki), po uwzględnieniu faktu, iż maksymalnie m może wynosić n², a współczynnik nasycenia od 0 do 1, można zastosować następujące przeliczniki:

Rodzaj grafu	Minimalna wartość m	Maksymalna wartość m
Pełny	n2	n2
Gęsty	0,5n2	0,(9)n2
Rzadki	0	0,(5)n2

Zatem, dla poszczególnych typów grafów i reprezentacji, można wysnuć następujące wnioski co do złożoności obliczeniowej.

Graf pełny	Złożoność pamięciowa	Sprawdzenie, czy dwa wierzchołki są incydentne	Wyszukanie wszystkich wierzchołków incydentnych do danego
Macierz sąsiedztwa	O(n2)	O(1)	O(n)
Lista krawędzi	O(n2)	O(n2)	O(n2)
Macierz incydencji	O(n3)	O(n2)	O(n2)
Lista incydencji	O(n2+n)	O(n)	O(1)

Graf gęsty	Złożoność pamięciowa	Sprawdzenie, czy dwa wierzchołki są incydentne	Wyszukanie wszystkich wierzchołków incydentnych do danego
Macierz sąsiedztwa	O(n2)	O(1)	O(n)
Lista krawędzi	[O(0,5n2), O(n2))	[O(0,5n2), O(n2))	[O(0,5n2), O(n2))
Macierz incydencji	[O(0,5n3), O(n3))	[O(0,5n2), O(n2))	[O(0,5n2), O(n2))
Lista incydencji	[O(0,5n2+n), O(n2+n))	O(n)	O(1)

Graf rzadki	Złożoność pamięciowa	Sprawdzenie, czy dwa wierzchołki są incydentne	Wyszukanie wszystkich wierzchołków incydentnych do danego
Macierz sąsiedztwa	O(n2)	O(1)	O(n)
Lista krawędzi	[O(1), O(0,5n2))	[O(1), O(0,5n2))	[O(1), O(0,5n2))
Macierz incydencji	[O(n), O(0,5n3))	[O(1), O(0,5n2))	[O(1), O(0,5n2))
Lista incydencji	[O(n), O(0,5n2+n))	O(n)	O(1)

Cóż, nie wygląda to zbyt interesująco – zwłaszcza dla tych, którzy jeszcze nie muszą (lub już nie muszą) się tym zajmować. Można jednak wysnuć z tych tabelek parę wniosków, które mogą się przydać w przyszłości:

• Dla grafów gęstych i pełnych świetnym wyborem jest macierz sąsiedztwa.
• Im mniej krawędzi ma graf (lub jeśli chcemy posortować go topologicznie), tym lepszą reprezentacją będzie lista incydencji.
• Jedynymi zaletą listy krawędzi okazuje się miejscami mała zajętość pamięci oraz dosyć prosta budowa. Jest jednak zbyt wolna w porównaniu do dwóch powyższych struktur.
• Macierz incydencji jest wolna, zajmuje dużo pamięci i generalnie nie jest to produkt polecany przez Instytut Matki i Dziecka.

Zdaję sobie sprawę, że te wynurzenia nie są jakoś specjalne wyrafinowane. Lubię jednak dużo dziwnych wyprowadzać, a nie lubię się tym nie chwalić. A poza tym – być może ktoś skorzysta lub nawet mnie poprawi, co będzie dla mnie bardzo miłą oznaką.

A co do obrazka przy tytule notki – nie, to nie dotyczy grafów. To po prostu “easter egg” z Wielkiego Mistrza umieszczony przez jednego z twórców. Przy okazji – przepraszam całą ekipę za to, iż nie mam ostatnio czasu na tworzenie gry ze względu na studia.

A skoro mowa o easter eggach – Wesołych Świąt!

Pozdrawiam i dziękuję – SceNtriC.