Jagiellonian University
Theoretical
Computer Science
Matematyka Dyskretna
(Zbiory, Logika)
WSB NLU
Edward Szczypka
szczypka@tcs.uj.edu.pl
2 Pa´zdziernik 2009
Edward Szczypka
1 / 31
Jagiellonian University
Theoretical
Computer Science
Matematyka Dyskretna
(Zbiory, Logika)
WSB NLU
Edward Szczypka
szczypka@tcs.uj.edu.pl
2 Pa´zdziernik 2009
Edward Szczypka
1 / 31
Jagiellonian University
Theoretical
Computer Science
Dzisiejszy wykład
relacje i kwantyfikatory,
Edward Szczypka
2 / 31
Jagiellonian University
Theoretical
Computer Science
spis
1
Relacje Dwuargumentowe
Relacje Wieloargumentowe
Relacje Jednoargumentowe
Predykaty
Kwantyfikatory
Kwantyfikatory
Zmienne
2
Edward Szczypka
3 / 31
Jagiellonian University
Theoretical
Computer Science
Relacje Dwuargumentowe
Dowolny podzbiór iloczynu kartezja ´nskiego (ustalonych zbiorów) nazywamy
relacj ˛
a
.
W j ˛ezyku naturalnym słowo relacja oznacza zale˙zno´s´c, powi ˛
azanie itp. Tutaj
sens jest podobny, ale formalnie po prostu wyliczamy wszystkie elementy, które
s ˛
a w relacji (zamiast opisywa´c, na czym owa relacja polega).
Najcz ˛e´sciej rozpatrujemy relacje dwuargumentowe.
Dla dwuargumentowej relacji R ⊆ X × Y , je´sli hx , y i ∈ R
to mówimy, ˙ze element x jest w relacji R z elementem y
cz ˛esto zamiast hx , y i ∈ R piszemy xRy.
Edward Szczypka
4 / 31
Jagiellonian University
Theoretical
Computer Science
Relacje Dwuargumentowe - przykłady
Przykład 1 dla zbiorów
X = {
kot, pies, rybka}
Y = {
woda, mleko, ko´s´c, trawa}
rozwa˙zmy relacj ˛e R ⊆ X × Y zdefiniowan ˛
a jako:
R = {(
kot, mleko), (pies, woda), (pies, ko´s´c), (rybka, woda)}
wtedy relacj ˛e R mo˙zna zdefiniowa´c jako lubi:
(
pies, woda) ∈ R oznacza, ˙ze pies lubi wod ˛e,
poniewa˙z (
rybka, mleko) /
∈ R wi ˛ec wnioskujemy, ˙ze rybka nie lubi mleka
Edward Szczypka
5 / 31
Jagiellonian University
Theoretical
Computer Science
Relacje Dwuargumentowe - przykłady II
Cz ˛esto jest tak, ˙ze X = Y , mówimy wtedy, ˙ze R ⊆ X × X jest relacj ˛
a binarn ˛
a na
zbiorze X .
Przykład 2 Na zbiorze liczb naturalnych N okre´slmy relacj ˛e:
R = {(x , y ) ∈ N × N : istnieje a ∈ N takie ˙ze xa = y}
Łatwo zauwa˙zy´c, ˙ze ta relacja definiuje nam podzielno´s´c, tzn. xRy oznacza, ˙ze y jest
podzielne przez x . np. (3, 12) ∈ R, (4, 8) ∈ R a (4, 6) /
∈ R.
Relacj ˛e podzielno´sci zwykle oznacza si ˛e pionow ˛
a kresk ˛
a, a zatem 3 | 9 oraz 3 - 8.
Zauwa˙z, ˙ze zgodnie z definicj ˛
a:
1 dzieli ka˙zd ˛
a liczb ˛e naturaln ˛
a: 1 | x , bo 1 · x = x ,
0 ka˙zda liczba dzieli 0: x | 0, bo x · 0 = 0.
Edward Szczypka
6 / 31
Jagiellonian University
Theoretical
Computer Science
Relacje Dwuargumentowe - przykłady III
Przykład 3 Podobnie mo˙zna okre´sli´c relacj ˛e porz ˛
adku ¬ na liczbach naturalnych:
R = {(x , y ) ∈ N × N : istniejea ∈ Ntakie ˙zex + a = y}
Wtedy 3 ¬ 12, 8 6¬ 4.
Oczywi´scie bardziej naturalnym jest pisanie 3 ¬ 12 zamiast (3, 12) ∈¬, ostatni napis
cho´c poprawny jest jednak mało czytelny.
Zadanie 4 Zdefiniuj relacj ˛e ¬ na zbiorze liczb rzeczywistych R.
Zadanie 5 Czy w podobny sposób mo˙zna zdefiniowa´c relacj ˛e porz ˛
adku na liczbach
wymiernych? Je´sli nie spróbuj zaproponowa´c inne rozwi ˛
azanie.
Edward Szczypka
7 / 31
Jagiellonian University
Theoretical
Computer Science
Relacje Wieloargumentowe - przykład IV
Jak sama nazwa wskazuje, w tych relacjach rozwa˙zamy wi ˛eksz ˛
a ilo´s´c argumentów,
jest to bardzo cz ˛esty przypadek w rzeczywistym ´swiecie (np bazy danych).
Przykład 6 Niech
S - oznacza zbiór sal,
T - oznacza zbiór terminów,
W - oznacza zbiór wykładowców,
G - oznacza zbiór grup,
wtedy zbiór H ⊆ S × T × W mo˙ze reprezentowa´c czwór argumentow ˛
a relacj ˛e
(
sala, terin, wykładoca, grupa) opisuj ˛
ac ˛
a harmonogram.
Je´sli na zbiór H nało˙zymy pewne restrykcje (np. terminy, pojemno´s´c sal itp.) problem
staje si ˛e niezwykle trudny do rozwi ˛
azania oraz zaprojektowania w postaci algorytmu.
Edward Szczypka
8 / 31
Jagiellonian University
Theoretical
Computer Science
Relacje Jednoargumentowe
Rozwa˙za si ˛e te˙z relacje jednoargumentowe.
Taka jednoargumentowa relacja w zbiorze X to nic innego jak podzbiór zbioru X .
Poniewa˙z podzbiory danego zbioru uto˙zsamili´smy z własno´sciami jego elementów, to
na relacje jednoargumentowe mo˙zemy patrze´c tak jak na własno´sci.
Przykład 7 W zbiorze liczb naturalnych N wyró˙znijmy podzbiór P liczb parzystych.
Wtedy a ∈ P oznacza, ˙ze a jest liczb ˛
a parzyst ˛
a. Zamiast a ∈ P pisze si ˛e te˙z cz ˛esto
P(a).
Przykład 8 Inn ˛
a tak ˛
a własno´sci ˛
a mo˙ze by´c:
{x ∈ N : x > 5}
tzn. własno´s´c bycia wi ˛ekszym od pi ˛eciu.
Edward Szczypka
9 / 31
Jagiellonian University
Theoretical
Computer Science
Relacje, predykaty i wyra˙zenia Booleñowskie
Niech
R ∈ A
1
× A
2
× . . . × A
n
b ˛edzie n-argumentow ˛
a relacj ˛
a,
a krotka ha
1
,
a
2
, . . .
a
n
i nale˙zy do produktu A
1
× A
2
× . . . × A
n
,
Wtedy wyra˙zenie R(a
1
,
a
2
, . . . ,
a
n
)
:
jest prawdziwe gdy ha
1
,
a
2
, . . . ,
a
n
i ∈ R
jest fałszywe gdy ha
1
,
a
2
, . . . ,
a
n
i /
∈ R
A zatem na relacje mo˙zemy patrze´c jak na własno´sci, (inaczej:
predykaty
). Poniewa˙z
wyra˙zenie takie jak R(a
1
,
a
2
, . . . ,
a
n
)
dla konkretnych elementów a
1
,
a
2
, . . . ,
a
n
ma
zawsze okre´slon ˛
a warto´s´c
PRAWDY lub FAŁSZU (tzw. warto´s´c Booleñowsk ˛
a), to
cz ˛esto mówi si ˛e, ˙ze jest to wyra˙zenie Booleñowskie.
Edward Szczypka
10 / 31
Jagiellonian University
Theoretical
Computer Science
Predykaty
Rozwa˙zaj ˛
ac jak ˛
a´s własno´s´c (predykat) R musimy zawsze poda´c:
ile ma argumentów
elementów jakiego zbioru dotyczy (tzw. dziedzin ˛e predykatu R).
Czasem te rzeczy znane s ˛
a przez domniemanie, ale w programach zwykle
specyfikujemy ich typ, tzn. liczb ˛e argumentów i dziedzin ˛e.
Dla danej własno´sci P, np. jednoargumentowej, mo˙zemy utworzy´c wyra˙zenie P(x ),
gdzie x nie jest konkretnym elementem jakiego´s zbioru, ale zmienn ˛
a przebiegaj ˛
ac ˛
a
ten zbiór:
wyra˙zenie P(x ) nie jest ani prawdziwe ani fałszywe
staje si ˛e nim dopiero takim, gdy za zmienn ˛
a x podstawimy konkretny element
dziedziny predykatu P
Edward Szczypka
11 / 31
Jagiellonian University
Theoretical
Computer Science
Predykaty II
Podobnie dla predykatu dwuargumentowego S nad liczbami naturalnymi oraz
zmiennych x, y mo˙zemy utworzy´c wyra˙zenia
S(x , y )
S(x , 6)
S(2, y )
S(2, 6)
z których tylko ostatnie przyjmuje konkretn ˛
a warto´s´c Booleowsk ˛
a (prawdziwo´s´c).
Pierwsze trzy s ˛
a tylko wyra˙zeniami Booleowskimi, ale bez konkretnej oceny
prawdziwo´sciowej.
Zauwa˙zmy, ˙ze S(x , y ) jest predykatem binarnym, ale S(2, y ) jak i S(x , 6) s ˛
a
predykatami jednoargumentowymi. Np., gdy S jest relacj ˛
a podzielno´sci, to:
S(2, y ) jest własno´sci ˛
a bycia liczb ˛
a parzyst ˛
a
S(x , 6) jest własno´sci ˛
a dzielenia liczby 6 z odpowiadaj ˛
acym jej zbiorem
{1, 2, 3, 6}
Edward Szczypka
12 / 31
Jagiellonian University
Theoretical
Computer Science
Kwantyfikatory
W praktyce matematycznej, a tak˙ze informatycznej wa˙zne s ˛
a wyra˙zenia postaci:
ka˙zdy przedmiot ma własno´s´c P
jaki´s przedmiot ma własno´s´c P
Pierwsze z tych wyra˙ze ´n mo˙ze gwarantowa´c np., ˙ze przebieg jakiej´s p ˛etli zako ´nczy
si ˛e sukcesem ˝
O np. instrukcje zostan ˛
a wykonane dla całych zasobów w bazie danych.
Drugie wyra˙zenie, mo˙ze gwarantowa´c np. ˙ze p ˛etla typu WHILE ...DO ... nie
b ˛edzie wykonywana w niesko ´nczono´s´c ˝
O istnieje bowiem przedmiot, który nie spełnia
warunku sprawdzanego w p ˛etli.
Symbolicznie zapisuje si ˛e takie wyra˙zenia z u˙zyciem kwantyfikatorów:
wyra˙zenie
zapis
kwantyfikator
ka˙zdy przedmiot ma własno´s´c P
∀xP(x)
∀ du˙zy, uniwersalny
jaki´s przedmiot ma własno´s´c P(x )
∃P(x)
mały, egzystencjalny
Edward Szczypka
13 / 31
Jagiellonian University
Theoretical
Computer Science
Kwantyfikatory u˙zyciu
Bardzo cz ˛esto u˙zywaj ˛
ac kwantyfikatorów zapisuje si ˛e dziedzin ˛e dla odpowiednich
zmiennych.
Np. ∀x ∈ R : x
2
0
lub ∃x ∈ R : x
2
=
2.
Kwantyfikatorów mo˙zna u˙zywa´c do tworzenia bardziej skomplikowanych wy- ra˙ze ´n.
Przykład 9 Predykaty a zadnia
Wyra˙zenie
jest
y
2
>
3
predykatem a nie jest zdaniem logicznym
∃y ∈ R : y
2
<
3
zdaniem(prawdziwym)
∀y ∈ R : y < 0
zdaniem(fasyzwzm)
∀x ∈ R : x < y
predykatem jednoargumentowym
∀y ∈ R∃x ∈ R : x ¬ y
zdaniem prawdziwym
Edward Szczypka
14 / 31
Jagiellonian University
Theoretical
Computer Science
Zmienne wolne i zwi ˛
azane
Zmienne wolne i zwi ˛
azane:
w wyra˙zeniu P(x ) zmienna x jest wolna
w wyra˙zeniach ∀xP(x ) oraz ∃xP(x ) zmienna x jest zwi ˛
azana
w wyra˙zeniu ∀xP(x , y ) zmienna x jest zwi ˛
azana, a zmienna y wolna
Aby wyra˙zenie było zdaniem logicznym (a zatem prawdziwe lub fałszywe) nie mo˙ze
zawiera´c zmiennych wolnych.
Je´sli s ˛
a zmienne wolne to wyra˙zenie takie nadal jest predykatem (o liczbie
argumentów równej liczbie zmiennych wolnych)
Edward Szczypka
15 / 31
Jagiellonian University
Theoretical
Computer Science
Fałszywo ´s ´c wyra˙ze ´
n skwantyfikowanych
Kiedy zdania z kwantyfikatorami s ˛
a fałszywe:
zdanie ∀xP(x ) jest fałszywe, gdy dla pewnego x nie zachodzi P(x )
zdanie ∃xP(x ) jest fałszywe, gdy dla ˙zadnego x nie zachodzi P(x ), czyli gdy dla
ka˙zdego x zachodzi 6 P(x )
Innymi słowy mamy (prawa De Morgana dla rachunku predykatów):
∀xP(x) ↔ ∃x¬P(x)
∃xP(x) ⇔ ∀x¬P(x)
Przykład 10
zdanie ∀x ∈ R : x > 0 jest fałszywe, gdy˙z ∃x ∈ R :6 (x > 0), tzn. ∃x ∈ R : x ¬ 0;
wystarczy np. wzi ˛
a´c x = −1,
zdanie ∃x ∈ R : x > 0 jest prawdziwe; wystarczy np. wzi ˛
a´c x = 1
zdanie ∃x ∈ R : x
2
0 jest prawdziwe; istotnie, kwadrat dowolnej liczby
rzeczywistej jest wi ˛ekszy lub równy 0
zdanie ∃x ∈ R : x
2
<
0 jest fałszywe; bo jego negacja (zdanie poprzednie) jest
prawdziwe
Edward Szczypka
16 / 31
Jagiellonian University
Theoretical
Computer Science
Kilka praw
Zadanie 10 Uzasadnij, ˙ze:
∀x(P(x) ∧ Q(x)) ↔ (∀xP(x) ∧ ∀xQ(x)),
∃x(P(x) ∧ Q(x)) → (∃xP(x) ∧ ∃xQ(x)),
∀x(P(x) ∨ Q(x)) ← (∀xP(x) ∨ ∀xQ(x)),
∃x(P(x) ∨ Q(x)) ↔ (∃xP(x) ∨ ∃xQ(x)),
∀x(P(x) → Q(x)) → (∀xP(x) ∧ ∀xQ(x)),
∀x∀yR(x, y ) ↔ ∀y ∀xR(x, y ),
∀x∃yR(x, y ) ↔ ∃y ∃xR(x, y ),
∃x∀yR(x, y ) → ∀y ∃xR(x, y ),
Poka˙z, ˙ze tam gdzie wymieniono wył ˛
acznie implikacje, nie zachodz ˛
a równowa˙zno´sci.
Edward Szczypka
17 / 31
Jagiellonian University
Theoretical
Computer Science
spis
1
2
Scie˙zki
Osigalno´s´c
Relacje Przechodnie
Odwrotno´s´c relacji
Własno´sci relacji
Grafy nieskierowane
Pełny, Indukowany
Stopie ´n wierzchołka
Edward Szczypka
18 / 31
Jagiellonian University
Theoretical
Computer Science
Definicja
Graf
to intuicyjnie zbiór wierzchołków (punktów, w ˛ezłów) poł ˛
aczonych kraw ˛edziami.
Formalnie graf to struktura G = hV , E i, gdzie
V jest zbiorem wierzchołków
E jest zbiorem kraw ˛edzi
W grafach skierowanych kraw ˛ed´z to para wierzchołków (v , w ) ∈ V × V . A zatem
E ⊆ V × V , czyli E jest dowoln ˛
a relacj ˛
a binarn ˛
a na zbiorze wierzchołków V W
praktyce grafy najcz ˛e´sciej przedstawia si ˛e na rysunkach, na których kraw ˛ed´z (v , w )
zaznacza si ˛e strzałk ˛
a v → w
Edward Szczypka
19 / 31
Jagiellonian University
Theoretical
Computer Science
Grafy s ˛
a u˙zyteczne przy opisywaniu wielu zjawisk, np.:
sie´c dróg pomi ˛edzy miastami
architektura sieci komputerowej
powi ˛
azania kapitałowe mi ˛edzy firmami
poł ˛
aczenia lotnicze mi ˛edzy miastami
reprezentacja danych w programach
Elementy zbioru V (czyli wierzchołki grafu) reprezentuj ˛
a wtedy obiekty, które
opisujemy, a elementy zbioru E (czyli kraw ˛edzie grafu) ˝
O powi ˛
azania mi ˛edzy
tymi obiektami.
Edward Szczypka
20 / 31
Jagiellonian University
Theoretical
Computer Science
Zliczanie grafów skierowanych
Graf skierowany o wierzchołkach ze zbioru V to dowolna relacja dwuargumentowa na
zbiorze V . A zatem, gdy |V | = n to liczba takich grafów jest liczb ˛
a podzbiorów zbioru
n
2
elementowego, czyli
2
n
2
.
Cz ˛esto rozwa˙za si ˛e grafy bez p ˛etelek, tzn. zakłada si ˛e, ˙ze relacja E jest
przeciwzwrotna
:
∀v (v , v ) /
∈ E
Liczba takich relacji to liczba podzbiorów zbioru V
2
\{(v , v ) : v ∈ V } czyli
2
n
2
− n
Zadanie 1 Ile jest grafów skierowanych, w których ka˙zdy wierzchołek ma p ˛etelk˛e?
Innymi słowy, ile jest zwrotnych relacji binarnych, tzn. relacji E spełniaj ˛
acych:
∀(v , v ) ∈ E
Edward Szczypka
21 / 31
Jagiellonian University
Theoretical
Computer Science
Droga w grafie skierowanym
Droga w grafie skierowanym to ci ˛
ag wierzchołków poł ˛
aczonych kraw ˛edziami:
v
1
→ v
2
→ v
3
→ . . . → v
n+1
tzn. (v
i
,
v
i+1
) ∈
E dla wszystkich i = 1, 2, . . . , n.
Długo´s´c takiej drogi to liczba u˙zytych kraw ˛edzi - tu jest to n.
Nie zakładamy, ˙ze wierzchołki wyst ˛epuj ˛
ace na tej drodze s ˛
a ró˙zne.
Je´sli pocz ˛
atek i koniec drogi to ten sam wierzchołek, tzn. v
n+1
=
v 1,mówimy, ˙ze
jest to droga zamkni ˛eta lub cykl
Mówimy, ˙ze wierzchołek y jest osi ˛
agalny z wierzchołka x, je´sli istnieje droga
x = v
1
→ v
2
→ v
3
→ . . . → v
n
=
y
zaczynaj ˛
aca si ˛e w x i ko ´ncz ˛
aca w y
Edward Szczypka
22 / 31
Jagiellonian University
Theoretical
Computer Science
Osi ˛
agalno ´s ´c i składanie relacji
Jak otrzyma´c relacj ˛e osi ˛
agalno´sci w gra?e z samej relacji E ? Niech
T = {(x , y ) ∈ V × V : y
jest osi ˛
agalny z x}.
ka˙zdy punkt jest osi ˛
agalny z samego siebie, poniewa˙z nie zakładali´smy ˙ze droga
musi mie´c niezerow ˛
a długo´s´c
je´sli xEy to y jest osi ˛
agalny z x , tzn. xTy
je´sli xTy oraz yEz, to równie˙z xTz
Dla relacji E , F ⊆ X × X okre´slamy zło˙zenie E ◦ F jako relacj ˛e:
E ◦ F = {(x , z) : ∃yxEy ∧ yFz}
Przykład 2 Je´sli E i F s ˛
a dwoma grafami, np. reprezentuj ˛
acymi odpowiednio sie´c po-
ł ˛
acze ´n lotniczych i kolejowych, to
E ◦ F składa si ˛e z par miast takich, ˙ze z pierwszego z nich mo˙zna si ˛e dosta´c do
drugiego lec ˛
ac (koniecznie) najpierw samolotem, a potem (przesiadaj ˛
ac si ˛e w
jakim´s mie´scie) jad ˛
ac poci ˛
agiem
F ◦ E składa si ˛e natomiast z par miast takich, ˙ze z pierwszego z nich mo˙zna si ˛e
dosta´c do drugiego najpierw jad ˛
ac (koniecznie) poci ˛
agiem, a potem
(przesiadaj ˛
ac si ˛e w jakim´s mie´scie) lec ˛
ac (koniecznie) samolotem
Edward Szczypka
23 / 31
Jagiellonian University
Theoretical
Computer Science
Osi ˛
agalno ´s ´c i składanie relacji II
Ogólnie w grafie (skierowanym) G = hV , E i zło˙zenie E ◦ E reprezentuje wierzchołki
poł ˛
aczone drog ˛
a o długo´sci 2.
Chc ˛
ac wi ˛ec opisa´c pary osi ˛
agalne z co najwy˙zej jedn ˛
a przesiadk ˛
a, musimy rozwa˙zy´c
sum ˛e
∆ ∪
E ∪ (E ◦ E )
gdzie zwyczajowo ∆ oznacza najmniejsz ˛
a relacj ˛e zwrotn ˛
a na rozwa˙zanym zbiorze,
tzn. tu δ = {(v , v ) : v ∈ V } Podobnie zło˙zenie E ◦ E ◦ E reprezentuje wierzchołki
poł ˛
aczone drog ˛
a o długo´sci 3, a suma zło˙ze ´n
E ∪ (E ◦ E ) ∪ (E ◦ E ◦ E )
opisuje pary wierzchołków poł ˛
aczone drog ˛
a o długo´sci co najwy˙zej 3, tzn. osi ˛
agalnych
z co najwy˙zej dwiema przesiadkami. Ogólnie, niesko ´nczona suma
T (E ) = ∆ ∪ E ∪ (E ◦ E ) ∪ (E ◦ E ◦ E ) ∪ . . .
opisuje pary wierzchołków poł ˛
aczone jak ˛
akolwiek drog ˛
a, a zatem jest to rozwa˙zana
relacja osi ˛
agalno´sci.
Edward Szczypka
24 / 31
Jagiellonian University
Theoretical
Computer Science
Realcje Przechodnie
Relacja binarna E na zbiorze X jest przechodnia je´sli
∀x, y , zxEy ∧ yEz → xEz
Oznacza to, ˙ze je´sli z x do z mo˙zna si ˛e dosta´c z przesiadk ˛
a, to mo˙zna te˙z
dosta´c si ˛e tam bezpo´srednio.
W istocie relacja E jest przechodnia wtw E ◦ E ⊆ E .
Dlatego dla relacji przechodnich E mamy T (E ) = E .
Co wi ˛ecej, dla dowolnej relacji E , relacja T (E ) jest najmniejsz ˛
a relacj ˛
a
przechodni ˛
a
zwrotn ˛
a
i zawieraj ˛
ac ˛
a E
i dlatego cz ˛esto jest nazywana tranzytywnym (przechodnim) domkni ˛eciem relacji E
Edward Szczypka
25 / 31
Jagiellonian University
Theoretical
Computer Science
Odwrotno ´s ´c relacji
Relacja odwrotna do relacji E to E
−1
= {(
y , x ) : (x , y ) ∈ E } a zatem gdy E ⊆ V × V ,
to relacja E ( reprezentuje graf z przeciwnie skierowanymi strzałkami.
Przykład 3 Relacja odwrotna do ¬ na zbiorze R to relacja .
Relacja odwrotna do relacji lubi to relacja by´c lubianym: (x
lubi y )
−1
, to
(
y jest lubiany przez x ). Relacja równo´sci (x = y ) jest sama swoj ˛
a odwrotno´sci ˛
a.
Relacja by´c tej samej parzysto´sci jest sama swoj ˛
a odwrotno´sci ˛
a.
Edward Szczypka
26 / 31
Jagiellonian University
Theoretical
Computer Science
Własno ´sci składania i odwracania relacji
Zadanie 14 Poka˙z, ˙ze dla relacji binarnych E , f , G na zbiorze X zachodzi
(
E ◦ F ) ◦ G = E ◦ (F ◦ G)
(
E
−1
)
−1
=
E
(
E ◦ F )
−1
=
F
−1
◦ E
−1
∆
−1
= ∆
(
E ∪ F )
−1
=
E
−1
∪ F
−1
(
E ∩ F )
−1
=
E
−1
∩ F
−1
Sprawd´z, które równo´sci s ˛
a prawdziwe
E ◦ F = F ◦ E
(
E ∪ F ) ◦ G ⊆ (E ◦ G) ∪ (F ◦ G)
(
G ◦ E ) ∪ (G ◦ F ) ⊆ G ◦ (E ∪ F )
(
E ◦ G) ∩ (F ◦ G) ⊆ (E ∩ F ) ◦ G
G ◦ (E ∩ F ) ⊆ (G ◦ E ) ∩ (G ◦ F )
∆ ◦
E = E
E ◦ ∆ = E
Edward Szczypka
27 / 31
Jagiellonian University
Theoretical
Computer Science
Grafy nieskierowane
Graf nieskierowany
(lub po prostu graf) to struktura, G = hV , E i, w której poł ˛
aczenia
nie s ˛
a ju˙z uporz ˛
adkowane. Mo˙zemy wi ˛ec E traktowa´c jako:
zbiór dwuelementowych podzbiorów zbioru V lub, alternatywnie jako
relacj ˛e symetryczn ˛
a na zbiorze V , tzn. tak ˛
a ˙ze
∀x, y
xEy −→ yEx
i równocze´snie przeciwzwrotn ˛
a
∀x
¬xEx
Na rysunkach, odpowiada to
brakowi p ˛etelek (przeciwzwrotno´s´c)
brakowi skierowania kraw ˛edzi (symetria) ˝
O poł ˛
aczenia s ˛
a tu symetryczne.
Edward Szczypka
28 / 31
Jagiellonian University
Theoretical
Computer Science
Grafy nieskierowane II
uwaga
Poj ˛ecia dotycz ˛
ace grafów skierowanych, takie jak drogi czy osi ˛
agalno´s´c s ˛
a tu nadal
aktualne i na ogół łatwiejsze.
Zadanie 7 Ile jest (nieskierowanych) grafów na zbiorze n-elementowym?
Graf nieskierowany to rodzina (niektórych) dwuelementowych podzbiorów zbioru
wierzchołków V . Uzasadnij, ˙ze dwuelementowych podzbiorów zbioru
n-elementowego jest
n(n−1)
2
. A zatem grafów (nieskierowanych) na zbiorze
n-elementowym jest
2
n(n−1)
2
Edward Szczypka
29 / 31
Jagiellonian University
Theoretical
Computer Science
Graf pełny, podgraf i graf indukowany
Graf pełny to graf (nieskierowany), w którym ka˙zde dwa (ró˙zne) wierzchołki s ˛
a
poł ˛
aczone kraw ˛edzi ˛
a.
graf pełny na zbiorze n-elementowym ma zatem
n(n−1)
2
kraw ˛edzi.
graf pełny na zbiorze n-elementowym oznaczany jest K
n
Podgraf grafu G = hV , E i to kawałek tego grafu
formalnie to taki graf G
0
= h
V
0
,
E
0
i, ˙ze V
0
⊆ V i E
0
⊆ E
Podgraf G
0
= h
V
0
,
E
0
i grafu G = hV , Ei nazywamy grafem indukowanym, je´sli
E
0
=
E ∩ (V × V ), tzn. G
0
zawiera wszystkie kraw ˛edzie grafu G o ko ´ncach w
zbiorze V
0
.
Zadanie 7 Czy podgraf indukowany grafu pełnego jest grafem pełnym?
Czy ka˙zdy graf jest podgrafem jakiego´s grafu pełnego?
Edward Szczypka
30 / 31
Jagiellonian University
Theoretical
Computer Science
Stopie ´
n wierzchołka
Stopniem wierzchołka v w grafie (nieskierowanym) G = hV , E i nazywamy liczb ˛e
kraw ˛edzi wychodz ˛
acych z tego wierzchołka. Formalnie:
deg(v ) = #{e ∈ E : v ∈ e}
Przykład 8 W sko ´nczonym grafie nieskierowanym liczba wierzchołków o
nieparzystym stopniu jest parzysta. Istotnie, sumuj ˛
ac stopnie wszystkich wierzchołków
grafu G = hV , E i, ka˙zda kraw ˛ed´z grafu zostanie policzona podwójnie:
X
v ∈V
deg(v ) = 2 · |E |
Skoro suma taka jest liczb ˛
a parzyst ˛
a, to liczba jej nieparzystych składników musi by´c
parzysta.
Edward Szczypka
31 / 31