Stopień wierzchołka v w grafie Gto liczba krawędzi dochodzących do tego wierzchołka.

Stopień wierzchołka v w grafie G oznaczamy degG(v).

Ważnymi parametrami są największy (oznaczany przez Δ(G)) i najmniejszy(oznaczany przez δ(G)) stopień wierzchołka w grafie G.

Na poniższym przykładzie można sprawdzić stopnie poszczególnych wierzchołków klikając na nie. Można też sprawdzić Δ(G) i δ(G) .










Graf regularny albo r-regularny to graf, w którym każdy wierzchołek ma ten sam stopień równy r .

??? Który z poniższych grafów jest 4-regularny?



















ROZWIĄZANIE:

Pierwszy graf jest 4-regularny. Drugi nie jest 4-regularny, bo zawiera wierzchołki stopnia 5 (zaznaczone na rysunku).










Drogą w grafie G nazywamy taki ciąg jego wierzchołków v1,v2,...,vk , że każde dwa kolejne wierzchołki w tym ciągu są połączone krawędzią (czyli można przejść z jednego końca drogi na drugi chodząc tylko po krawędziach).

Zaznacz na rysunku dwa wierzchołki, a komputer pokaże ci jedną z dróg między nimi (o ile istnieje).











Cykl w grafie G to droga w tym grafie, która kończy się w tym samym wierzchołku, w którym się zaczęła.

??? Czy w poniższym grafie istnieje cykl zawierający wszystkie jego wierzchołki? A może istnieje cykl, zawierający wszystkie wierzchołki oprócz jednego?











ROZWIĄZANIE: W tym grafie nie istnieje cykl zawierający wszystkie wierzchołki, ale dla każdego wierzchołka v można znalexć taki cykl, który zawiera wszystkie wierzchołki grafu oprócz v . Na rysunku podano przykład takiego cyklu.











W roku 1856 sir William Rowan Hamilton postanowił trochę zarobić, więc zaczął sprzedawać następującą łamigłowkę. Wyobraxmy sobie drewniany klocek o kształcie dwunastościanu foremnego. Należało znaleźć drogę złożoną z krawędzi klocka przechodzącą dokładnie raz przez każdy jego wierzchołek i wracającą do wierzchołka wyjściowego.

Taką drogę w grafie nazywamy cyklem Hamiltona.

??? Rozwiązanie zagadki sir Hamiltona sprowadza się do znalezienia cyklu Hamiltona w poniższym grafie. Sprawdź, czy potrafisz.











ROZWIĄZANIE: Na rysunku podano przykładowy cykl Hamiltona w tym grafie.









Graf spójny to graf, w którym każde dwa wierzchołki są połączone drogą.

Inaczej mówiąc, graf śkłada się z jednego kawałka. Jeśli graf nie jest spójny, to jego spójne kawałki, między którymi nie ma połączenia, nazywamy składowymi grafu.

??? Czy poniższy graf jest spójny? Jeśli nie, to znajdź jego składowe.










ROZWIĄZANIE: Graf nie jest spójny. Na rysunku pokazano dwie składowe grafu.










Graf G jest izomorficzny z grafem H jeśli istnieje takie, różnowartościowe i ńa, przyporządkowanie (bijekcja) wierzchołków grafu H wierzchołkom grafu G , że jeśli jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, to odpowiadające im wierzchołki w drugim grafie również łączy krawędź.

Izomorfizm grafów zachowuje właściwie wszystkie interesujące własności, na przykład: liczbę wierzchołków, liczbę krawędzi, stopnie wierzchołków, spójność, planarność. Dlatego grafy izomorficzne zwykle utożsamia się.

??? Który z grafów B lub C jest izomorficzny z grafem A?

A:








B: C:








ROZWIĄZANIE: Graf B jest izomorficzny z grafem A. Na rysunku podano bijekcję między wierzchołkami obu grafów.

Graf C nie jest izomorficzny z grafem A, gdyż usunięcie dwóch zaznaczonych wierzchołków spowoduje, że graf przestanie być spójny. W grafie A takie wierzchołki nie istnieją.

A: B:








C:








Podgraf grafu G to graf, którego wierzchołki stanowią podzbiór zbioru wierzchołków grafu G , a krawędzie podzbiór zbioru krawędzi G .

??? Znajdź w grafie A podgraf izomorficzny z grafem B.

A: B:








ROZWIĄZANIE: Na rysunku zaznaczono poszukiwany podgraf.

A: B:








