Programowanie i algorytmy

Pojęcie grafu

Algorytmy grafowe

Definicja

Grafem nazywamy strukturę złożoną z wierzchołków i krawędzi łączących te wierzchołki. Takie struktury danych mają szerokie zastosowanie w wielu dziedzinach nauki takich jak matematyka, informatyka, kryptografia, topologia, chemia itd. 

Graf nieskierowany

Graf nieskierowany połączenie między dwoma wierzchołkami AB jest dwukierunkowe (A <--> B). Oznacza to, że możemy przejść z wierzchołka A do B i z do A.

Przykład grafu nieskierowanego

graf nieskierowany

Graf skierowany

W tym rodzaju grafów nadany jest kierunek poruszania się między dwoma wierzchołkami:

graf skierowany

Zauważmy, że przejście z wierzchołka 1 do jest możliwe tylko poprzez wierzchołek numer 5, natomiast z 9 możemy tylko wyjść ale nie ma możliwości przejścia do niego.

Graf wagowy

W grafie wagowym (skierowanym lub nieskierowanym) każda krawędź ma nadaną wagę. Wierzchołki można porównać do miast, krawędzie do dróg łączących te miasta, natomiast odległości między tymi miastami to wagi.

graf wagowy

Drzewo

Drzewo to taki graf, w którym istnieje dokładnie jedna droga między dwoma wierzchołkami. W drzewie o n wierzchołkach jest dokładnie n-1 krawędzi.

grafy - drzewo