Teoria grafow kombinatoryka

Spójny graf nieskierowany bez cykli; między każdą parą wierzchołków istnieje dokładnie jedna ścieżka.

Drzewo zawierające wszystkie wierzchołki grafu ważonego i mające najmniejszą możliwą sumę wag krawędzi.

Przypisanie etykiet (kolorów) wierzchołkom tak, by sąsiednie wierzchołki miały różne kolory, zwykle przy minimalnej liczbie kolorów.

Najmniejsza liczba kolorów potrzebna do poprawnego pokolorowania wierzchołków grafu tak, by sąsiednie miały różne kolory.

Liczba sposobów wyboru k-elementowego podzbioru ze zbioru n-elementowego, oznaczana C(n,k); podstawowa wielkość kombinatoryki przeliczeniowej.

Zamknięta marszruta o co najmniej trzech wierzchołkach, w której wierzchołek początkowy pokrywa się z końcowym, a pozostałe się nie powtarzają.

Ciąg wierzchołków połączonych krawędziami, w którym żaden wierzchołek nie powtarza się; łączy wierzchołek początkowy z końcowym.

Zamknięta marszruta przechodząca przez każdą krawędź grafu dokładnie raz; istnieje wtedy, gdy graf jest spójny i wszystkie stopnie są parzyste.

Liczba krawędzi incydentnych z danym wierzchołkiem; w grafie skierowanym rozróżnia się stopień wejściowy i wyjściowy.

Graf, który można narysować na płaszczyźnie tak, że jego krawędzie przecinają się wyłącznie we wspólnych wierzchołkach.

Skierowany graf acykliczny (directed acyclic graph) — digraf bez cykli skierowanych; dopuszcza sortowanie topologiczne wierzchołków.

Graf, którego wierzchołki dzielą się na dwa rozłączne zbiory tak, że każda krawędź łączy wierzchołek z jednego zbioru z wierzchołkiem z drugiego.

Graf, w którym krawędzie (łuki) mają ustaloną orientację — są uporządkowanymi parami wierzchołków wskazującymi kierunek relacji.

Funkcja przypisująca łukom sieci wartości spełniające ograniczenia przepustowości i zachowania przepływu w wierzchołkach pośrednich.

Zbiór krawędzi grafu, z których żadne dwie nie mają wspólnego wierzchołka; skojarzenie maksymalne ma największą liczność.

Własność grafu polegająca na istnieniu ścieżki między każdą parą wierzchołków; w grafach skierowanych rozróżnia się spójność silną i słabą.