Wykres planarny:
Graf nazywamy planarnym, jeśli można go narysować na płaszczyźnie tak, aby żadne krawędzie się nie przecinały.
Przykład: Wykres pokazany na rys. jest grafem planarnym.
Region wykresu: Rozważmy graf planarny G=(V,E). Region definiuje się jako obszar płaszczyzny ograniczony krawędziami i nie dający się dalej dzielić. Wykres planarny dzieli plany na jeden lub więcej regionów. Jeden z tych obszarów będzie nieskończony.
Skończony region: Jeśli obszar regionu jest skończony, wówczas obszar ten nazywa się obszarem skończonym.
Nieskończony obszar: Jeśli obszar regionu jest nieskończony, obszar ten nazywa się obszarem nieskończonym. Graf planarny ma tylko jeden nieskończony obszar.
Przykład: Rozważ wykres pokazany na ryc. Określ liczbę regionów, skończonych regionów i nieskończonego regionu.
Rozwiązanie: Na powyższym wykresie znajduje się pięć regionów, tj. r 1 ,R 2 ,R 3 ,R 4 ,R 5 .
Na wykresie znajdują się cztery skończone obszary, tj. r 2 ,R 3 ,R 4 ,R 5 .
Istnieje tylko jeden skończony region, tj. r 1
Właściwości grafów planarnych:
- Jeśli spójny graf planarny G ma e krawędzi i r obszarów, to r ≦
To jest. - Jeśli spójny graf planarny G ma e krawędzi, v wierzchołków i r obszarów, to v-e+r=2.
- Jeśli spójny graf planarny G ma e krawędzie i v wierzchołki, to 3v-e≧6.
- Kompletny wykres K N jest planarna wtedy i tylko wtedy, gdy n <5. < li>
- Kompletny graf dwudzielny K mn jest planarna wtedy i tylko wtedy, gdy m3.
Przykład: Udowodnić, że pełny graf K 4 jest planarny.
Rozwiązanie: Pełny wykres K 4 zawiera 4 wierzchołki i 6 krawędzi.
Wiemy, że dla spójnego grafu planarnego 3v-e≧6. Stąd dla K 4 , mamy 3x4-6=6, co spełnia własność (3).
Zatem K 4 jest grafem planarnym. Stąd udowodnione.
Wykres niepłaski:
Graf nazywamy niepłaskim, jeśli nie można go narysować na płaszczyźnie tak, aby żadne krawędzie się nie przecinały.
Przykład: Wykresy pokazane na rys. nie są wykresami planarnymi.
Wykresów tych nie można narysować na płaszczyźnie, tak aby żadne krawędzie się nie przecinały, dlatego są to wykresy niepłaskie.
Właściwości grafów nieplanarnych:
Wykres jest niepłaski wtedy i tylko wtedy, gdy zawiera podgraf homeomorficzny z K 5 lub K 3.3
Przykład 1: Pokaż, że K 5 jest niepłaski.
Rozwiązanie: Pełny wykres K 5 zawiera 5 wierzchołków i 10 krawędzi.
Teraz dla połączonego wykresu planarnego 3v-e≧6.
Stąd dla K 5 , mamy 3 x 5-10=5 (co nie spełnia własności 3, ponieważ musi być większa lub równa 6).
Zatem K 5 jest grafem niepłaskim.
Przykład 2: Pokaż, że wykresy pokazane na rys. nie są planarne, znajdując podgraf homeomorficzny dla K 5 lub K 3.3 .
Rozwiązanie: Jeśli usuniemy krawędzie (V 1 ,W 4 ),(W 3 ,W 4 ) i (V 5 ,W 4 ) wykres G 1 , staje się homeomorficzny z K 5 Dlatego nie jest planarny.
Jeśli usuniemy krawędź V 2, V 7) wykres G 2 staje się homeomorficzny z K 3.3 Dlatego jest niepłaski.
Kolorowanie wykresu:
Załóżmy, że G= (V,E) jest grafem bez wielu krawędzi. Kolorowanie wierzchołków G to przypisanie kolorów wierzchołkom G w taki sposób, że sąsiednie wierzchołki mają różne kolory. Wykres G jest M-Kolorowalny, jeśli istnieje kolorowanie G wykorzystujące M-Kolorowe.
Właściwa kolorystyka: Kolorowanie jest właściwe, jeśli dowolne dwa sąsiednie wierzchołki u i v mają różne kolory, w przeciwnym razie nazywa się to kolorowaniem niewłaściwym.
Przykład: Rozważ poniższy wykres i pokoloruj C={r, w, b, y}. Pokoloruj odpowiednio wykres, używając wszystkich lub mniejszej liczby kolorów.
Wykres pokazany na rys. jest co najmniej 3-kolorowalny, stąd x(G)=3
Rozwiązanie: Ryc. pokazuje wykres poprawnie pokolorowany wszystkimi czterema kolorami.
Ryc. pokazuje wykres odpowiednio pokolorowany trzema kolorami.
Liczba chromatyczna G: Minimalna liczba kolorów potrzebna do prawidłowego pokolorowania grafu G nazywana jest liczbą chromatyczną G i oznaczana przez x(G).
Przykład: Liczba chromatyczna K N jest n.
Rozwiązanie: Kolorystyka K N można skonstruować przy użyciu n kolorów, przypisując różne kolory każdemu wierzchołkowi. Nie można przypisać dwóm wierzchołkom tego samego koloru, ponieważ każde dwa wierzchołki tego grafu sąsiadują ze sobą. Stąd liczba chromatyczna K N =rzecz.
Zastosowania kolorowania wykresów
Niektóre zastosowania kolorowania wykresów obejmują:
- Zarejestruj alokację
- Kolorowanie mapy
- Sprawdzanie wykresu dwudzielnego
- Przydzielanie częstotliwości radiowych mobilnych
- Sporządzanie harmonogramu itp.
Sformułuj i udowodnij twierdzenie o uścisku dłoni.
Twierdzenie o uścisku dłoni: Suma stopni wszystkich wierzchołków grafu G jest równa dwukrotności liczby krawędzi grafu.
Matematycznie można to określić jako:
∑ v∈V stopień(v)=2e
Dowód: Niech G = (V, E) będzie wykresem, w którym V = {v 1 ,W 2 , . . . . . . . . . .} będzie zbiorem wierzchołków i E = {e 1 ,To jest 2 . . . . . . . . . .} będzie zbiorem krawędzi. Wiemy, że każda krawędź leży pomiędzy dwoma wierzchołkami, więc zapewnia stopień pierwszy każdemu wierzchołkowi. Zatem każda krawędź wnosi stopień drugi do wykresu. Zatem suma stopni wszystkich wierzchołków jest równa dwukrotności liczby krawędzi w G.
Stąd ∑ v∈V stopień(v)=2e
