Opracowanie:
Graf

Graf

Zweryfikowane

Graf (nazywany też grafem ogólnym) jest to para składająca się z niepustego zbioru {displaystyle V}, zawierającego wierzchołki (nazywane również węzłami bądź punktami grafu) oraz rodziny krawędzi (jedno lub dwuelementowych podzbiorów zbioru {displaystyle V}) nazywanej {displaystyle E}, łączących te wierzchołki. Krawędzie mogą łączyć ze sobą dwa różne wierzchołki, lecz mogą również łączyć wierzchołek z samym sobą. Może się również zdarzyć sytuacja, w której te same dwa węzły grafu są połączone wieloma krawędziami.

Wyróżniamy również tzw. graf prosty, czyli graf, w którym nie występują pętle (krawędzie łączące wierzchołek z samym sobą) oraz krawędzie wielokrotne (te same dwa węzły grafu mogą być połączone maksymalnie jedną krawędzią). Jeśli graf nie spełnia warunków bycia grafem prostym, nazywamy go multigrafem.


Przykład grafu prostego.


Przykład multigrafu. Wierzchołki 1 i 3 są połączone podwójną krawędzią, a wierzchołek 2 jest połączony sam ze sobą pętlą.

Możemy również wyodrębnić
graf skierowany (inaczej digraf). Jest to graf, w którym krawędzie są spolaryzowane, to znaczy mają swój zwrot. Jeśli w grafie ogólnym zilustrujemy sobie krawędzie jako odcinki łączące wierzchołki, to krawędzie w grafie skierowanym możemy wyobrazić sobie jako strzałki. Graf skierowany możemy zdefiniować podobnie do grafu ogólnego, zastępując zbiór krawędzi zbiorem krawędzi skierowanych . Cechy grafu ogólnego i grafu skierowanego łączy graf mieszany, który zawiera zarówno krawędzie skierowane, jak i nieskierowane.


Przykład grafu skierowanego.

Graf ważony jest grafem ogólnym lub skierowanym, w którym wierzchołkom (graf ważony wierzchołkowo) lub krawędziom (graf ważony krawędziowo) przypisane zostały wartości liczbowe nazywane wagami.