Graf (matematyka)

Z Wikipedii

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf podgraf cykl klika stopień wierzchołka dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Breadth-first search Depth-first search Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego

edytuj ten szablon

Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.

Wierzchołki grafu zwykle są numerowane i mogą stanowić reprezentację jakichś obiektów rzeczywistych, natomiast krawędzie mogą obrazować połączenia między takimi obiektami. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie jest grafem skierowanym. Krawędź może posiadać także wagę, to znaczy liczbę, która określa na przykład odległość między wierzchołkami (jeśli na przykład graf jest reprezentacją połączeń między miastami). W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (jeśli graf będzie reprezentował trud poruszania się po jakimś terenie, to droga pod górkę będzie miała większą wagę niż z górki).

Spis treści 1 Definicje 1.1 Graf 1.2 Graf skierowany 1.3 Graf mieszany 1.4 Warianty definicji 2 Pojęcia 2.1 Podstawowe 2.2 Zaawansowane 3 Przykład 4 Izomorfizm i homeomorfizm grafów 5 Grafy geometryczne 6 Oznaczenia formalne 7 Klasy grafów 8 Operacje na grafach 8.1 Operacje binarne 8.1.1 Suma grafów 8.1.2 Przecięcie grafów 8.1.3 Zespolenie grafów 8.2 Operacje unarne 9 Sposoby reprezentacji grafów 9.1 Macierz sąsiedztwa 9.2 Lista sąsiedztwa 9.3 Macierz incydencji 10 Zastosowania 11 Bibliografia 12 Zobacz też 13 Linki zewnętrzne

[edytuj] Definicje

Różni autorzy stosują bardzo odmienne sposoby definiowania i oznaczania elementów grafu.

[edytuj] Graf

Graf lub graf nieskierowany to uporządkowana para G := (V,E) gdzie:

• V jest zbiorem wierzchołków,
• E jest rodziną dwuelementowych podzbiorów zbioru wierzchołków V, zwanych krawędziami: .

Wierzchołki należące do krawędzi nazywane są jej końcami. Zazwyczaj V (i co za tym idzie E) są określane jako zbiory skończone. Jednak powyższa definicja tego nie wymaga i w praktyce rozważa się też czasami grafy o nieskończonej ilości wierzchołków i/lub krawędzi.

[edytuj] Graf skierowany

Graf skierowany lub inaczej digraf to uporządkowana para G := (V,A) gdzie:

• V jest zbiorem wierzchołków,
• A jest zbiorem uporządkowanych par różnych wierzchołków ze zbioru V, zwanych krawędziami skierowanymi, lub łukami: .

Przyjmuje się, że krawędź e:=(x,y) jest skierowana z x do y, czyli wychodzi z x, a wchodzi do y.

[edytuj] Graf mieszany

Graf mieszany to uporządkowana trójka G:=(V,E,A) gdzie zbiory V,E,A są zdefiniowane jak wyżej, czyli może zawierać jednocześnie krawędzie skierowane i nieskierowane.

[edytuj] Warianty definicji

W wielu zastosowaniach tak zdefiniowane grafy nie są wystarczające i wprowadza się pewne modyfikacje.

Na przykład aby wprowadzić pętlę czyli krawędź, której oba końce są tym samym wierzchołkiem, w definicji grafu nieskierowanego należy dopuścić zbiory jednoelementowe {v} albo użyć dwuelementowego multizbioru {v,v}. W grafie skierowanym pętla jest naturalnie reprezentowana przez parę (v,v).

Czasami potrzebna jest możliwość połączenia dwóch wierzchołków przy pomocy więcej niż jednej krawędzi (w przypadku grafu skierowanego chodzi o łuki o takim samym zwrocie). Graf, który na to pozwala, nazywany jest multigrafem. Uzyskuje się go np. przez zdefiniowanie E, lub A jako multizbioru.

Przez zdefiniowanie funcji z V, E, lub A w pewnien zbiór X, można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatowych informacji. Etykiety liczbowe są często nazywane wagami. Dla grafów z wagami zbiór tworzący graf jest rozszerzony o funkcję taką, że dla każdej krawędzi , jest wagą danej krawędzi

