Teoria grafów

Teoria grafów to temat dzisiejszego artykułu. Na samym początku warto zadać sobie pytanie, czym tak właściwie jest graf. Definicja grafu jest bardzo prosta. Grafem możemy nazwać pewien zbiór wierzchołków. Wierzchołki te są ze sobą połączone, tworząc tym samym krawędzie. Wierzchołki w grafie stanowią końce krawędzi. Każda krawędź więc ma dwa końce.

Przykładowy wygląd grafu jest przedstawiony na ilustracji stworzonej przeze mnie. Jak widzimy na załączonym obrazku, są przedstawione krawędzie, które stanowią proste kreski, czasem jednak dopuszczalne są grafy jak na rysunku numer 2. Poza tym, rzadko kiedy można spotkać się z grafami, w których krawędzie są skierowane. Mówimy wtedy, że są to grafy skierowane. Je przedstawia ilustracja numer 3.

Innymi rodzajami grafów są grafy, przy krawędziach których są napisane, przyporządkowane wartości –> waga. Inaczej mówiąc są to grafy ważone. Wartości napisane przy krawędziach mogą wyrażać na przykład odległość pomiędzy poszczególnymi wierzchołkami grafu. Przedstawia je rysunek nr 4.

Ponadto, wyróżniamy jeszcze rodzaj grafu, w którym wierzchołki są „podpisane”. Te podpisy nazywamy etykietami, a sam rodzaj grafów nazywamy grafami etykietowanymi. Przedstawia je rysunek nr 5.