Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 29

Wiele twierdzeń głosi, że istnieje pewien określony typ obiektu. Jedna z metod dowiedzenia takiego twierdzenia polega na zademonstrowaniu, jak skonstruować taki obiekt. Technika ta jest nazywana dowodem przez konstrukcję (dowodem konstrukcyjnym).

Spróbujmy użyć dowodu przez konstrukcję dla wykazania następującego twierdzenia. Graf definiujemy jako k-regularny, jeśli każdy wierzchołek grafu ma stopień k.

Twierdzenie 0.22

Dla każdej liczby parzystej n większej od 2 istnieje 3-regularny graf o n wierzchołkach.

Dowód Niech n będzie liczbą parzystą większą od 2. Konstruujemy graf G = (V, E) o n wierzchołkach zgodnie z następującą procedurą: zbiór wierzchołków G to V = {0, 1, …, n − 1}, zaś zbiór krawędzi G to zbiór

E = { {i, i + 1} : dla 0 ≤ i ≤ n − 2} ∪ { {n − 1, 0} }∪ { {i, i + n/2} : dla 0 ≤ i ≤ n/2 − 1}.

Wierzchołki tego grafu można przedstawić, rozmieszczając je równomiernie na okręgu. W tym przypadku krawędzie opisane przez górny wiersz definicji zbioru E łączą sąsiadujące pary wierzchołków wokół okręgu. Krawędzi opisane w dolnym wierszu definicji zbioru E biegną między wierzchołkami po przeciwnej stronie okręgu. Taki myślowy obraz jasno pokazuje, że każdy wierzchołek grafu G ma stopień 3.