Rozwiązuje grafie ważonym. Idea algorytmu opiera się na metodzie relaksacji (dokładniej następuje relaksacja V-1 razy każdej z krawędzi). W odróznieniu od algorytmu Dijkstry, poprawność algorytmu Ballmana-Forda nie opiera się na założeniu, że wagi w grafie są nieujemne.

, którego nazwa pochodzi od nazwiska odkrywcy - holenderskiego informatyka Edsgera Dijkstry, służy do rozwiązywania problemu najkrótszej ścieżki w grafie skierowanym, o nieujemnych wagach krawędzi. W przełożeniu na praktykę może służyć do znalezienia najlepszej trasy między dwiema zadanymi miejscowościami. Kryterium może być czas pokonania, długość, koszt itp. Zapis w pseudokodzie Dla grafu G, funkcji wagowej w i wierzchołka s, otrzymamy tablicę d[u] odległości każdego wierzchołka grafu od wierzchołka s.

Poszukiwanie ścieżki Eulera w grafie Przypuśćmy, że dany jest graf G i że G jest grafem eulerowskim. Chcemy teraz znaleźć wierzchołka v.

Służy do znajdowania najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w grafie ważonym.

Naiwny algorytm rozwiązywania problemu komiwojażera polegający na odwiedzaniu począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Bardzo prosty do zaprogramowania, szybki, ale daje słabe wyniki. Zobacz też: cykl Hamiltona, problem komiwojażera.

To taki grafie, w którym każda krawędź grafu występuje dokładnie jeden raz. W grafie nieskierowanym cykl taki występuje gdy graf jest spójny i stopień wszystkich wierzchołków jest parzysty. W grafie skierowanym natomiast wtedy, gdy graf jest silnie spójny i dla każdego wierzołka liczba krawędzi wchodzących jest równa liczbie krawędzi wychodzących. Grafy takie nazywamy grafami eulerowskimi.

To taki grafie, w którym każdy problemu komiwojażera. Grafy zawierające cykl Hamiltona nazywamy hamiltonowskimi. Zobacz też: cykl Eulera, problem komiwojażera, algorytm najbliższego sąsiada.

Dopełnieniem grafu (ang. complement of graph) G nazywamy graf \overline, zawierający te same wierzchołko co graf G, natomiast pomiędzy wierzchołkami grafu \overline istnieje krawędź wtedy i tylko wtedy gdy pomiędzy tymi wierzchołkami nie istnieje krawędź w grafie G. Własności Dopełnieniem n-wierzchołkowego grafu regularnego stopnia k jest graf regularny stopnia n-k. Dopełnieniem grafu pełnego jest graf nie zawierający krawędzi.

W teorii grafów drzewo to spójny graf acykliczny.

Drzewem rozpinającym grafu G nazywamy drzewo, które zawiera wszystkie wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem zbioru krawędzi grafu. Konstrukcja drzewa rozpinającego polega na usuwaniu z grafu tych krawędzi które należą do cykli. Najmniejszą liczbą krawędzi jaką trzeba usunąć z grafu, aby graf stał się acykliczny (stał się drzewem) nazywa się rzędem acykliczności grafu lub liczbą cyklometryczną.

Graf zwykły G definiuje dwójka: G = (V; E), gdzie V jest dowolnym, niepustym zbiorem, natomiast E jest podzbiorem zbioru wszystkich 2-elementowych zbiorów, których elementy należą do V, czyli: # V ≠ ∅ # E ⊆ P2(V) Graficzną reprezentacją wierzchołków grafu są punkty, natomiast łuki między nimi obrazują krawędzie. Oprócz grafów zwykłych, istnieją między innymi grafy skierowane.

Graf hamiltonowski to graf zawierający cykl Hamiltona. Zobacz też: cykl Hamiltona, cykl Eulera, graf Eulerowski. .

To graf o ciekawych własnościach często używany w teorii grafów. Nazwa pochodzi od nazwiska matematyka J. Petersena któremu przypisuje się pierwszą publikację grafu w 1898 roku. Własności Graf petersena. . . jest silnie regularny stopnia 3. jest trójspójny i trójspójny krawędziowo. ma ścieżkę Hamiltona ale nie ma cyklu Hamiltona. jest grafem trójdzielnym. jest dopełnieniem grafu krawędziowego grafu K5.

To graf nie zawierający cykli. W przypadku grafów nieskierowanych spójne grafy acykliczne są równoważne drzewom, a niespójne lasom. Zobacz też: cykl (teoria grafów), graf nieskierowany, graf skierowany.

(ang. perfect graph) to graf którego kliki. Linki zewnętrzne: [http://mathworld. wolfram. com/PerfectGraph. html Grafy doskonałe - MathWorld].