ZASADA WŁĄCZANIA I WYŁĄCZANIA
=
| | −
− ⋯+ (−1)
…
W szczególności
= | | + | | −
DOWÓD szczególnego przypadku
Zbiory A-B, A ⋃ , B-A są parami rozłączne
( − )
(
)
( − ) =
Stąd
= ( − )
(
)
( − ) = | − | +
+ | − |
Stąd
+
= | − | +
+ | − | +
= | − | +
+ | − | +
= ( − )
(
) + ( − )
(
) = | | + | |
A stąd otrzymujemy
= | | + | | −
Co kończy dowód
TWIERDZENIE: Każda mapa może być pokolorowana pięcioma kolorami
DOWÓD: Udowodnimy, że każdy graf planarny da się pokolorować na pięć kolorów (po wierzchołkach)
Indukcja względem liczby wierzchołków:
1Dla ≤ 5 jest to prawda
23. Niech G będzie grafem planarnym o liczbie wierzchołków n>5. Zakładam, że grafy planarne o ilości wierzchołków mniejszej niż n
mogę pokolorować przy pomocy pięciu kolorów.
4
∑
( ) = 2| | ≤ 6| | − 12 ≤ 6| |
Z tego wynika, że istnieje wierzchołek v o stopniu co najwyżej 5
Tworzę podgraf G’ grafu G poprzez usunięcie wierzchołka v i krawędzi do niego incydentnych z grafu G. Graf G’ jest planarny i ma
mniej wierzchołków niż G, stąd z założenia indukcyjnego mogę go pokolorować przy użyciu pięciu kolorów.
Koloruję G’ na 5 kolorów.
Jeśli któryś z pięciu kolorów nie został użyty przy kolorowaniu G’, to mogę go użyć do pokolorowania wierzchołka v w grafie G i mam w nim
pięć kolorów
Dla wszystkich 1 ≤ < ≤ 5 oznaczamy przez
,
podgraf G utworzony przez wierzchołki pokolorowane kolorami i i j oraz krawędzie
między nimi
Np.
,
Jeśli wierzchołki , należą do różnych składowych spójności grafu
,
, to w składowej zawierającej zamieniamy kolory. Wtedy
zyskujemy jeden „wolny” kolor do pokolorowania wierzchołka v
Jeśli wierzchołki należą do tej samej składowej spójności grafu
,
, to
,
Jeśli wierzchołki , są z tej samej składowej spójności co , , to muszą się przeciąć, co oznacza sprzeczność z tym, że graf G jest
planarny
Dowód tw. Halla dla wersji małżeńskiej
<= Jeśle jest spełniony warunek Hall, to każda dziewczyna znajdzie męża.
Indukcja ze względu na m-ilość dziewczyn
1M=1 – oczywiste
2Zakładamy, że stwierdzenie jest prawdziwe dla m dziewcząt, gdzie m>1, czyli dziewcząt 1,…,m może znaleźć sobie mężów, niech to będą
chłopcy 1
I
,…,m
I
3Weźmy dziewczynę m+1 – czy znajdzie męża ? – musimy pokazać, że tak
J4eśli m+1 zna jakiegoś innego chłopaka niż 1
I
,…,m
I
, to tego chłopaka może wziąć za męża.
Dziewczyna m+1 zna tylko chłopców 1
I
,…,m
I
.
Dziewczyna m+1 urządza przyjęcie. Zaprasza na nie wszystkich chłopców których zna 1
I
,…,i
I
. Ci chłopcy biorą na przyjęcie swoje żony 1,…,i.
Dziewczyny 1,…,i zapraszają chłopców, których znają
(m+1) -> (1
I
,…,i
I
) -> (1,…,i) -> ( (i+1)
I
,…,k
I
) ->((i+1),…,k) -> (…,c,…)
A których jeszcze nie ma na przyjęciu, ( (i+1)
I
,…,k).
Oni biorą swoje żony itd. Aż do momentu, w którym pojawi się chłopak c, który nie ma żony. Musi się pojawić, bo jest spełniony warunek
Halla.
Chłopak c tańczy z dziewczyną, która go zaprosiła, powiedzmy p. Dziewczyna p przyszła z chłopakiem p
I
(c,p) ->(p
I
, r) -> … -> (s
I
,t) -> (t
I
,m+1)∈ (1
I
,…,i
I
)
Który tańczy z dziewczyną r.
Każda dziewczyna znalazła męża.
12.Twierdzenie chińskie o resztach + dowód.
Niech m
1
,m
2
,...,m
n
będą dodatnimi liczbami względnie pierwszymi,tzn dla każdej pary 1<=i<=j<=r mamy NWD(m
i
,m
j
)=1,oraz niech a
1
,a
2
,...a
r
będą dowolnymi resztami.Wtedy istnieje liczba całkowita a,taka że:a
1
=a(mod m
1
),a
2
=a(mod m
2
),...,a
r
=a(mod m
r
)
Dowód:
Niech M=m
1
*m
2
*...*m
r
,m
i
,m
j
są względnie pierwsze dla każdego 1£i<j£r
"1£i£r M/m
i
,m
i
-względnie pierwsze,czyli NWD(M/m
i
,m
i
)=1.
W takim razie $x
i
,y
i
: x
i
*M/m
i
+y
i
*m
i
=1.
To z kolei oznacza,że M/m
i
*x
i
º1(mod m
i
), 1£i£r.
M/m
i
jest podzielne bez reszty przez m
j
,j¹i,czyli M/m
i
*x
i
º0(mod m
j
)
Mnożymy przez a
i
M/m
i
*x
i
*a
i
ºa
i
(mod m
i
) dla j¹1 M/m
i
*x
i
*a
i
º0(mod m
j
)
Weźmy:aº(M/m
1
*x
1
*a
1
+M/m
2
*x
2
*a
2
+...+M/m
r
*x
r
*a
r
)(mod m
1
)
aºM/m
1
*x
1
*a
1
(mod m
1
)
aº M/m
2
*x
2
*a
2
(mod m
2
)
aº(M/m
1
*x
1
*a
1
+M/m
2
*x
2
*a
2
+...+M/m
r
*x
r
*a
r
)(mod m
r
)
aº M/m
r
*x
r
*a
r
(mod m
r
)
W takim razie "1£i£r aº(M/m
i
*x
i
*a
i
)(mod m
i
)
Załóżmy teraz,że "1£i£r jest a
i
ºa(mod m
i
) oraz a
i
ºb(mod m
i
) ,b¹a
Odejmujemy stronami:0º(a-b)(mod mi),czyli każda z liczb mi dzieli (a-b)
Ponieważ liczby m
1
,...,m
r
–względnie pierwsze,więc ich iloczyn czyli M również dzieli (a-b)Þa-b różnią się o krotność M.
16.Lemat o uściskach dłoni + dowód.
Niech G będzie grafem prostym.Wówczas deg(v
1
)+...+deg(v
n
)=2m
Dowód:1)Jeśli m=0,to równość jest prawdziwa 2)Zakładamy,że lemat zachodzi dla m³0 3)Udowodnimy równanie dla m+1.Niech eÎE(G)
będzie dowolną krawędzią.Z zał.ind. wiadomo,że deg(v
1
)+...+deg(v
n
)=2m*(G-e),gdzie deg(v
1
) jest stopniem v1 w grafie G-e.Dla grafu G suma
stopni wierzchołków jest o 2 większa niż dla G-e oraz m(G)=m(G-e)+1,co oznacza,że równanie zachodzi dla grafie G o m+1 krawędziach.
Twierdzenie Orego o grafach hamiltonowskich
Dowód: Załóżmy, że istnieją grafy spełniające warunek (Jeżeli dla każdych dwóch nie sąsiednich wierzchołków grafu G suma ich
stopni jest nie mniejsza niż ilość wszystkich wierzchołków w G, to G jest hamiltonowski. *) ale nie hamiltonowskie. Wybieramy
maksymalny (ze względu na ilość krawędzi) taki graf G, który spełnia (*), nie jest hamiltonowski, ale po dodaniu krawędzi stanie się
hamiltonowski. W grafie G jest ścieżka hamiltona.
(v1) = {v2,
,...,
}
~
( 1)={
,…
}
Zauważmy, że (**) (v1)
∩ (vn)≠ ∅
Dowód (**)
Przypuśćmy, że
~
( 1) ∩ (vn)=∅
Wtedy
~
( 1) ∪ (vn)≤{v2,v3,...,vn}
|
~
( 1)∪ (vn)|≤n-2|
~
( 1) + (vn)|≤n-2 (v1)-1+ (vn)≤n-2 (v1)+ (vn)≤n-1
W takim razie
~
( 1)+ (vn)≠ ∅ =>
∃ ∈ ~
( 1) ^ ∈
(vn)
∈ (v1) ∈
(vn)
Cykl Hamiltona w grafie G: (v1,v2,...,vil,vn,vn-1,...,vil+1,v1)
Twierdzenie Kóninga
Jeżeli G jest dwudzielny to
(G)=
∆
Dowód: Niech G-graf dwudzielny
*krawędzie są „pomiędzy” zbiorami podwału
*w grafie dwudzielnym wszystkie cykle jakie istnieją są parzyste
Dowód indukcyjny ze względu na ilość krawędzi (m) w G
(1) m=0,
∆=0, =0=∆ m=1, ∆=1, =1=∆ (2) zakładamy, że dla każdego grafu dwudzielnego G’ o 1<m’<m krawędziach (G’)=∆ (3)
niech G-graf dwudzielny o m krawędziach
Tworzymy G’ usuwając dowolną krawędź czyli
(G’)=
∆ - czyli krawędź w G’ można pokolorować na ∆ kolorów Czy graf G można
pokolorować w
∆ kolorów?
( )= ( )-1≤ ∆-1 ( )= ( )-1≤ ∆-1(a) przy wierzchołku u brakuje koloru c; przy wierzchołku v brakuje tego samego koloru c.
Wtedy kolorem c kolorujemy krawędź uv, mamy pokolrowanie G w
∆ kolorów (b) przy wierzchołku u brakuje koloru c, a przy v brakuje
koloru c’. Rozważmy najdłuższą ścieżkę wychodzącą z wierzchołka u, w której znajdują na przemian krawędzie pokolorowane kolorami c i
c’. W ścieżce wychodzącej od wierzch. U zauważamy kolory c
↔c’. W wyniku tego przy wierzchołku u i v brakuje tego samego koloru c’.
Kolorujemy tym kolorem krawędź uv i mamy kolorwanie grafu G w
∆ kolorów.Twierdzenie Eulera-Nierholtza
Niech G-graf spójny. Następujące własności są równoważne:
-każdy wierzchołek w G ma st. parzysty
-istnieje p cykli c1...cp takich, że każda krawędź grafu G należy do dokładnie jednego cyklu (G można przedstawić jako sumę rozłącznych
krawędziowo cykli)
-G nie jest Eulerowski
Dowód: ''1=>2'' Indukcja ze względu na c-ilość cykli w grafie G
1.
C=1 (rysunek szesciokątu foremnego) G=Cn
2.
Zakładamy, że stwierdzenie zachodzi dla każdego grafu G' o c' cyklach (jeśli każdy st. wierzchołka w grafie G'
jest parzysty, to G' można przedstawić w postaci sumy krawędziowo rozłącznych cykli)
3.
Niech G-graf o c cyklach 1<c'<c, każdy wierzchołek G ma st. parzysty Tworzymy G' usuwając z grafu G
krawędzie dolnego cyklu. Z założenia indukcyjnego G' można podzielić na rozłączne krawędziowo cykle => G też można
''2=>3''
1.
c=1 G=Cn
2.
Zakładając, że stwierdzenie jest prawdziwe dla każdego G' o c' cyklach 1<c'<c (jeśli G' można podzielić na
rozłączne krawędziowo cykle, to w G' można znaleźć domknięty szlak Eulera)
3.
Niech G-graf, który można podzielić na c rozłącznych krawędziowo cykli i c>1 Cyklegrafu G numerujemy w
ten sposób, że (rysunek 7 kół)
Tworzymy graf G' usuwając z G krawędzie ostatniego cyklu (p-tego). Graf G' spełnia zał. indukcyjne, więc w G' istnieje zamknięty szlak
Eulera:(v1,...vn,v1) Dodajemy do G' krawędzie p-tego cyklu. Szukamy zamkniętego szlaku Eulera w G.
(v1,....,vi,.....vj,vi,....,vn,v1)
1 2 3
1.
idziemy po wierzchołkach ze szlaku Eulera z grafu G' aż do napotkania wierzchołka vi bnależącego do cyklu p-
tego
2.
przechodzimy po krawędziach p-tego cyklu
3.
3. część szlaku eulera w G'
„3=>1' Jeśli G jest Eulerowski to każdy wierzchołek ma stopień parzysty.