MATEMATYKA DYSKRETNA
Skrypt pisany na podstawie wykładu prowadzonego przez
Dr. T. Traczyka
Wiadomości wstępne
Tw. O indukcji matematycznej
Zasada szufladkowa Dirichleta
Jeżeli do n szuflad włożymy n+1 przedmiotów, to w co najmniej jednej szufladzie będzie 2 lub więcej przedmiotów.
Definicje
Def. Grafem nazywamy parę 
gdzie 
- zbiór (skończony) niepusty, 
- zbiór wierzchołków
- zbiór krawędzi
Def. Stopniem wierzchołka 
w grafie 
jest liczba 
Def. 
wtedy v - izolowany
wtedy v - liść
Def. 
, 
u-v drogą w G nazywamy ciąg 
gdzie
1) 
2) 
3) 
Liczbę k nazywamy długością drogi. Jeżeli ponadto 
to 
jest drogą prostą.
Def. G jest grafem spójnym 
u-v droga w 
Def. Jeżeli w drodze 
to drogę nazywamy cyklem. Jeżeli w drodze prostej 
sąsiaduje z 
, to drogę nazywamy cyklem prostym.
Def. Dopełnieniem grafu 
nazywamy graf 
. W dopełnieniu grafu G sąsiadują te, i tylko te wierzchołki, które nie sąsiadowały w G.
Graf i jego dopełnienie.
Def. 
jest pograłem 
Graf i jego podgraf.
Def. H jest nadgrafem G 
G jest podgrafem H.
Def. 
jest pograłem indukowanym 
Graf i jego podgraf indukowany.
Def. H jest podgrafem rozpinającym w 
Graf i jego podgraf rozpinający.
Def. Najmniejszy stopień wierzchołka w grafie G - 
Def. Największy stopień wierzchołka w grafie G - 
Def. G jest r-regularny 
Graf 4-regularny o 7 wierzchołkach.
Def. 
- graf pełny o n wierzchołkach - 
Grafy pełne.
Def. 
i 
są izomorficzne 
.
Izomorfizm grafów oznacza się 
Def. Graf jest acykliczny wtedy i tylko wtedy, kiedy nie zawiera cykli.
Def. Grafem krawędziowym grafu G nazywamy graf L(G) taki, że istnieje bijekcja z V(G) do E(L(G)) taka, że wierzchołki odpowiadające krawędziom e i f w grafie G są połączone krawędzią w L(G) 
e i f mają wspólny wierzchołek w G.
Grafy 
i 
.
Twierdzenia
Lemat O uściskach dłoni.
Lemat 
w G istnieje pewien cykl (prosty).
Spójność
Definicje
Def. Graf G jest k-spójny (wierzchołkowo) 
spójny). Spójnością grafu G nazywamy największe k takie, ze G jest k-spójny i oznaczamy 
.
Def. Graf G jest l-spójny krawędziowo 
spójny). Spójnością krawędziową grafu G nazywamy największe l takie, ze G jest l-spójny krawędziowo i oznaczamy 
Def. 
- ilość sąsiadów podzbioru S
Def. 
i
. Zbiór 
jest x-y oddzielający 
każda x-y droga przechodzi przez S 
w G-S x i y są w różnych składowych.
Twierdzenia
Tw. W grafie prostym mającym n wierzchołków, k składowych i m krawędzi zachodzi nierówność:
Tw. Whitney'a
Tw. Graf jest dwuspójny 
każde dwa wierzchołki z G leża na pewnym cyklu prostym
Tw. Halla (o zawieraniu małżeństw)
G - graf dwudzielny X na Y. G ma 
niezależnych krawędzi 
. Powyższy warunek nosi nazwę warunku Halla.
Tw. Mengera (1927)
Jeśli dla każdego u-v zbioru rozdzielającego S mamy 
, to w G istnieje k rozłącznych u-v dróg.
Tw. Këniga - Halla
W każdym grafie dwudzielnym 
.
Drzewa
Definicje
Def. Drzewem nazywamy spójny graf acykliczny.
Def. Lasem nazywamy graf acykliczny.
Def. Promieniem grafu nazywamy liczbę 
Def. 
jest wierzchołkiem centralnym w 
Twierdzenia
Tw. Następujące warunki są równoważne:
1) 
jest drzewem.
2) 
droga) i jest to droga prosta (
”istnieje dokładnie jeden”).
3) G jest spójny i 
.
4) G jest acykliczny i 
.
5) G jest spójny i 
jest niespójny.
6) G jest acykliczny i 
posiada cykl i to dokładnie jeden.
Tw. Jordana
Dla każdego drzewa T centrum T składa się z jednego wierzchołka, lub z dwóch wierzchołków sąsiadujących ze sobą.
Grafy dwudzielne
Definicje
Def. Graf dwudzielny 
Def. Graf pełny dwudzielny 
- dwudzielny i 
. Oznaczamy go przez 
, gdzie 
Graf pełny dwudzielny.
Twierdzenia
Tw. W grafie dwudzielnym każdy cykl ma parzystą długość.
Grafy eulerowskie
Definicje
Def. Cykl Eulera w grafie G jest to cykl przechodzący przez wszystkie wierzchołki i krawędzie grafu G. G jest grafem Eulera 
G ma cykl Eulera.
Twierdzenia
Tw. Jeśli w grafie G stopień każdego wierzchołka jest większy lub równy 2, to graf ten ma cykl.
Tw. Eulera (1736)
Graf G ma cykl Eulera 
G jest spójny, 
i stopień każdego wierzchołka jest liczbą parzystą.
Grafy hamiltonowskie
Definicje
Def. Cyklem Hamiltona w grafie G nazywamy każdy cykl rozpinający. G jest grafem Hamiltona 
G ma cykl Hamiltona.
Def.
-grafy.
Def. 
Def. k-domknięciem grafu G nazywamy minimalny (ze względu na zbiór krawędzi) nadgraf H rozpięty nad G, taki, że 
. Oznaczamy je 
.
Def. 
to graf, w którym wierzchołki 
są połączone krawędzią wtedy i tylko wtedy, kiedy długość u-v drogi w G nie przekracza n.
Twierdzenia
Tw. G - graf Hamiltona 
(liczba składowych w G-S nie przekracza 
.
Tw. Jeśli graf G jest dwuspójny i nie zawiera 
podgrafu, to G ma cykl Hamiltona.
Tw. Diraca (1952)
Jeżeli graf G ma 
wierzchołków oraz 
, to G ma cykl Hamiltona.
Tw. Ore (1960)
Jeżeli graf G ma 
wierzchołków oraz 
, to G ma cykl Hamiltona.
Tw. Pòsa (1962)
Jeżeli w grafie G o p wierzchołkach 
zachodzi 
, a gdy p nieparzyste 
, to G ma cykl Hamiltona.
Tw. Bondy, Chvatal (1976)
Jeśli w grafie G o 
wierzchołkach 
, to G ma cykl Hamiltona.
Tw. Sekanina (1968)
Jeżeli graf G o 
wierzchołkach jest spójny, to 
ma cykl Hamiltona.
Tw. Erdös, Chvatal
Jeżeli w grafie G o 
wierzchołkach 
, to G ma cykl Hamiltona.
Faktory
Definicje
Def. k-faktorem w grafie G nazywamy każdy k-regularny podgraf rozpinający.
Def. k-faktoryzacja grafu G to zbiór krawędziowo rozłącznych k-faktorów 
, takich, że 
.
Twierdzenia
Tw. Tutte (1947)
G ma jeden faktor 
liczba składowych o nieparzystych ilościach wierzchołków w grafie G-S nie przekracza 
Tw. 
ma 1-faktoryzację 
n jest parzyste.
Tw. 
ma 2-faktoryzację taką, że każdy 2-faktor jest cyklem Hamiltona.
Pokrycia i niezależność
Definicje
Def. 
1) S jest zbiorem niezależnych wierzchołków 
2) F jest zbiorem niezależnych krawędzi 
3) S jest zbiorem pokrywających wierzchołków 
4) F jest zbiorem pokrywających krawędzi 
- najmniejsza liczność pokrywającego zbioru wierzchołków w G
- najmniejsza liczność pokrywającego zbioru krawędzi w G
- największa liczność niezależnego zbioru wierzchołków w G
- największa liczność niezależnego zbioru krawędzi w G
Twierdzenia
Tw. Gallai
Kolorowanie
Definicje
Def. Graf jest k-kolorowalny 
- zbiór wierzchołków można podzielić na k podzbiorów w ten sposób, aby żadne dwa wierzchołki należące do jednego podzbioru nie były połączone krawędzią.
Def. Najmniejsze k takie, że G jest k-kolorowalny nazywamy liczbą chromatyczną grafu G i oznaczamy 
.
Def. Graf jest k-kolorowalny krawędziowo jeżeli jego krawędzie można pokolorować k kolorami tak, żeby żadna para krawędzi sąsiednich nie miala tego samego koloru.
Def. Najmniejsze k takie, że G jest k-kolorowalny krawędziowo nazywamy indeksem chromatycznym grafu G i oznaczamy 
.
Twierdzenia
Tw. Grafy dwudzielne są dwukolorowalne.
Tw. W grafie G o p wierzchołkach zachodzi nierówność:
Tw. Szekerés, Wilf (1968)
Jeżeli H są indukowanymi podgrafami G, to zachodzi nierówność:
Tw. Brooks (1941)
Jeżeli G jest spójnym grafem prostym, nie będącym grafem pełnym, i jeśli największy stopień wierzchołka grafu G wynosi 
(gdzie 
), to graf G jest 
-kolorowalny.
Tw. Appel, Haken (1976)
Każdy graf planarny jest 4-kolorowalny.
Tw. Визинг (1968)
.
Grafy planarne
Definicje
Def. G jest grafem planarnym 
istnieje taka reprezentacja graficzna grafu G na płaszczyźnie, że łuki reprezentujące krawędzie nie mają punktów wspólnych poza wierzchołkami w których się łączą.
Twierdzenia
Tw. Kuratowski (1930)
G jest grafem planarnym 
G nie zawiera podgrafu homeomorficznego z 
, ani 
.
Tw. Euler (1750)
Niech G będzie rysunkiem płaskim spójnego grafu płaskiego i niech n, m i f oznaczają odpowiednio liczbę wierzchołków, krawędzi i ścian grafu G. Wtedy:
Wniosek
Jeśli G jest spójnym planarnym grafem prostym, mającym n wierzchołków (gdzie 
) i m krawędzi, to 
. Jeśli ponadto graf G nie zawiera 
, to 
Lemat
G - planarny 
Tw. Tutte (1956)
G - planarny i 
G ma cykl Hamiltona.
Turnieje
Definicje
Def. Turniejem nazywamy graf zorientowany otrzymany z grafu pełnego 
przez nadanie każdej krawędzi jednej z dwóch możliwych orientacji w dowolny sposób.
Def. T jest mocno spójnym turniejem 
w T u-v droga).
Def. 
- półstopień wejściowy.
- półstopień wyjściowy.
Twierdzenia
Tw. Landau (1955)
W każdym turnieju odległość od wierzchołka o maksymalnym wyniku do każdego innego wierzchołka wynosi 1 albo 2.
Tw. Rédei (1934)
Każdy turniej ma drogę Hamiltona.
Tw. Moser (1966)
Jeżeli T jest mocno spójnym turniejem i 
, to 
istnieje w T cykl długości i.
Twierdzenie Ramsey'a
Def. Liczba Ramsey'a R(s,t) jest to najmniejsze n takie, że dla każdego podziału zbioru krawędzi grafu 
na czerwone i zielone istnieje czerwony podgraf 
lub zielony 
.
Tw. Ramsey (1929)
Dla każdych 
:
1) 
2) 
Matroidy
Def. Matroidem nazywamy parę M=(E,J) (E - zbiór skończony, 
, J - rodzina zbiorów niezaleznych) o własnościach:
1) 
2) 
3) 
DODATKI
Izomorficzne postacie grafu Petersena.