Przykłady odmiennych sposobów definiowania grafu:

• Graf może być też określony jako niepusty zbiór wierzchołków i dana na nim relacja binarna taka, że dla dowolnych wierzchołków i zachodzi wtedy i tylko wtedy, gdy istnieje krawędź łącząca i . Dla grafów nieskierowanych relacja ta jest symetryczna (zob. też "macierz sąsiedztwa" poniżej).

• Graf nieskierowany można też definiować jako trójkę , gdzie

• jest zbiorem wierzchołków
• zbiorem krawędzi
• funkcją ze zbioru krawędzi w rodzinę jedno- i dwuelementowych podzbiorów zbioru wierzchołków - . Wówczas jeżeli jest krawędzią grafu to:

• kończy się ona wierzchołkami , gdy
• jest ona pętlą, gdy

• Graf skierowany określa się też jako trójkę , gdzie zbiory i są zdefiniowane analogicznie do grafów nieskierowanych a jest funkcją ze zbioru krawędzi w zbiór uporządkowanych par (kwadrat kartezjański, czyli iloczyn kartezjański zbioru ze sobą) wierzchołków - . Wówczas jeżeli jest krawędzią grafu to istnieją takie wierzchołki , że . W takim przypadku krawędź biegnie z do .

[edytuj] Pojęcia

[edytuj] Podstawowe

• Droga

Wyznaczona przez krawędzie trasa polegająca na podróżowaniu od wierzchołka do wierzchołka po łączących je krawędziach. Jeżeli przez e_i oznaczy się i-tą krawędź grafu, to droga może być jednoznacznie zapisana jako

• Droga prosta

Droga nie zawierająca dwóch tych samych krawędzi

• Długość drogi/ścieżki

To liczba krawędzi/wierzchołków tworzących daną drogę/ścieżkę

• Cykl

Zamknięta droga prosta , taka, że krawędź e_z kończy się w początkowym wierzchołku drogi

• Droga acykliczna

Droga nie zawierająca cyklu

• Gęstość grafu

Stosunek liczby krawędzi do największej możliwej liczby krawędzi: :.

Używa się również określeń: graf gęsty, jeżeli ma on dużo krawędzi w stosunku do liczby wierzchołków i podobnie graf rzadki, jeżeli ma on mało krawędzi w stosunku do liczby wierzchołków. Przy czym znaczenie słów mało i dużo może zależeć od kontekstu.

• Krawędzie sąsiednie

Krawędzie kończące się w jednym wierzchołku. W przypadku grafów skierowanych zazwyczaj wymagana jest "zgodność kierunków" krawędzi, tj. dwie krawędzie są sąsiednie, jeżeli odpowiednio kończą się i zaczynają w tym samym wierzchołku.

• Pętla

Krawędź zaczynająca i kończąca się w tym samym wierzchołku

• Podgraf grafu H

Graf G uzyskany poprzez usunięcie części wierzchołków z H, wraz z kończącymi się w nich krawędziami

• Nadgraf grafu H

Taki graf, że H jest jego podgrafem.

• klika

Podzbiór wierzchołków danego grafu, z których każdy jest sąsiadem każdego innego (czyli podgraf pełny).

• Sąsiad:

Dwa wierzchołki są sąsiadami, jeśli istnieje krawędź pomiędzy nimi.

• Stopień wierzchołka v

Liczba kończących się w nim krawędzi. Oznaczenie: deg(v). W przypadku grafów skierowanych mówi się o stopniach wejściowym i wyjściowym - degIn(v), degOut(v)

• Graf r-regularny:

Graf, w którym każdy wierzchołek grafu jest stopnia r.

• Ścieżka

Intuicyjnie jest bardzo podobna do drogi, z tym, że jest wyznaczona przez wierzchołki, tj. można ją opisać poprzez ciąg wierzchołków

• Ścieżka prosta

Ścieżka wyznaczona tak, by żaden wierzchołek na trasie nie powtarzał się

• Ścieżka zamknięta

Ścieżka , czyli kończąca się w początkowym wierzchołku