Graf nazywamy dwudzielnym jeśli zbiór jego wierzchołków można podzielić na takie dwa rozłączne podzbiory X i Y , że każda krawędź grafu ma jeden koniec w X a drugi w Y .

Innymi słowy są to wszystkie grafy, których wierzchołki można pokolorować na dwa kolory tak, aby końce każdej krawędzi miały różne kolory.

??? Który z tych grafów jest dwudzielny?

A: B:








ROZWIĄZANIE: Graf A nie jest dwudzielny, bo zawiera cykl o nieparzystej liczbie wierzchołków. Zauważmy, że wierzchołków leżących na takim cyklu nie da się pokolorować na dwa kolory tak, aby końce każdej krawędzi miały różne kolory.

Graf B jest dwudzielny. Podzbiory, na które dzielimy zbiór wierzchołków grafu, zaznaczono na rysunku innym kształtem.

B:








Graf nazywamy płaskim lub planarnym jeśli można go narysować na płaszczyźnie w ten sposób, że krawędzie nigdzie nie będą się przecinać.

Graf, którego nie można narysować tak, aby krawędzie nie przecinały się, nazywamy nieplanarnym.

??? Czy poniższy graf jest planarny?











ROZWIĄZANIE: Tak. Na rysunku pokazano inny - bez przecinania się krawędzi - sposób narysowania tego grafu. Ponumerowano wierzchołki obu grafów, aby lepiej uwidocznić izomorfizm między nimi.











Grubością grafu nazywamy najmniejszą liczbę planarnych podgrafów, na które można podzielić dany graf.

Grubość grafu G oznaczamy t(G) .

Każdy graf planarny ma grubość równą 1.

??? Znajdź grubość poniższego grafu.











ROZWIĄZANIE: Można się przekonać, że graf nie jest planarny, więc jego grubość jest większa niż 1. Na rysunku pokazano podział grafu na dwa grafy planarne, więc t(G) = 2 .











Spójnością grafu lub spójnością wierzchołkową grafu nazywamy taką liczbę k , że usunięcie z grafu pewnych k wierzchołków spowoduje, że graf przestanie być spójny lub zredukuje go do jednego wierzchołka, ale usunięcie dowolnych k-1 wierzchołków zawsze pozostawi graf spójny.

(Wierzchołki usuwamy wraz z dochodzącymi do nich krawędziami.)

Spójność grafu G oznaczamy κ(G) .

??? Czy istnieje graf 3-regularny o spójności 1?

ROZWIĄZANIE: Takich grafów istnieje nieskończenie wiele. Na rysunku pokazano przykład grafu o tych własnościach.












Spójnością krawędziową grafu nazywamy taką liczbę k , że usunięcie z grafu pewnych k krawędzi spowoduje, że graf przestanie być spójny, ale usunięcie dowolnych k-1 krawędzi zawsze pozostawi graf spójny.

(Krawędzie usuwamy bez wierzchołków do których dochodzą.)

Spójność krawędziową grafu G oznaczamy κ'(G) .

Można pokazać, że zachodzi zależność:

kappa(G) κ'(G) δ(G) .

??? Czy istnieje graf o δ(G) = 3, κ'(G) = 2 i κ(G) = 1 ?

ROZWIĄZANIE: Istnieje taki graf. Na rysunku pokazano przykład grafu o tych własnościach.












Liczbą chromatyczną grafu nazywamy najmniejszą liczbę kolorów, którymi można pokolorować wierzchołki grafu w taki sposób, aby każde dwa wierzchołki połączone krawędzią miały różne kolory.

Liczbę chromatyczną grafu G oznaczamy χ(G) .

??? Znajdź liczbę chromatyczną poniższego grafu.











ROZWIĄZANIE: χ(G) = 3 . Na rysunku pokazano przykład pokolorowania wierzchołków grafu na 3 kolory.











Indeksem chromatycznym grafu nazywamy najmniejszą liczbę kolorów, którymi można pokolorować krawędzie grafu w taki sposób, aby każde dwie krawędzie o wspólnym końcu miały różne kolory.

Indeks chromatyczny grafu G oznaczamy χ'(G) .

W 1964 roku Vizing udowodnił, że:

Δ(G) χ'(G) Δ(G) + 1 .

??? Znajdź indeks chromatyczny poniższego grafu.










ROZWIĄZANIE: χ'(G) = 4 . Na rysunku pokazano przykład pokolorowania krawędzi grafu na 4 kolory.












next up previous
Administrator 2000-05-27

[ Początek strony ] [ MiNIWykłady ]


Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej