2
2
3
Dwa grafy G1 i G2 są izomorficzne, jeżeli istnieje wzajemnie jednoznaczna odpowiedniość m-dzy wierzchołkami grafu G
7
1 i G2 taka,
1
8
7
6
3
10
że liczba krawędzi łączących dane dwa wierzchołki grafu G
1
4
1 jest równa
8
liczbie krawędzi łączących odpowiadające im wierzchołki grafu G2.
9
10
5
Krótko: można znaleźć przyporządkowanie wierzchołków obu grafów, 6
9
dla którego macierze sąsiedztwa są jednakowe.
4
5
Przykład:
Macierze sąsiedztwa
Grafy pokazane na poniższym rysunku są izomorficzne 1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1
1
1 1
1
1
1 1
2
2 1
1
1
2 1
1
1
3
1
1
1
3
1
1
1
1
7
6
3
4
1
1
1
4
1
1
1
8
5 1
1
1
5 1
1
1
9
10
6 1
1 1
6 1
1 1
7
1
1 1
7
1
1 1
4
5
8
1
1
1
8
1
1
1
Proces przyporządkowania wierzchołków 9
1
1 1
9
1
1 1
10
1
1 1
10
1
1 1
a)
2
2
b)
3
c)
2
3
7
8
7
1
1
1
4
Inny graf izomorfizmiczny dla tego grafu 5
5
5
6
6
6
2
2
3
2
3
d)
e)
1
7
6
3
8
7
8
7
10
1
4
1
4
8
9
10
5
5
6
9
4
6
9
5
Grafy planarne - 1
Grafy planarne - 2
Grafy planarne
Grafy planarne – przykłady grafów regularnych Graf planarny to taki graf, który można narysować na płaszczyźnie bez przecięć krawędzi, poza wierzchołkami z którymi sa one incydentne.
Płaski rysunek grafu planarnego nazywamy też grafem płaskim.
Przykłady
Graf Petersena – nieplanarny
Grafy planarne - 3
Grafy planarne - 4
Grafy homeomorficzne - gdy można je otrzymać z tego samego grafu Ściany – spójne obszary płaszczyzny, powstałe z podziału rysunkiem przez wstawienie nowych wierzchołków stopnia 2 wewntrz jego grafu. Punkty grafu nie należą do ściany.
krawędzi.
Twierdzenie (Euler, 1750)
Niech G będzie rysunkiem płaskim spójnego grafu płaskiego, w którym n – liczba wierzchołków
m – liczba krawędzie
f – liczba ścian
Wtedy zachodzi równość
n − m + f = 2
Twierdzenie (Kuratowski, 1930)
Przykład
Graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu homeomorficznego z grafem K
f 5
5 lub K3,3.
f 1
f 4
f
3
f 2
n = 10 m = 13 f = 5 n − m + f = 10 − 13 +5 = 2
Graf K5
Graf K
Wykonać podobne sprawdzenie dla poprzednio podanych planarnych 3,3
regularnych
bez dowodu.
Sciany w grafie planarnym
f
5
f
1
f 4
f 3
f 2
Ściany w grafie - f 5 ściana nieskończona (nieograniczona) Grafy planarne - 5
Grafy planarne - 6