Na dzisiejszych zajęciach dokończymy temat izomorfizmu grafów nieskierowanych. Dwa grafy
są izomorficzne, gdy
, oraz gdy istnieje
, która jest bijekcją taką, że
. Stąd wynikają trzy warunki konieczne izomorfizmu. A mianowicie:

1. |V'| = |V''|, czyli, że grafy izomorficzne maja tą samą liczbę wierzchołków

2. |E'| = |E''|, czyli, że grafy izomorficzne maja tą samą liczbę krawędzi

3. d(i) = d(f(i)), czyli, że stopnie wierzchołków izomorficznych (przeprowadzanych przez to f) są równe.

I teraz powiedzmy sobie kilka słów o macierzach reprezentacji grafów. Na poczatek powiedzmy o macierzy incydencji grafu skierowaneego. Macierzą incydencji grafu zorientowanego (skierowanego) G = (V, K) o zbiorze wierzchołków V =
i krawędzi K =
nazywamy macierz M = (
), gdzie i = 1,...,n oraz j = 1,...,m taką, że:

Przykładowo jeśli:

,
,
,

oznaczają wszystkie krawędzie grafu skierowanego z przykładowego rysunku, to macierz incydencji o kolumnach e_i i wierszach v_i może wyglądać tak:

Kolejna rzecz, to macierz sąsiedztwa. W teorii grafów macierz sąsiedztwa grafu G jest kwadratową macierzą w której
oznacza liczbę krawędzi pomiędzy wierzchołkami i i j. W przypadku grafów prostych macierz sąsiedztwa jest macierzą zerojedynkową z zerami na głównej przekątnej. Dla grafów nieskierowanych macierz sąsiedztwa jest z definicji symetryczna. Dla przykładowego grafu o sześciu wierzchołkach oraz siedmiu krawędziach:

macierz sąsiedztwa jest następująca:

Macierz sąsiedztwa dla grafów nieskierowanych jest z definicji symetryczna. W szczególności oznacza to że ma wszystkie wartości własne rzeczywiste, i pełen zbiór ortogonalnych wektorów własnych. Zbiór wartości własnych tej macierzy określa się jako widmo grafu. Izomorfizmowi grafów odpowiada permutacja macierzy sąsiedztwa. Oznacza to że grafy izomorficzne mają ten sam wielomian charakterystyczny, zbiór wartości własnych, wyznacznik, oraz ślad. Odwrotna zależność nie jest prawdziwa - grafy z takim samym wielomianem charakterystycznym nie muszą być izomorficzne. Jeśli A jest macierzą sąsiedztwa grafu skierowanego G, to macierz
(enta potęga macierzy A) ma następującą interpretację:
oznacza liczbę ścieżek długości n z wierzchołka i do wierzchołka j.

Dla grafów skierowanych macierz I − A (gdzie I oznacza macierz jednostkową) jest odwracalna wtedy i tylko wtedy gdy graf G nie zawiera cykli. W takim przypadku (I − A)−1 ma następującą interpretację: aij oznacza liczbę wszystkich ścieżek z wierzchołka i do wierzchołka j (przy braku cykli ta liczba jest skończona). Wynika to z rozwinięcia tej odwrotności w szereg geometryczny dla macierzy:

(I − A) −1 = I + A + A2 + A3 + ... odpowiadający sumowaniu liczby ścieżek długości 0, długości 1, 2 i tak dalej. Przy okazji macierzy sąsiedztwa mówi się czasem o macierzy diagonalnej. Jest to macierz
gdzie
. Przykładowo macierz

jest macierzą diagonalną, bo ma wszedzie zera, a jedynie nie ma ich po przekatnej z góry na dół.

Następne zagadnienia o jakich będziemy mówić, to drogi i cykle. Droga to wyznaczona przez krawędzie trasa polegająca na podróżowaniu od wierzchołka do wierzchołka po łączących je krawędziach. Jeżeli przez ei oznaczy się i-tą krawędź grafu, to droga może być jednoznacznie zapisana jako
. Z kolei cykl to zamknięta droga prosta
, taka, że krawędź
kończy się w początkowym wierzchołku drogi. Drogą w grafie nazywamy elementarną, jeśli żadne dwa wierzchołki się w niej nie powtarzają. Droga nazywamy prostą z kolei, jeśli nie powtarzają się w niej krawędzie. Stąd wniosek, że każda droga elementarna jest prosta, ale już nie odwrotnie. Kolejne ważne pojęcie to cykl elementarny. Jest to zamknięta droga elementarna. Cykl prosty z kolei to zamknięta droga prosta. Graf nazywamy spójnym, gdy dowolne dwa wierzchołki grafu możemy połączyć drogą. Jeśli nie będzie to możliwe, graf będzie niespójny. Istnieje jeszcze pojęcie składowej spójnej grafu. Maksymalny w sensie inkluzji spójny podgraf grafu nazywamy spójną składową. Ilość spójnych składowych grafu G oznacza się przez
. Inaczej spójną składową grafu G jest jego spójny podgraf nie zawarty w większym podgrafie spójnym grafu G. Nieformalnie spójna składowa grafu jest to taki podgraf, który można wydzielić z całego grafu bez usuwania krawędzi. Graf spójny ma jedną spójna składową. Dla przykładu, w lesie spójnymi składowymi są drzewa.Spójna składowa to fragment grafu, który nie jest połączony z innym fragmentem. Oczywiście
.
oznacza, że graf G jest spójny, zaś
oznacza, że G składa się z | G(V) | izolowanych wierzchołków. Graf nazywamyseparowalnym, gdy po usunięciu z niego wierzchołka, straci on swoją spójność. Nastepne pojęcie to most grafu. Jest to krawędź grafu spójnego której usunięcie z grafu rozspójnia go na dwa grafy niepuste. Grafem pustym byłby bowiem izolowany wierzchołek. Jeśli graf nieskierowany ma n wierzchołków, m krawędzi, oraz k składowych spójnych, to wtedy mamy taką nierówność:

. Przykładowo dla grafu spójnego o k = 1 nierównośc ma postać:
. I na zakończenie wykładu omówmy sobie klasy grafów. Klasa grafów to zbiór grafów zawierający wszystkie grafy spełniające jakieś warunki. Przykładowo klasa grafów pełnych zawiera wszystkie grafy w których istnieje krawędź pomiędzy dowolnymi dwoma wierzchołkami. W teorii grafów wyróżnia się wiele klas grafów. Jednym z powodów jest to, że pewne problemy teorii grafów, których nie potrafimy efektywnie rozwiązać dla wszystkich grafów, są łatwo rozwiązywalne dla pewnych klas grafów. Klasą grafu może być graf pełny. Graf pełny jest grafem prostym, w którym dla każdej pary węzłów istnieje krawędź je łącząca. Graf pełny o n wierzchołkach oznacza się następująco: K_n.Oto jego własności:

• pełny graf o n wierzchołkach posiada
  krawędzi

• pełny graf stopnia n jest grafem regularnym stopnia n − 1

• wszystkie grafy pełne są swoimi klikami

• żaden z grafów pełnych stopnia co najmniej 5 nie jest planarny (wynika z twierdzenia Kuratowskiego)

Oto grafy pełne o liczbie wierchołków od 1 do 8:

No i omówmy sobie jeszcze jedną klasę grafów, a mianowicie kostki n - wymiarowe Qn mające 2 do entej wierzchołków. Przykładowo dla Q2:

Graf skierowany

(1,1)

(1,0)

(0,1)

(0,0)

---