• Usunięcie wierzchołka

Przez usunięcie wierzchołka rozumie się wymazanie go, oraz wszystkich kończących się w nim krawędzi z danego grafu

• Acentryczność wierzchołka grafu

To maksymalna odległości wierzchołka do innych wierzchołków grafu, lub inaczej długość najdłuższej ścieżki prostej zaczynającej się w danym wierzchołku.

• Waga krawędzi

Często od grafu reprezentującego np. sieć połączeń komunikacyjnych oczekuje się nie tylko informacji o istniejącym połączeniu (krawędzi lub ścieżki), ale też o np. długości połączenia. Wprowadza się wtedy wagi, wartość przypisaną każdej krawędzi. Graf taki można wykorzystać np. do wyznaczenie optymalnej, w sensie przejechanych kilometrów trasy, lub, ogólniej rozwiązanie problemu komiwojażera, wyznaczenia optymalnego rozłożenia kabli w sieci, koordynowania wysyłania plików metodą peer to peer itp.

• wierzchołek izolowany

Wierzchołek o stopniu 0, czyli nie będący końcem żadnej krawędzi.

[edytuj] Zaawansowane

• Kolorowanie grafu

To nadanie każdemu wierzchołkowi koloru, tak by żadne sąsiadujące ze sobą wierzchołki nie były pokolorowane tym samym kolorem.

• Krawędź/wierzchołek krytyczny

Krawędź/wierzchołek, po usunięciu której/którego ze zbioru pokrywającego zmniejsza się indeks pokrycia krawędziowego/wierzchołkowego.

• Liczba chromatyczna

Najmniejsza liczba kolorów potrzebna do prawidłowego pokolorowania grafu.

• Minimalny pokrywający podzbiór krawędzi/wierzchołków

To możliwie najmniejszy podzbiór krawędzi/wierzchołków grafu, taki, że pokrywają one wszystkie wierzchołki/krawędzie danego grafu.

Liczność minimalnego zbioru pokrywającego krawędzi/wierzchołków nazywa się indeksem pokrycia wierzchołkowego/krawędziowego. Wszystkie podzbiory o tej liczności i własności nazywa się pokryciem minimalnym.

• Spójna składowa grafu G

Spójna składowa grafu to możliwie największy spójny podgraf grafu G. Graf spójny ma jedną spójną składową.

• Ściana

Obszar zamknięty wyznaczony przez krawędzie grafu (tzw. krawędzie tworzące ścianę). Z pojęciem ściany ściśle powiązane jest twierdzenie Eulera.

Uwaga! Za ścianę uważa się też nieskończony obszar znajdujący się "na zewnątrz" grafu (a więc każdy graf ma co najmniej jedną ścianę)!

• Ściany sąsiadujące

Ściany są sąsiadujące, jeżeli mają co najmniej jedną wspólną krawędź tworzącą.

• Wierzchołek rozspajający

Wierzchołek, po usunięciu którego zwiększa się liczba spójnych składowych grafu. Nazywany przegubem tworzy "wąskie gardło" grafu - tj. istnieją w grafie dwa wierzchołki takie, że każda łącząca je droga musi przejść przez wierzchołek rozspajający.

• Most

Krawędziowy "odpowiednik" wierzchołka rozspajającego - krawędź, po usunięciu której wzrasta liczba spójnych składowych grafu.

• Wierzchołek pokrywający krawędź

Wierzchołek v pokrywa krawędź e, jeżeli e kończy się w v. W analogiczny sposób definiuje się krawędź pokrywającą dany wierzchołek - krawędź e kryje wierzchołek v, gdy się w nim kończy.

[edytuj] Przykład

To przykład grafu nieskierowanego G wraz z jego ilustracją:

• 
• ,
  

• Przykładową ścieżką prostą może być a cyklem
• Stopnie wierzchołków

• 
• 
• 
• 
• 
• 

• Krawędź jest sąsiednia z , ale nie jest z
• Graf G ma trzy ściany - zewnętrzną oraz dwie wyznaczone odpowiednio przez ścieżki np. i
• Graf G jest spójny, czyli ma jedną spójną składową. Natomiast podgraf grafu G, składający się z wierzchołków i incydentnych z nimi krawędziami, ma dwie spójne składowe - cykl i wierzchołek izolowany v₆.

