Grafami mo偶emy nazwa膰 zbi贸r kropek i kresek 馃檪 Niezbyt to naukowe wi臋c poprawie si臋. Grafy to zbi贸r wierzcho艂k贸w i kraw臋dzi. Kraw臋dzie 艂膮cz膮 wierzcho艂ki. Zbi贸r wierzcho艂k贸w oznaczamy zazwyczaj Vg – od Vertx a zbi贸r kraw臋dzi oznaczamy Eg – Edges.
Grafy mo偶emy podzieli膰 na proste i skierowane. Te drugie maj膮 po prostu kierunki opisuj膮ce kraw臋dzie. Czyli jest to para uporz膮dkowana dw贸ch wierzcho艂k贸w i 艂膮cz膮cego je kraw臋dzi (ma pocz膮tek i koniec). Jest jeszcze multigraf czyli dana para wierzcho艂ek i kraw臋d藕 mo偶e wyst臋powa膰 wielokrotnie, powtarza膰 si臋 np. tzw p臋tla lub kraw臋d藕 wielokrotna.
Jak sprawdzi膰 czy grafy s膮 jednakowe ?
Izomorficzno艣膰 graf贸w sprawdzamy czy ilo艣膰 kraw臋dzi wychodz膮cych z danego wierzcho艂ka jest identyczna. Analogicznie w grafach skierowana tylko tu liczy si臋 jeszcze pocz膮tek i koniec czyli to czy wierzcho艂ek jest nada tym samym pocz膮tkiem (lub ko艅cem) wierzcho艂ka. Czasami mo偶emy spotka膰 si臋 z okre艣leniem funkcji bijekcji, kt贸ra jest wzajemnie jednoznaczna. Sprawdzenie czy grafy s膮 izomorficzne polega膰 b臋dzie w g艂贸wnej mierze na nadaniu numer贸w wierzcho艂k贸w i sprawdzenie czy z wierzcho艂k贸w w drugim grafie o identycznym numerze wychodzi tyle samo kraw臋dzi.
Kilka poj臋膰 z tzw. s艂owniczka graf贸w.
Wierzcho艂ek V jest incydentny z kraw臋dzi膮 e gdy e = { v,w } (czyli kraw臋d藕 wychodzi lub wchodzi do wierzcho艂ka V)
Wierzcho艂ki s膮 s膮siednie je艣li s膮 incydentne z t膮 sam膮 kraw臋dzi膮 (analogicznie z kraw臋dziami).
Stopie艅 wierzcho艂ka – liczba kraw臋dzi incydentnych. (p臋tle liczymy podw贸jne).
Izomorfizm zachowuje stopnie wierzcho艂k贸w.
Graf nazywamy pe艂nym dwudzielnym je艣li istniej膮 dwa zbiory roz艂膮czne wierzcho艂k贸w V1 i V2 takie 偶e ka偶dy wierzcho艂ek ze zbioru V1 艂膮czy si臋 z ka偶dym wierzcho艂kiem ze zbioru V2 ale nie 艂膮cz膮 si臋 wzajemnie wewn膮trz zbior贸w V1 i V2. Troch臋 zakr臋cone ale rysunek wszystko wyja艣nia.
Podgraf F grafu H to taki graf, kt贸rego kraw臋dzie i wierzcho艂ki stanowi膮 podzbi贸r wierzcho艂k贸w i kraw臋dzi grafu H.
Mo偶emy wykona膰 kilka podstawowych operacji na grafach jak:
- suma graf贸w
- dodanie wierzcho艂ka
- usuni臋cie wierzcho艂ka – przy czym usuwaj膮c wierzcho艂ek musimy r贸wnie偶 usun膮膰 kraw臋dzie incydentne z nim
- dodanie kraw臋dzi
- dope艂nienie grafu – zostawiamy wierzcho艂ki a wszystkie kraw臋dzie zast臋pujemy kraw臋dziami, kt贸rych wcze艣niej w grafie nie by艂o
- 艣ci膮gni臋cie kraw臋dzi – chyba najbardziej skomplikowana operacja z w/w. 艢ci膮gni臋cie kraw臋dzi polega na po艂膮czeniu wierzcho艂k贸w incydentnych ze 艣ci膮gan膮 kraw臋dzi膮 a sama kraw臋d藕 jest usuwana. Poni偶ej operacja 艣ci膮gni臋cia kraw臋dzi e.
Na koniec pozostaje jeszcze podstawowe pytanie – gdzie si臋 nam to przyda ??
Grafy maj膮 swoje zastosowanie wsz臋dzie tam gdzie s膮 jakie艣 po艂膮czenia 馃檪 Czyli b臋d膮 to:
- sieci spo艂eczno艣ciowe
- mapy, transport itp.
- cz膮stki, kryszta艂y
- sieci komputerowe
- diagramy, drzewa decyzyjne
- importy w kodzie (kompilator sprawdza graf import贸w 偶eby nie by艂o importu do importu)
- przetwarzanie tekstu
- SQL i bazy danych