Wpis opublikowany przez Hakken
1313 wyświetleń
Przedsłowie
Czemu mnie tak długo nie było?
No cóż, najpierw sesja, potem nie miałem weny. Wybaczcie.
Czemu jakieś badziewne grafy jak miała być kryptologia?
Bo uświadomiłem sobie, że żeby zrobić następny wpis kryptologiczny musiałbym powiedzieć więcej o rachunku prawdopodobieństwa i ekstraktorach losowości. Zajęłoby mi to ze dwa miesiące i byłoby to dość nudne, więc postanowiłem zająć się czymś lżejszym. Z bólem serca, bo kryptologia to bardzo ciekawy temat, ale tak jak przed chwilą napisałem - wymaga sporo wiedzy żeby móc się nim poważnie zająć.
Abstrakt
Graf to, mówiąc najprościej, wierzchołki połączone krawędziami.
Używa się ich często do modelowania zjawisk ze świata rzeczywistego, takich jak rozmieszczenie miast, połączenia pociągowe czy relacje między poszczególnymi osobami.
Definicja
Grafem skierowanym 
nazwiemy parę 
, gdzie V jest skończonym zbiorem wierzchołków, a E relacją binarną w V. Zbiór E nazwiemy zbiorem krawędzi, a jego elementy krawędziami.
Grafem nieskierowanym nazwiemy parę , gdzie V jest zbiorem wierzchołków jak wyżej, natomiast E to zbiór nieuporządkowanych par wierzchołków.
Różnica między grafem nieskierowanym a skierowanym jest więc taka, że w grafie nieskierowanym para ze zbioru krawędzi 
, a w grafie skierowanym nie.
Kolokwialnie rzecz ujmując, graf to wierzchołki (punkty) i łączące je krawędzie. W grafie skierowanym krawędzie mają strzałki - działają tylko w jedną stronę. W nieskierowanym krawędzie nie mają strzałek - działają w obie strony.
Przykłady
Poniżej jest wykonany rysunek (1.1) grafu skierowanego dla 
.
Tutaj natomiast jest przykład (1.2) grafu nieskierowanego, dla 
.
Oznaczenia
W grafie skierowanym mówimy, że krawędź wychodzi i wchodzi do wierzchołka. Na przykładzie 1.2 powiemy, że krawędź wychodzi z wierzchołka 4 a wchodzi do wierzchołka 1.
Jeżeli dwa wierzchołki są połączone krawędzią, to mówimy, że są one sąsiadami. W grafie nieskierowanym relacja bycia sąsiadem jest oczywiście symetryczna, czyli jeśli v jest sąsiadem u, to u jest sąsiadem v.
W grafie skierowanym jest inaczej, jeśli u jest sąsiadem v, to v nie musi być sąsiadem u. Na przykładzie 1.2 3 jest sąsiadem 6, ale 6 nie jest sąsiadem 3.
Stopniem wierzchołka w grafie nieskierowanym nazywamy liczbę krawędzi w których dany wierzchołek uczestniczy, na przykładzie 1.2 stopień wierzchołka 2 to 2, a wierzchołka 5 to 1.
W grafie nieskierowanym stopień wejściowy wierzchołka to liczba krawędzi wchodzących do tego wierzchołka, a stopień wyjściowy to liczba krawędzi z niego wychodzących.
Stopień wierzchołka w grafie nieskierowanym to suma stopnia wejściowego i wyjściowego.
Dla wierzchołka 2 w przykładzie 1.1 jego stopień wejściowy to 2, wyjściowy 3, a więc stopień w ogóle to 5.
Ścieżka o długości k pomiędzy wierzchołkami v i u to taki zbiór wierzchołków 
, że każdy jest sąsiadem swojego poprzednika oraz 
.
Długość ścieżki to liczba wierzchołków wchodzących w skład ścieżki (inaczej mówiąc jest to moc wyżej zdefiniowanego zbioru).
Jeżeli istnieje ścieżka p z wierzchołka u do v, to powiemy, że v jest osiągalny z v po ścieżce p.
Cyklem nazwiemy taką ścieżkę , że 
oraz długość ścieżki jest niezerowa.
Graf który nie zawiera cykli nazywamy acyklicznym.
Spójność
Graf nieskierowany jest spójny jeżeli każde dwa wierzchołki są przez siebie osiągalne.
Spójne składowe to klasy abstrakcji relacji bycia osiągalnym. Kolokwialnie mówiąc, jeśli istnieje ścieżka z jednego wierzchołka do drugiego, to są one w ten samej spójnej składowej.
Na przykładzie 1.2 mamy trzy spójne składowe: są to zbiory wierzchołków: 
. Oczywiście graf nieskierowany jest spójny wtedy, i tylko wtedy, gdy ma tylko jedną spójną składową (jest nią wtedy cały graf).
Graf skierowany jest silnie spójny jeżeli każde dwa wierzchołki są osiągane jeden z drugiego.
Analogicznie tworzymy silne spójne składowe. Są to klasy abstrakcji relacji bycia wzajemnie osiągalnym.
Na przykładzie 1.1 mamy trzy silnie spójne składowe: 
.
Ważenie grafu
Graf jest ważony, jeżeli zdefiniujemy koszt przejścia po każdej krawędzi.
Dodajmy wagi do grafu z przykładu 1.1
Można w taki sposób prezentować np. koszt biletów pociągowych między miastami. Naturalnie nasuwającym się pytaniem jest "jak najtaniej przejechać z miasta A do miasta B?". Dla tego przykładu rozpatrzmy przejście z wierzchołka 1 do 4.
Możemy przejść z 1 do 2 i z 2 do 4. Taka ścieżka ma sumaryczny koszt równy 7.
Ale można też przejść z 1 do 2, z 2 do 5 i na koniec z 5 do 4. Taka ścieżki mimo, że jest dłuższa, to koszt jest mniejszy (wynosi 6).
Algorytm rozwiązujący ten problem ogólnie to algorytm Dijkstry, ale nie będę teraz o nim pisał, być może poświęcę mu osobny wpis.
Myślę, że na początek starczy. W następnym wpisie zajmę się najprawdopodobniej drzewami (nie, nie zmieniłem zainteresowań z matematyki/informatyki na botanikę 
).
Jak zawsze zachęcam do komentowania, zadawania pytań i dyskutowania!
5 komentarzy
Rekomendowane komentarze