1-3

Graf (nieskierowany)

Graf (nieskierowany) to uporządkowana para zbiorów: G = (V, E), gdzie: a. V to zbiór wierzchołków grafu; b. E to zbiór krawędzi grafu G; c. każda krawędź e = {v, w} ze zbioru E to nieuporządkowana para wierzchołków ze zbioru V, zwanych końcami krawędzi e.

Graf skierowany

uporządkowana para zbiorów: G = (V, E), gdzie: a. V to zbiór wierzchołków grafu; b. E to zbiór krawędzi grafu G; c. każda (skierowana) krawędź e = (v,w) ze zbioru E to uporządkowana para wierzchołków ze zbioru V, zwanych początkiem i końcem krawędzi e.

Wierzchołek

w teorii grafów punkt pewnej przestrzeni (zbioru) V nad którą zbudowany jest graf G=(V,E), gdzie E jest zbiorem jego krawędzi.

Krawędzie

stanowią one reprezentację relacji pomiędzy wierzchołkami. Dla krawędzi e = {v, w} ∈ E mówimy też: a. krawędź e łączy wierzchołki v i w; b. wierzchołki v i w są sąsiednie w grafe c. krawędź e jest incydentna z wierzchołkiem v i w.

Łuki

krawędzie skierowane.

Pętle

krawędź postaci (v, v).

Grafy proste

nie ma pętli ani krawędzi wielokrotnych (uwaga: dla grafu skierowanego krawędzie (v, w) i (w, v) są różne, a więc mogą występować obie na raz i nie będzie to krawędź wielokrotna).

Izomorfizm

Grafy G1 (V1, E1) i G2 (V2, E2) są izomorficzne ⇔ istnieje bijekcja f pomiędzy zbiorami wierzchołków V1 i V2, f: V1 → V2 zachowująca krawędzie, tzn. wierzchołki v i w są połączone krawędzią w grafie G1 ⇔ f (v), f (w) są połączone krawędzią w grafie G2.

Spójność

graf jest spójny, gdy każde dwa różne wierzchołki grafu są połączone drogą

Składowa spójne

- to maksymalny podgraf grafu, który jest spójny

Składowa silnie spójna

to taki maksymalny podgraf grafu, w którym dla każdej uporządkowanej pary różnych wierzchołków istnieje droga skierowana z pierwszego do drugiego.

Sąsiedztwo

Wierzchołki nazywamy sąsiednie, jeśli istnieje krawędź (skierowana lub nieskierowana) pomiędzy nimi.

Incydentność

Jeśli krawędź e jest incydentna z wierzchołkiem v i w to ma ona w tym wierzchołku swój koniec lub początek (wychodzi lub wchodzi do tego wierzchołka).

Stopnie

wierzchołka, deg(v), liczba krawędzi incydentnych z tym wierzchołkiem. Każda pętla w grafach nieprostych wnosi 2 do stopnia wierzchołka.

Ciąg stopni

ciąg stopni wierzchołków w kolejności wzrastającej, z uwzględnieniem powtórzeń, np. (3,3,5,5,5,5).

Lemat o uściskach dłoni

suma stopni wierzchołków grafu jest parzysta wniosek: liczba wierzchołków nieparzystego stopnia musi być parzysta

Podgraf

- Podgrafem grafu G = (V, E) nazywamy graf H = (V’, E’) taki, że V’ ⊆ V i E’ ⊆ E (czyli reprezentowany przez podzbiory wierzchołków i krawędz

Macierze sąsiedztwa

dla G = (V, E), o n wierz. macierz s. grafu G to kwadratowa macierz A o n wierszach i kolumnach, taka, że A[i, j] = 1 ⇔ wierzchołki i, j są połączone krawędzią, A[i, j] = 0 w przeciwnym przypadku. petla -wartosc 2

Macierz incydencji

Macierz I, gdzie wiersze odpowiadają wierzchołkom a kolumny krawędziom. I[v, e] zawiera 1 ⇔ v jest incydentny z e. W przeciwnym razie zawiera 0. Dla grafów skierowanych: 1 dla wchodzących, -1 dla wychodzących.

Listy sąsiedztwa

Reprezentacja ta składa się z list odpowiadających poszczególnym wierzchołkom. Każda lista rozpoczyna się od etykiety wierzchołka, po której następuje lista wierzchołków sąsiednich. Lista sąsiedztwa ma rozmiar Θ(n + m), czyli dostosowuje się do licz kraw

Graf pusty (Nn)

graf składający się jedynie z wierzchołków który nie zawiera żadnych krawędzi

Graf pełny (Kn)

to graf prosty, w którym każde dwa wierzchołki są połączone krawędzią. (dopełnienie pustego). Liczba krawędzi w grafie pełnym wynosi n*(n-1).

Graf acykliczny

graf nie zawierający cykli. W przypadku grafów nieskierowanych spójnych grafy acykliczne są równoważne drzewom, a niespójne – lasom.

Graf liniowy (ścieżkowe) (Pn)

- graf, otrzymany poprzez usunięcie jednej krawędzi z grafu cyklicznego Cn (czyli grafu spójnego, regularnego stopnia 2) Uwaga: graf cykliczny to niekoniecznie graf który po prostu zawiera cykl.

Grafy koła (Wn)

to grafy powstałe przez dodanie do cyklu jeszcze jednego wierzchołka i połączenie tego wierzchołka ze wszystkimi wierzchołkami cyklu.

Grafy regularne

graf, w którym wszystkie stopnie są równe i nazywamy regularnym stopnia i (lub i-regularnym).

Grafy kubiczne

Graf 3-regularny nazywamy kubicznym

Graf Petersena

nieskierowany graf o 10 wierzchołkach i 15 krawędziach, który: ● 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.