MATEMATYKA DYSKRETNA
Skrypt pisany na podstawie wykładu prowadzonego przez
Dr. T. Traczyka
MATEMATYKA DYSKRETNA
Skrypt pisany na podstawie wykładu prowadzonego przez
Dr. T. Traczyka
Wiadomości wstępne
Tw. O indukcji matematycznej
n
n
n
k
k
n
k
n
N
n
0
0
0
0
1
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ę
E
V ,
gdzie
V
– zbiór (skończony) niepusty,
2
:
2
2
A
V
A
A
V
V
P
E
V
-
zbiór wierzchołków
E - zbiór krawędzi
Def.
Stopniem wierzchołka v w grafie
E
V
G
,
jest liczba
E
uv
u
E
v
u
V
u
v
G
:
,
:
deg
Def.
0
deg
v
wtedy v
– izolowany
1
deg
v
wtedy v
– liść
Def.
E
V
G
,
,
V
v
u
,
u-v
drogą w G nazywamy ciąg
k
v
v
v
,...,
,
1
0
gdzie
1)
v
v
u
v
k
,
0
2)
E
v
v
k
i
i
i
1
,
1
,...,
1
,
0
3)
1
1
,
,
1
,
0
j
j
i
i
v
v
v
v
j
i
k
j
i
Liczbę k nazywamy długością drogi. Jeżeli ponadto
j
i
v
v
j
i
j
i
,
to
k
v
v ,...,
0
jest drogą prostą.
Def. G
jest grafem spójnym
V
v
u,
u-v droga w
G
Def.
Jeżeli w drodze
k
v
v
v
,...,
,
1
0
k
v
v
0
to drogę nazywamy cyklem. Jeżeli w
drodze prostej
k
v
v
v
,...,
,
1
0
0
v sąsiaduje z
k
v , to drogę nazywamy cyklem
prostym.
Def.
Dopełnieniem grafu
E
V
G
,
nazywamy graf
E
V
P
V
G
/
,
'
2
. 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.
F
W
H
,
jest pograłem
E
W
P
F
V
W
F
W
H
E
V
G
2
,
,
Graf i jego podgraf.
Def. H jest nadgrafem G
G jest podgrafem H.
Def.
F
W
H
,
jest pograłem indukowanym
E
W
P
W
H
V
W
E
V
G
2
,
,
Graf i jego podgraf indukowany.
Def. H
jest podgrafem rozpinającym w
G
V
H
V
G
Graf i jego podgraf rozpinający.
Def. Najmniejszy
stopień wierzchołka w grafie G -
G
V
v
v
G
:
deg
min
Def.
Największy stopień wierzchołka w grafie G -
G
V
v
v
G
:
deg
max
Def. G jest r-regularny
r
v
V
v
deg
Graf 4-
regularny o 7 wierzchołkach.
Def.
n
K - graf pełny o n wierzchołkach -
n
P
n
K
n
,...,
1
,
,...,
1
2
Grafy
pełne.
Def.
1
1
1
, E
V
G
i
2
2
2
, E
V
G
są izomorficzne
2
1
1
2
1
1
"
"
1
,
:
E
v
f
u
f
E
uv
V
v
u
V
V
f
na
.
Izomorfizm grafów oznacza się
2
1
G
G
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
5
K i
5
K
L
.
Twierdzenia
Lemat
O uściskach dłoni.
V
v
G
v
deg
2
Lemat
2
deg v
V
v
w G istnieje pewien cykl (prosty).
Spójność
Definicje
Def. Graf G jest k-
spójny (wierzchołkowo)
S
G
k
S
V
S
k
V
spójny). Spójnością grafu G nazywamy największe k takie, ze G jest k-spójny i
oznaczamy
G
.
Def. Graf G jest l-
spójny krawędziowo
F
G
l
F
E
F
l
E
spójny).
Spójnością krawędziową grafu G nazywamy największe l takie, ze G jest l-
spójny krawędziowo i oznaczamy
G
Def.
E
xy
S
y
V
x
S
N
:
-
ilość sąsiadów podzbioru S
Def.
E
V
G
,
i
E
xy
V
y
x
,
. Zbiór
V
S
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ść:
2
1
k
n
k
n
m
k
n
Tw
. Whitney’a
G
G
G
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 X niezależnych krawędzi
S
N
S
V
S
.
Powyższy warunek nosi nazwę warunku Halla.
Tw. Mengera (1927)
Jeśli dla każdego u-v zbioru rozdzielającego S mamy
k
S
, to w G istnieje k
rozłącznych u-v dróg.
Tw
. Këniga – Halla
W każdym grafie dwudzielnym
G
G
0
1
.
Drzewa
Definicje
Def.
Drzewem nazywamy spójny graf acykliczny.
Def. Lasem nazywamy graf acykliczny.
Def.
Promieniem grafu nazywamy liczbę
v
u
dist
G
r
V
v
V
u
,
max
min
Def.
V
v
jest wierzchołkiem centralnym w
v
u
dist
G
r
G
V
u
,
max
Twierdzenia
Tw.
Następujące warunki są równoważne:
1)
E
V
G
,
jest drzewem.
2)
v
u
V
v
u
!
,
droga) i jest to droga prosta (
!
”istnieje dokładnie jeden”).
3) G
jest spójny i
1
E
V
.
4) G jest acykliczny i
1
E
V
.
5) G
jest spójny i
e
G
E
e
jest niespójny.
6) G jest acykliczny i
uv
G
E
uv
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
V
V
V
V
V
V
V
V
2
1
2
1
2
1
,
2
1
V
e
V
e
E
e
Def.
Graf pełny dwudzielny
G
- dwudzielny i
E
v
v
V
v
V
v
2
1
2
2
1
1
,
.
Oznaczamy go przez
n
m
K
.
, gdzie
2
1
,
V
n
V
m
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,
1
V
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.
n
v
V
v
D
n
deg
:
Def. k-
domknięciem grafu G nazywamy minimalny (ze względu na zbiór krawędzi)
nadgraf H
rozpięty nad G, taki, że
k
v
u
H
E
uv
H
V
v
u
H
H
deg
deg
,
. Oznaczamy je
G
C
k
.
Def.
n
G to graf, w którym wierzchołki
G
V
v
u
,
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
V
S
(liczba składowych w G-S nie przekracza
S
.
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
3
n
wierzchołków oraz
2
deg
n
v
V
v
, to G ma cykl
Hamiltona.
Tw. Ore (1960)
Jeżeli graf G ma
3
n
wierzchołków oraz
n
v
u
V
v
u
deg
deg
,
, to G ma cykl
Hamiltona.
Tw.
Pòsa (1962)
Jeżeli w grafie G o p wierzchołkach
2
1
p
n
n
zachodzi
n
D
n
, a gdy p
nieparzyste
2
1
2
1
p
D
p
, to G ma cykl Hamiltona.
Tw. Bondy, Chvatal (1976)
Jeśli w grafie G o
3
p
wierzchołkach
p
p
K
G
C
, to G ma cykl Hamiltona.
Tw. Sekanina (1968)
Jeżeli graf G o
3
p
wierzchołkach jest spójny, to
3
G ma cykl Hamiltona.
Tw
. Erdös, Chvatal
Jeżeli w grafie G o
3
p
wierzchołkach
G
G
0
, 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
s
i
E
V
G
i
i
,...,
1
,
,
takich, że
s
i
i
E
E
1
.
Twierdzenia
Tw. Tutte (1947)
G ma jeden faktor
V
S
liczba składowych o nieparzystych ilościach
wierzchołków w grafie G-S nie przekracza
S
Tw.
n
K ma 1-faktoryzację
n jest parzyste.
Tw.
1
2
n
K
ma 2-
faktoryzację taką, że każdy 2-faktor jest cyklem Hamiltona.
Pokrycia i niezależność
Definicje
Def.
E
F
V
S
E
V
G
,
,
,
1) S jest zbiorem ni
ezależnych wierzchołków
E
S
P
2
2) F
jest zbiorem niezależnych krawędzi
d
e
d
e
E
d
e,
3) S
jest zbiorem pokrywających wierzchołków
S
e
E
e
4) F
jest zbiorem pokrywających krawędzi
V
e
F
e
G
0
-
najmniejsza liczność pokrywającego zbioru wierzchołków w G
G
1
-
najmniejsza liczność pokrywającego zbioru krawędzi w G
G
0
-
największa liczność niezależnego zbioru wierzchołków w G
G
1
-
największa liczność niezależnego zbioru krawędzi w G
Twierdzenia
Tw. Gallai
G
G
V
G
G
G
1
1
0
0
0
Kolorowanie
Definicje
Def. Graf jest k-kolorowalny
E
i
f
P
i
k
V
f
1
2
,...,
2
,
1
:
-
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
G
.
Def. Graf jest k-kolorowal
ny 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
G
'
.
Twierdzenia
Tw.
Grafy dwudzielne są dwukolorowalne.
Tw. W grafie G o p
wierzchołkach zachodzi nierówność:
1
0
0
p
G
p
Tw
. Szekerés, Wilf (1968)
Jeżeli H są indukowanymi podgrafami G, to zachodzi nierówność:
1
max
H
G
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
3
), to graf G jest
-kolorowalny.
Tw. Appel, Haken (1976)
Każdy graf planarny jest 4-kolorowalny.
Tw
. Визинг (1968)
1
'
G
G
G
G
.
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
5
K , ani
3
,
3
K
.
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:
2
f
m
n
Wniosek
Jeśli G jest spójnym planarnym grafem prostym, mającym n wierzchołków (gdzie
3
n
) i m
krawędzi, to
6
3
n
m
. Jeśli ponadto graf G nie zawiera
3
K , to
4
2
n
m
Lemat
G
– planarny
5
G
Tw. Tutte (1956)
G
– planarny i
4
G
G ma cykl Hamiltona.
Turnieje
Definicje
Def.
Turniejem nazywamy graf zorientowany otrzymany z grafu pełnego
n
K przez
nadanie każdej krawędzi jednej z dwóch możliwych orientacji w dowolny
sposób.
Def. T
jest mocno spójnym turniejem
T
V
v
u,
w T u-v droga).
Def.
E
v
u
V
u
v
)
,
(
:
deg
-
półstopień wejściowy.
E
u
v
V
u
v
)
,
(
:
deg
-
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
3
p
T
V
, to
p
i
,...,
4
,
3
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
n
K na czerwone i zielone istnieje czerwony podgraf
s
K
lub zielony
t
K .
Tw. Ramsey (1929)
Dla każdych
2
,
2
t
s
:
1)
1
,
,
1
,
t
s
R
t
s
R
t
s
R
2)
1
2
,
s
t
s
t
s
R
Matroidy
Def.
Matroidem nazywamy parę M=(E,J) (E – zbiór skończony,
E
J
2
, J
– rodzina
zbiorów niezaleznych) o własnościach:
1)
J
J
2)
J
Y
X
Y
J
X
Y
X
E
2
,
3)
J
e
Y
Y
e
X
e
Y
X
J
Y
X
1
,
DODATKI
Izomorficzne postacie grafu Petersena.