UWAGA konkurs!
Mistrz Programowania
Serwis algorytm.edu.pl zaprasza na kompleksowe zajęcia przygotowujące do matury z informatyki (nowa podstawa programowa) oraz dla uczniów szkół podstawowych do zajęć przygotowujących do Olimpiady Informatycznej Juniorów.
więcej informacji pod adresem szkola-fraktal.pl
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 połączenie między dwoma wierzchołkami A i B jest dwukierunkowe (A <--> B). Oznacza to, że możemy przejść z wierzchołka A do B i z B do A.
Przykład grafu nieskierowanego
W tym rodzaju grafów nadany jest kierunek poruszania się między dwoma wierzchołkami:
Zauważmy, że przejście z wierzchołka 1 do 3 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.
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.
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.