Każdy graf G jest parą (X,E) dwóch rozłącznych zbiorów skończonych X={x₁,x₂,...,x_n} gdzie n>0 oraz E={ e₁,e₂,...,e_m} gdzie m>0, przy czym dla każdego i e_i jest parą elementów ze zbioru X. Zbiór X nazywamy zbiorem wierzchołków, zbiór E nazywamy zbiorem krawędzi.

Stopień grafu - ilość jego wierzchołków.

Graf nieskierowany - nazywamy funkcje przyporządkowującą każdej krawędzi e_i dwa (różne) wierzchołki x_i. Krawędź ma dwa wierzchołki, żaden nie jest wyróżniony i nie istnieje kierunek krawędzi.

Graf skierowany - nazywamy funkcje przyporządkowującą każdej krawędzi e_i uporządkowaną pare (niekoniecznie różne) wierzchołków x_i i x_j. X_i jest początkiem a X_j końcem krawędzi. Graf skierowany może zawierać pętle. Zawiera kierunek.

Graf prosty - nazywamy gdy nie posiada pętli oraz zbioru krawędzi powtórzonych ( takie grafy nazywamy multografami).

Graf pełny - taki graf, w którym każdy wierzchołek jest sąsiadem każdego innego. Graf pełny o n wierzchołkach oznacza się przez K_n. Posiada on n * (n-1) / 2 krawędzi - tyle, ile par różnych wierzchołków.

Stopień wierzchołka - stopniem wierzchołka x, d(x) nazywamy ilość krawędzi incydentnych z x. Pętla występująca w wierzchołku liczona podwójnie!

Droga - ciąg krawędzi e₁,e_2,…,e_n wraz z ciągiem wierzchołków v₁,v₂,…,v_n+1 taki, że dla każdego i krawedź e_i łączy wierzchołki v_i,v_{i + 1}.

Droga prosta - drogę nazwiemy prostą, jeśli jej wszystkie krawędzie są różne.

Droga elementarna - drogę nazwiemy elementarną, jeśli jej wszystkie wierzchołki są różne.

Droga zamknięta - droga zamknięta długości n to droga, w której v_{n + 1} = v₁.

Pętla - jeśli v_i = v_{i + 1} to krawędź e_i jest pętlą.

Cykl - zamknięta droga prosta (długości co najmniej 3), której wszysktie wierzchołki oprócz ostatniego są parami różne.

Składową spójną grafu - nazywamy podgraf, który jest spójny i nie jest podgrafem grafu spójnego.

Spójność grafu - jeśli od każdego wierzchołka grafu istnieje droga do dowolnego innego, to graf jest spójny.

Drzewo - drzewo jest grafem spójnym bez cyklu. Las jest grafem bez cyklu.

Drzewo rozpinające - dla grafu spójnego G=(V,E), każde drzewo G_T=(V,T), gdzie T
E nazywamy drzewem rozpinającym grafu G.

WNIOSKI:

1. Każdy graf spójny złożony ze skończonej ilości wierzchołkow, ma co najmniej jedno drzewo spinające.

2. Jeśli graf nie ma drzewa spinającego to nie jest grafem spójnym (kadrze drzewo jest spójne!)

Graf dwudzielny - to graf, którego zbiór wierzchołków można podzielić na dwa rozłączne zbiory tak, że krawędzie nie łączą wierzchołków tego samego zbioru. Jeśli pomiędzy wszystkimi parami wierzchołków należących do różnych zbiorów v₁,v₂ istnieje krawędź, graf taki nazywamy pełnym grafem dwudzielnym i oznaczamy K_n,m gdzie n i m oznaczają liczności zbiorów wierzchołków.

Graf G jest dwudzielny wówczas:

- jeśli G ma cykl Hamiltona to wówczas na pewno |v₁|=|v₂|

- jeśli G ma drogę Hamiltona to wówczas v₁ i v₂ różnią się najwyżej o 1.

- jeśli graf dwudzielny jest pełny i ma przynajmniej 3 wierzchołki to relacje odwrotne są też prawdziwe.

DROGA EULERA nazywamy drogę prostą, która zawiera wszystkie krawędzie grafu.

CYKLEM EULERA nazywamy zamkniętą drogę Eulera.

WNIOSEK: Graf spójny, zawierający nie więcej niż 2 wierzchołki stopnia nieparzystego ma drogę Eulera.

ALGORYTM WYZNACZANIA DROGI EULERA:

1. Wybierz dowolny wierzchołek v o nieparzystym stopniu, o ile taki istnieje. W przeciwnym przypadku wybierz dowolny wierzchołek v.

2. Dopóki są w grafie krawędzie incydentne wykonuj:

• Jeśli jest dokładnie jedna krawędź z v - {v,w} to podstaw v w, wstaw tę krawędź jako kolejny wyraz ciągu i usuń ją z grafu.

• Jeśli istnieje więcej niż jedna krawędź incydentna krawędź z v, to wybierz dowolną krawędź {v,w}, która nie jest mostem, podstaw v w, wstaw tę krawędź jako kolejny wyraz ciągu i usuń ją z grafu.

3. Jeśli ciąg zawiera wszystkie krawędzie grafu to została wyznaczona droga Eulera, jeśli nie to graf nie był spójny.

DROGA HAMILTONA - w grafie G nazywamy taką drogę elementarną, która zawiera wszystkie wierzchołki grafu.

CYKL HAMILTONA - w grafie G nazywamy taki cykl elementarny, który zawiera wszystkie wierzchołki grafu. Długość cyklu Hamiltona jest równa V.

WNIOSEK: Jeśli w grafie Hamiltona będziemy dodawać krawędź to dalej będzie on grafem Hamiltona.

ALGORYTM WYZNACZANIA DROGI HAMILTONA:

1. Warunek konieczny, ale niedostateczny !!!

• Liczba krawędzi musi być co najmniej równa ilości wierzchołków.

2. Warunki dostateczne:

• Jeśli graf G nie ma pętli i krawędzi wielokrotnych oraz ma przynajmniej 3 wierzchołki a ponadto dla każdego wierzchołka p,
  , gdzie m jest ilością wierzchołków to graf jest Hamiltonowski.

• Jeśli nie ma pętli i krawędzi wielokrotnych oraz ma przynajmniej ½ (n-1)(n-2)+2 krawędzi to jest Hamiltonowski.

• Jeśli nie ma pętli i krawędzi wielokrotnych oraz ma przynajmniej 3 wierzchołki, jeśli dla każdej pary wierzchołków vw nie połączonych krawędzią spełniony jest warunek
  to graf jest Hamiltonowski.

ALGORYTM WYZNACZANIA DRZEWA SPINAJĄCEGO LUB SPÓJNEJ SKŁADOWEJ

ZAŁOŻENIA:

• Graf T jest grafem częściowym, grafu G

• Graf T jest drzewem, czyli jest spójny i acykliczny.

WNIOSEK:

Jeśli V(T)=V(G) to graf jest spójny.

WYKONAJ:

1. Wybierz dowolny wierzchołek z grafu G np.
   

• v - jako korzeń naszego drzewa,

• V - zbiór wierzchołków,

• E - zbiór krawędzi.

• 
  

2. Dopóki istnieje krawędź w grafie G łącząca wierzchołki ze zbioru V z wierzchołkami z poza zbioru V tzn. np. [u,w], gdzie
   to wykonaj:

• Stwórz nowy
  w postaci o powiększony zbiór
  

• Jeśli na końcu
  to otrzymamy drzewo spinające, a graf G jest spójny.

• Jeśli na końcu
  to otrzymamy spójną składową.

ALGORYTM KRUSKALA

ZAŁOŻENIA:

Znaleźć tyle wierzchołków, by suma wag była najmniejsza.

Istnieje funkcja
(na ogół działa na [0,10]), jeśli
, to
jest wagą krawędzi.

Jeśli mamy graf H, który jest grafem częściowym grafu G to mamy
nazywamy sumą wag krawędzi należących do grafu H.

ALGORYTM:

• Trzeba posortować krawędzie e₁,e₂,e₃,…,e_n, gdzie
  , żeby waga krawędzi była
  

• Dla j=1 aż do n wykonaj:

• Jeśli graf
  jest acykliczny to dołącz
  do zbioru E

ALGORYTM PRIM-DIJKSTRA

ZAŁOŻENIA:

Graf G jest spójny.

ALGORYTM:

Wybieramy dowolny wierzchołek grafu G,
,

Dopóki
wykonaj:

• Wybierz
  ze zbioru
  , krawędź
  taką że
  i to jest krawędź o najmniejszej wadze, następnie dołącz do
  oraz krawędź
  do zbioru
  

ALGORYTM FORDA

ZAŁOŻENIA:

- waga danego łuku

Dla każdego p_i przyporządkowujemy dowolną u_i, gdzie u₀=0 i u_i<0, jeśli są łukiem i należą do zbioru E to wówczas sprawdzamy
,
:

• Jeśli
  to zmieniamy wartość
  powtarzamy długo aż nie będzie możliwości,

• 
  (
  są to długości najkrótszych dróg od
  

• Żeby znaleźć najkrótszą drogę cofamy się od
  po znakach równości do
  

---