WYKŁAD 1.
Grafy są wokół nas.
Pojęcia wstępne.
WYKŁAD 1.
Grafy są wokół nas.
Pojęcia wstępne.
Przykład 1. ZOO
• Budujemy domowe zoo mając do
dyspozycji kozę, lwa, wilka, słonia,
jastrzębia, zająca i mysz.
• Cel: jak najmniej klatek,
zapewniając bezpieczeństwo
wszystkich zwierząt.
k
l
s
w
j
z
m
l
s
w
j
k
z
m
Przykład 2. Podział na
pary
• Dzielimy grupę 10 osób na pary.
• Każdy chce być w parze ze swoim
znajomym.
Graf
Petersena
A
B
C
D
E
F
G
H
I
J
Graf
Petersena
A
B
C
D
E
F
G
H
I
J
A
B
A
B
Przykład 3. Muzeum
• Zwiedzamy muzeum będące
labiryntem korytarzy, w którym
obrazy wiszą po obu stronach.
• Cel: przejść każdy korytarz 2 razy
i wrócić do wyjścia.
PLAN MUZEUM
a
b
c
d
e
a
b
c
d
e
Przykład 4.
Trzy domki i trzy
studnie
• Mieszkańcy trzech domków chcą
korzystać z trzech studni, ale tak
by nigdy nie musieli spotkać się w
drodze do nich.
• Czy jest to możliwe?
D1
D2
D3
S1
S2
S3
?
?
Pojęcie grafu
• Graf to para zbiorów
G=(V,E),
gdzie
• V
to skończony zbiór (
wierzchołków
)
• E
to zbiór 2-elementowych
podzbiorów zbioru V (
krawędzi
).
2
V
E
•Inaczej, graf to relacja symetryczna i antyzwrotna.
•Jeszcze inaczej: symetryczna 0-1 macierz kwadratowa
z zerami na przekątnej.
Grafy puste i pełne.
Dopełnienia grafów.
Graf
pełny
n
V
2
V
E
E
V
V
G
2
,
n
n
K
N
n
K
Dopełnienie
grafu G:
Graf
pusty
Te same czy takie same?
a
b
c
d
G2
a
d
c
b
G3
a
b
c
d
G4
a
b
d
c
G5
a
b
d
e
G6
a
b
c
d
G1
Izomorfizm grafów
• Na przykład G1 jest izomorficzny z G2, bo
• f(a)=a, f(c)=c, f(b)=d, f(d)=b.
2
1
G
G
2
1
:
V
V
f
2
1
)
(
)
(
E
v
f
u
f
E
uv
• G1=G5, G2=G3, wszystkie grafy mają tę
samą strukturę – są
izomorficzne.
Automorfizmy
• Automorfizm
to izomorfizm grafu w siebie.
a
b
c
d
G1
• Na przykład f(a)=a, f(d)=d, f(c)=b,
f(b)=c to 1 z 8 automorfizmów grafu G1.
Samodopełnianie
• G nazywamy
samodopełniającym
, gdy jest izomorficzny ze
swoim dopełnieniem.
Na
przykład
Stopnie wierzchołków
Zachodzi wzór
)
(
2
)
(
G
e
v
d
V
v
G
Stopniem wierzchołka
v nazywamy liczbę
d
G
(v)=d(v)
krawędzi grafu zawierających
(incydentnych z) v.
gdzie e(G)=|
E|.
Ciąg stopni grafu
Ciąg stopni grafu
Uwaga
:
Nie każdy ciąg liczb
naturalnych jest ciągiem stopni grafu,
np. 4,4,3,2,1 lub 3,3,3,2,2.
V
v
G
v
d
)
(
• Δ(G)= Δ to największy stopień
wierzchołka w grafie,
• δ(G)=δ to najmniejszy stopień.
•
Graf jest
k-regularny
, gdy wszystkie
wierzchołki mają stopień k.
Podgrafy
• Indukowane
• Rozpięte
• Ani takie, ani takie
Podgrafy indukowane
• Podgraf
grafu G=(V,E)
indukowany
przez podzbiór wierzchołków W to
graf G[W]=(W,E’), gdzie E’ składa
się ze
wszystkich
krawędzi grafu G
o
obu
końcach w W.
Podgraf indukowany -
ilustracja
W={a,b,c}, G[W] – kolor
czerwony
a
b
c
Podgrafy rozpięte
• Rozpięty
podgraf grafu G to graf
G’=(
V
,E’), gdzie E’ jest
podzbiorem E.
Podgrafy
• Podgrafem
grafu G=(V,E) nazywamy
graf G’=(V’,E’), gdzie V’ jest
podzbiorem V, a E’ jest podzbiorem E.
Spójność
• Graf jest
spójny,
gdy dla każdego podziału
V na dwa rozłączne i niepuste podzbiory A
i B istnieje krawędź z A do B (graf jest w 1
„kawałku”).
Inaczej
2
2
:
,
B
A
E
B
A
B
A
V
Grafy niespójne
A
B
B1
B
2
Wierzchołek cięcia
• G-v=G[V-v]
• Wierzchołek v grafu spójnego G
nazywamy
wierzchołkiem cięcia
, gdy G-
v nie jest spójny.
• Inaczej, istnieje podział V na A i B, |A|, |
B|>1 :
v
B
A
2
2
B
A
E
Cykle
• Cykl
to 2-regularny graf spójny.
• Inaczej
: cykl to graf, którego
wierzchołki można ponumerować
v_1,...,v_n, tak, że pary {v_1, v_2},
{v_2,v_3},...,{v_(n-1),v_n}, {v_n,
v_1} są jego jedynymi krawędziami.
• Notacja
C_n,
dla
n=3,4,...
Cykle : ilustracja
C_3=K_3
C_4
C_5
Ścieżki
• Ścieżka
to graf spójny o 2
wierzchołkach stopnia 1, a
pozostałych o stopniu 2.
• Inaczej
: ścieżka to graf, którego
wierzchołki można ponumerować
v_1,...,v_n, tak, że pary {v_1, v_2},
{v_2,v_3},...,{v_(n-1),v_n}, są jego
jedynymi krawędziami.
• Notacja
P_n,
dla
n=1,2,...