[edytuj] Izomorfizm i homeomorfizm grafów

Graficzna reprezentacja grafów (w postaci kropek i łączących je krzywych) jest tylko sposobem przedstawienia relacji zachodzącej między wierzchołkami. Dla każdego grafu istnieje nieskończenie wiele przedstawiających go jednoznacznie wykresów, rysunków. Co więcej, właściwości grafów (takie jak większość podanych w następnej sekcji) są niezależne od sposobu numerowania wierzchołków, kolejności ich rysowania itp. Grafy różniące się tylko sposobem ich przedstawienia, lub indeksami nadanymi wierzchołkom, nazywamy izomorficznymi.

Dwa grafy są homeomorficzne, jeśli z jednego grafu można otrzymać drugi zastępując wybrane krawędzie łańcuchami prostymi lub łańcuchy proste pojedynczymi krawędziami. Mówiąc obrazowo, chodzi o dorysowywanie na krawędziach dowolnej ilości wierzchołków, bądź wymazywanie ich.

[edytuj] Grafy geometryczne

Dla każdego grafu istnieje nieskończenie wiele przedstawiających go rysunków, czasami jednak pożądane są w przypadku grafów własności stricte geometryczne (współrzędne geometryczne wierzchołków, tylko proste krawędzie, "zmieszczenie się" w pewnej przestrzeni itp.). Grafy rozpatrywane jako figury w przestrzeni (w której są one "zanurzone" i która nadaje im cechy charakterystyczne dla danej przestrzeni) nazywa się grafami geometrycznymi.

[edytuj] Oznaczenia formalne

Często dla danego grafu G stosuje się skrócone oznaczenia oparte na alfabecie greckim oraz łacińskim:

• liczba wierzchołków G
• liczba krawędzi G
• najmniejszy stopień wierzchołka w G
• największy stopień wierzchołka w G
• liczba chromatyczna G
• indeks chromatyczny G
• liczba spójnych składowych G

Ta sekcja jest zalążkiem. Jeśli możesz, rozbuduj ją.

[edytuj] Klasy grafów

Grafy można podzielić ze względu na różne własności, zazwyczaj zachowane w obrębie izomorfizmów danego grafu. Najczęściej dotyczą one tylko grafów prostych (nie zawierających pętli i krawędzi wielokrotnych), część z tych własności można rozszerzyć na multigrafy. Najczęściej spotykane klasy grafów to:

• graf prosty (właściwy)

Graf nie zawierający pętli ani krawędzi wielokrotnych. Graf nieprosty nazywany jest mulitigrafem. Z reguły zdanie G jest grafem oznacza w domyśle, że G jest grafem prostym

• graf pełny

Graf, którego każdy wierzchołek jest połączony bezpośrednio krawędzią z każdym innym. Graf pełny o n wierzchołkach oznacza się .

• graf regularny stopnia k

Graf, którego każdy wierzchołek jest stopnia k

• graf kubiczny

Specjalne określenie dla grafów regularnych stopnia 3

• graf acykliczny

Graf nie zawierający żadnej drogi zamkniętej

• graf spójny

Graf, w którym dla każdego wierzchołka istnieje droga do każdego innego wierzchołka

• graf k-spójny

Graf posiadający k spójnych składowych

• drzewo

Spójny graf acykliczny

• las

Graf, którego wszystkie spójne składowe są drzewami

• graf dwudzielny

Graf, którego wierzchołki mogą być podzielone na dwa zbiory, tak by w obrębie jednego zbioru żaden wierzchołek nie był połączony z innym

• graf dwudzielny pełny

Graf dwudzielny taki, że każdy wierzchołek z jednego zbioru jest połączony krawędzią z każdym wierzchołkam ze zbioru drugiego. Pełny graf dwudzielny o wierzchołkach oznacza się

• graf k-dzielny

