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.

kwartał w biznesie

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₁,R₂,R₃,R₄,R₅.

Na wykresie znajdują się cztery skończone obszary, tj. r₂,R₃,R₄,R₅.

Istnieje tylko jeden skończony region, tj. r₁

Właściwości grafów planarnych:

1. Jeśli spójny graf planarny G ma e krawędzi i r obszarów, to r ≦ To jest.
2. Jeśli spójny graf planarny G ma e krawędzi, v wierzchołków i r obszarów, to v-e+r=2.
3. Jeśli spójny graf planarny G ma e krawędzie i v wierzchołki, to 3v-e≧6.
4. Kompletny wykres K_Njest planarna wtedy i tylko wtedy, gdy n<5.< li>
5. Kompletny graf dwudzielny K_mnjest planarna wtedy i tylko wtedy, gdy m3.

Przykład: Udowodnić, że pełny graf K₄jest planarny.

Rozwiązanie: Pełny wykres K₄zawiera 4 wierzchołki i 6 krawędzi.

Wiemy, że dla spójnego grafu planarnego 3v-e≧6. Stąd dla K₄, mamy 3x4-6=6, co spełnia własność (3).

cykl życia SDLC

Zatem K₄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₅lub K_3.3

Przerzutnik typu T

Przykład 1: Pokaż, że K₅jest niepłaski.

Rozwiązanie: Pełny wykres K₅zawiera 5 wierzchołków i 10 krawędzi.

Teraz dla połączonego wykresu planarnego 3v-e≧6.

Stąd dla K₅, 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₅jest grafem niepłaskim.

Przykład 2: Pokaż, że wykresy pokazane na rys. nie są planarne, znajdując podgraf homeomorficzny dla K₅lub K_3.3.

Rozwiązanie: Jeśli usuniemy krawędzie (V₁,W₄),(W₃,W₄) i (V₅,W₄) wykres G₁, staje się homeomorficzny z K₅Dlatego nie jest planarny.

Jeśli usuniemy krawędź V_{2, V}7) wykres G₂staje się homeomorficzny z K_3.3Dlatego 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).

próba złapania Java

Przykład: Liczba chromatyczna K_Njest n.

Rozwiązanie: Kolorystyka K_Nmoż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∈Vstopień(v)=2e

Dowód: Niech G = (V, E) będzie wykresem, w którym V = {v₁,W₂, . . . . . . . . . .} będzie zbiorem wierzchołków i E = {e₁,To jest₂. . . . . . . . . .} 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∈Vstopień(v)=2e

lista religii