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
Document Outline
Wyszukiwarka
Podobne podstrony:
LECTURE 02 EN
wfhss workshop20090325 lecture01 02 en
wfhss workshop20090325 lecture02 02 en
wfhss workshop20071206 lecture06 02 en
wfhss conf20080604 lecture1 02 it
wfhss workshop20071206 lecture01 02 en
Lecture 01 02 03 Computer Unix
Feynman Lectures on Physics Volume 1 Chapter 02
Econometrics, Lecture 2, 2014 02 25
Econometrics, Lecture 1, 2014 02 18
IR Lecture1
uml LECTURE
lecture3 complexity introduction
Wyk 02 Pneumatyczne elementy
więcej podobnych podstron