To naturalne rozszerzenie klasy grafów dwudzielnych - jest to graf, którego zbiór wierzchołków można podzielić na k parami rozłącznych podzbiorów takich, że żadne dwa węzły należące do tego samego zbioru nie są połączone krawędzią

• pełny graf k-dzielny

Jeżeli zbiór wierzchołków dzieli się na k nie połączonych między sobą podzbiorów wierzchołków, to jeżeli dla każdego wierzchołka z -tego przedziału jest połączony z każdym wierzchołkiem z każdego z przedziałów poza j, to jest to pełny graf k-dzielny

• graf eulerowski

Graf posiadający drogę prostą przechodzą przez każdą krawędź.

• graf hamiltonowski

Graf posiadający ścieżkę prostą przechodzą przez każdy wierzchołek.

• graf planarny

Graf, dla którego istnieje graf izomorficzny, który można przedstawić na płaszczyźnie tak, by żadne krawędzie się nie przecinały (oczywiście, nie w sensie "spotkania się" w jednym wierzchołku).

Kazimierz Kuratowski udowodnił, że grafy pełne K₅ i K_3,3 są nieplanarne, oraz że każdy inny graf nieplanarny musi być grafem homeomorficznym z którymś z tych grafów

• graf płaski

To izomorficzne przedstawienie grafu takie, że żadne dwie krawędzie się nie przecinają

• graf platoński

Graf, którego przedstawienie tworzy siatkę wielościanu foremnego

• graf komórkowy

Graf płaski, którego wszystkie ściany są utworzone przez drogi zamknięte tej samej długości

• graf krytyczny

Graf, którego każdy wierzchołek/krawędź jest krytyczny/krytyczna

• graf symetryczny

Graf skierowany taki, że jeżeli istnieje krawędź to istnieje też krawędź . Graf asymetryczny ma własność: jeżeli istnieje krawędź to nie istnieje krawędź

• graf podstawowy grafu skierowanego

To niemal ten sam, ale nieskierowany, bo bez zwrotów na krawędziach

• turniej

To graf pełny, w którym zorientowano krawędzie, lub inaczej, graf skierowany którego graf podstawowy jest grafem pełnym

[edytuj] Operacje na grafach

[edytuj] Operacje binarne

[edytuj] Suma grafów

Definicja:

Jeżeli dane są dwa grafy oraz , to ich sumą jest graf, którego zbiór wierzchołków i krawędzi tworzą wszystkie wierzchołki i krawędzie tych grafów.

[edytuj] Przecięcie grafów

Definicja:

Jest definowane analogicznie do sumy. Jeżeli dane są dwa grafy i , to ich przecięciem jest graf, którego wierzchołki i krawędzie wchodzą w skład obu tych grafów.

[edytuj] Zespolenie grafów

Definicja:

Zespoleniem grafów i nazywamy graf w którym z każdego wierzchołka poprowadzono krawędzie do każdego wierzchołka .

[edytuj] Operacje unarne

• graf krawędziowy grafu prostego G

Graf który dla każdej krawędzi z G ma wierzchołek połączony z wierzchołkami reprezentującymi sąsiadujące ze sobą w G krawędzie.

• dopełnienie grafu

Dopełnieniem grafu nazywamy graf w którym dwa wierzchołki są sąsiednie wtedy i tylko wtedy, gdy nie były sąsiednie w . Inaczej mówiąc w dopełnieniu dwa wierzchołki są połączone krawędzią wtedy, gdy nie były połączone w grafie wyjściowym.

• graf dualny grafu G

Graf, którego wierzchołki odpowiadają ścianom w G. Wierzchołki te są połączone, jeżeli odpowiednie ściany w G są sąsiednie.

Dopisek: rysunek tłumaczy doskonale jak zrobić graf dualny do grafu planarnego, dla grafu nieplanarnego musimy znaleźć dwuwymiarową przestrzeń (osadzoną w wielowymiarze) w której ten graf jest "planarny" - na przykład K5 nie można bez przecięć narysować na kuli, ale da się na torusie i tam możemy znaleźć jego graf dualny

• domknięcie przechodnie grafu G

Graf posiadający te same wierzchołki, co G; dowolne dwa wierzchołki są w nim połączone wtedy i tylko wtedy, gdy w G istnieje między nimi droga.

