Droga (Å›cieżka)	naprzemienny ciÄ…g wierzchoÅ‚ków i krawÄ™dzi (v0, e0, v1, e1, …, vk, ek , … vl) taki, że krawï
Długość drogi:	liczba jej krawędzi
Droga (ścieżka) prosta:	nie powtarzają się krawędzie
Droga (ścieżka) elementarna	nie powtarzają się wierzchołki
Cykl:	droga o długości co najmniej 3, taka, że początkowy i końcowy wierzchołek to ten sam v0 === vl
Cykl prosty:	nie powtarzają się krawędzie, v0 === vl
Cykl elementarny:	nie powtarzają się wierzchołki, oprócz v0 === vl
Obwód grafu	długość najkrótszego cyklu elementarnego w grafie
Graf spójny:	taki, że każde jego dwa wierzchołki połączone są droga (czyli z każdego wierzchołka możemy
Składowa spójna c(G):	maksymalny podgraf grafu, który jest spójny
Graf silnie spójny:	graf skierowany, gdzie dla każdej pary różnych wierzchołków istnieje droga skierowana z pierwsz
Składowa silnie spójna	maksymalny podgraf silnie spójny
Składowa słabo spójna	maksymalny podgraf spójny
Zbiór rozspajający	taki zbiór krawędzi grafu, po usunięciu którego graf ma więcej składowych spójnych
Rozcięcie:	minimalny zbiór rozspajający (żaden jego podzbiór właściwy nie jest rozspajający)
Most:	jednokrawędziowe rozcięcie
Spójność krawędziowa Lambda(G)	liczba krawędzi najmniejszego rozcięcia (czyli liczba krawędzi, które należy usunąć, aby graf
Zbiór rozdzielający	podzbiór wierzchołków, po usunięciu którego (wraz z incydentnymi krawędziami) graf ma więcej
Wierzchołek rozdzielający (punkt artykulacji)	to jednoelementowy zbiór rozdzielający
Spójność wierzchołkowa	liczba elementów najmniejszego zbioru rozdzielającego w grafie spójnym
Blok	maksymalny podgraf grafu nie zawierający wierzchołków rozdzielających dla tego podgrafu
Graf blokowy BL(G	jego wierzchołki odpowiadają blokom G, krawędź łączy 2 wierzchołki BL(G) wtedy i tylko wtedy,
Odległość	między dwoma wierzchołkami v i w to długość najkrótszej ścieżki łączącej je
Metryka	taka odległość, gdzie • d(v,w) >= 0 i d(v,w) == 0 tylko dla v == w (musi być większa od zera
Średnica grafu diam(g):	maksymalna odległość między wierzchołkami w tym grafie
Ekscentryczność wierzchołka ecc(v)	maksymalna odległość od innego wierzchołka
Promień grafu rad(G):	minimalna ekscentryczność wierzchołka w tym grafie
Wierzchołek centralny	wierzchołek o minimalnej ekscentryczności, czyli ecc(v) = rad(G)
Centrum grafu Z(G)	graf indukowany na zbiorze wierzchołków centralnych grafu G
Cykl Eulera	cykl, który nie powtarza krawędzi i zawiera wszystkie krawędzie grafu
Graf Eulera	: graf, który zawiera cykl Eulera, czyli daje się narysować bez odrywania długopisu zaczynając
Ścieżka Eulera	ścieżka, która nie powtarza krawędzi i zawiera wszystkie krawędzie grafu
Graf półeulerowski	taki, który ma ścieżkę Eulera, czyli daje się narysować bez odrywania długopisu, niekonieczni
Cykl Hamiltona	cykl zawierający każdy wierzchołek dokładnie raz
Graf Hamiltona	zawiera cykl Hamiltona
Graf półhamiltonowski	zawiera ścieżkę przechodząca przez każdy wierzchołek dokładnie raz