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.

---