[edytuj] Sposoby reprezentacji grafów

Każdy graf może być jednoznacznie reprezentowany na wiele sposobów. Dla człowieka w przypadku grafów o "rozsądnej" ilości wierzchołków i krawędzi najwygodniejszy jest rysunek grafu. Pozostałe sposoby reprezentacji wykorzystywane są w komputerach. Każda z tych reprezentacji ma swoje wady i zalety, generalnie ograniczające są dwa warunki - ilość pamięci przeznaczonej na reprezentację i jej możliwości szybkiego odpowiadania na pytania typu czy między wierzchołkami v i u jest krawędź?. W przypadku grafów rzadkich listy sąsiedztwa okazują się wystarczająca szybkie by zrezygnować z pamięciożernych tablic.

Najwygodniejszy dla człowieka jest rysunek grafu, reprezentujący wierzchołki i łączące je krawędzie (rys. obok). Wierzchołki oznaczane są zazwyczaj kropkami lub kołami, niekiedy zawierającymi indeksy bądź inne dodatkowe informacje. Krawędzie reprezentowane są krzywymi bądź prostymi, w przypadku krawędzi ważonych, waga umieszczona jest bezpośrednio nad krawędzią.

Innymi najczęściej stosowanymi metodami reprezentacji grafów są macierze sąsiedztwa, listy sąsiedztwa i macierze incydencji. W przypadku implementacji algorytmów grafowych wybiera się tę metodę, za pomocą której dla danego problemu uzyska się program działający z mniejszą złożonością obliczeniową.

[edytuj] Macierz sąsiedztwa

Najprostszą ze struktur danych umożliwiających przedstawienie skomplikowanego grafu lub jego przechowywanie w pamięci komputera jest macierz sąsiedztwa, zawierająca dane na temat połączeń między wierzchołkami. Macierz jest rozmiaru na , wyraz leżący z i-tego wiersza i j-tej kolumny zawiera wartość będącą liczbą krawędzi łączących i-ty i j-ty wierzchołek. Sposób ten pozwala na reprezentację zarówno grafów prostych, jak i grafów zawierających krawędzie wielokrotne oraz pętle własne. W przypadku grafów prostych wyrazami w macierzy będą wartości boole'owskie - jest krawędź, bądź nie ma krawędzi).

Aby dowiedzieć się, ile krawędzi łączy wierzchołki , wystarczy sprawdzić wartość komórki .

Tak zaimplementowana komputerowa struktura danych gwarantuje, że operacje sprawdzenia, czy dodania oraz usunięcia krawędzi odbywają się w stałym czasie. Do jej wad należy duża ilość potrzebnej pamięci - O(n²), oraz fakt, że czas potrzebny do przejrzenia zbioru krawędzi jest proporcjonalny do kwadratu liczby wierzchołków (złożoność obliczeniowa wynosi O(n²), zamiast do liczby krawędzi.

[edytuj] Lista sąsiedztwa

Drugą popularną reprezentacją grafu są tzw. listy sąsiedztwa - dla każdego wierzchołka zapamiętywana jest lista sąsiadujących z nim wierzchołków, np.:

• 
• 
• 
• 
• 
• 

W implementacji tej metody stosuje się listy jednokierunkowe oraz jednowymiarową tablicę wskaźników o rozmiarze | V(G) | , gdzie i-ty element tablicy jest wskaźnikiem do początku listy przechowującej sąsiadów i-tego wierzchołka.

W odróżnieniu od macierzy sąsiedztwa, lista sąsiedztwa wymaga ilości pamięci proporcjonalnej do ilości krawędzi, także przejrzenie całego zbioru krawędzi jest proporcjonalne do jego rozmiaru. W stosunku do macierzy sąsiedztwa większą złożoność mają jednak operacje elementarne - sprawdzenie, czy wymaga czasu proporcjonalnego do mniejszego ze stopni wierzchołków, a np. usunięcie krawędzi - do większego z nich.

[edytuj] Macierz incydencji

Macierz incydencji M wymiaru na zawiera informacje takie, że M_i,j = 1 tylko, gdy j-ta krawędź kończy się w i-tym wierzchołku (czyli jest z nim incydentna). W przeciwnym wypadku M_i,j = 0

Niech

• 
• 
• 
• 
• 
• 
• 

oznaczają wszyskie krawędzie grafu z przykładu. Macierz incydencji o kolumnach e_i i wierszach v_i może wyglądać tak:

[edytuj] Zastosowania

Kiedy rozwój informatyki pozwolił na reprezentowanie grafów za pomocą komputera, okazało się, że algorytmy na nich oparte znajdują wiele praktycznych zastosowań. Szczególny rodzaj grafów zwanych drzewami okazał się przydatny do reprezentacji hierarchii. Przedstawione na rysunku obok drzewo binarne może opisywać np. mistrzostwa sportowe czy drzewo genealogiczne, a po dodaniu etykiet może służyć np. do tworzenia kodów Huffmana, do opisu rozwoju populacji bakterii w laboratorium albo niedeterministycznego automatu skończonego.

Kiedy komputery stały się powszechne okazało się, że grafy można zastosować w wielu problemach. Jako graf przedstawiono sieć dróg. Skrzyżowania stały się wierzchołkami grafu, a ulice jego krawędziami. Potem w podobny sposób przedstawiono sieci pomieszczeń i korytarzy w budynkach. Taka reprezentacja pozwoliła komputerom na poszukiwanie najlepszej drogi ze swojego obecnego położenia do pożądanego celu. Oprogramowanie oparte na algorytmach analizujących grafy znalazło zastosowanie w przenośnych urządzeniach PDA wyposażonych w GPS, które potrafią wskazać kierowcy trasę w nieznanym mieście.

Innym przykładem wykorzystania grafów stały się gry komputerowe, gdzie system sztucznej inteligencji musiał odszukać najlepszą drogę dla postaci sterowanych przez program, która pozwoli zaatakować ludzkiego przeciwnika. Sztuczna inteligencja mogła rozwiązać to zagadnienie tylko dzięki odpowiedniej reprezentacji mapy wirtualnego otoczenia jako grafu.

Projektanci robotów mobilnych również skorzystali z podobnych algorytmów, aby ich maszyny mogły bez udziału człowieka odnaleźć trasę w trudnym terenie. Przedstawienie sieci komputerowych w postaci grafów pozwoliło na stworzenie oprogramowania usprawniającego routing w Internecie.

Aby zwiększyć wydajność pracy w dużych organizacjach, realizację zlecanych przez klientów zadań przedstawiono w postaci grafów. Pracownikom odpowiadać mogą wierzchołki, a przepływ zadań między nimi opisać można za pomocą krawędzi. Zaprojektowano oprogramowanie pozwalające automatycznie śledzić pracę tak opisanej organizacji, co miało służyć wzrostowi wydajności. Rozwiązania tego typu znalazły zastosowanie w działach wsparcia technicznego klientów dużych korporacji.

[edytuj] Bibliografia

• Kenneth Ross, Charles Wright, Matematyka dyskretna, PWN, 2003
• Robin Wilson, Wprowadzenie do teorii grafów, PWN, 2004
• Witold Lipski, Kombinatoryka dla programistów, WNT, 2004
• Juliusz Kulikowski, Zarys teorii grafów, PWN, 1986
• Marek Kubale, Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT, 2002

[edytuj] Zobacz też

Sławni badacze właściwości grafów:

• Leonard Euler
• Sir William Hamilton
• Kazimierz Kuratowski
• Gustav Kirchhoff
• Francis Guthrie
• Kenneth Appel i Wolfgang Haken

[edytuj] Linki zewnętrzne

• Książka dostępna w internecie dotycząca teorii grafów (en)
• Graph theory tutorial (en)
• Animacje obrazujące niektóre algorytmy teorii grafów (en)
• Kompendium stron dotyczących wizualizacji algorytmów dotyczących grafów (en)
• Galeria grafów reprezentujących rzeczywiste problemy (en)
• Strona Grafos, hiszpańskiej otwartej aplikacji do analizy grafów (en)