DISKRETNA MATEMATIKA
OSNOVE KOMBINATORIKE I TEORIJE GRAFOVA
Dragan Stevanovi, Miroslav iri
Prirodno-matematiqki fakultet u Nixu
Slobodan Simi
Matematiqki institut u Beogradu
Vladimir Balti
Fakultet organizacionih nauka u Beogradu
B E O G R A D
2008
Autori:
dr Dragan Stevanovi
, Prirodno-matematiqki fakultet u Nixu
dr Slobodan Simi
, Matematiqki institut u Beogradu
dr Miroslav iri
, Prirodno-matematiqki fakultet u Nixu
mr Vladimir Balti
, Fakultet organizacionih nauka u Beogradu
Diskretna matematika — osnove kombinatorike i teorije grafova
Izdavaq: DRUXTVO MATEMATIQARA SRBIJE
Beograd, Kneza Mihaila
35/IV
[email protected]
,
http://www.matf.bg.ac.yu/dms/
Recenzenti:
dr Dragox Cvetkovi
dr Vojislav Petrovi
Urednik:
dr Zoran Kadelburg
Za izdavaqa:
dr Branko Popovi
Crtei i slog:
autori
CIP –
Katalogizacija u publikaciji
Narodna biblioteka Srbije, Beograd
51-74:004(075.8)(076)
STEVANOVI, Dragan
Diskretna matematika : osnovi
kombinatorike i teorije grafova : udˇzbenik/
Dragan Stevanovi´c, Slobodan Simi´c,
Miroslav ´
Ciri´c, Vladimir Balti´c ; [crteˇzi
autori]. – Beograd : Drushtvo matematichara
Srbije, 2007. (Valjevo : Alexandria). –
195 str. : graf. prikazi ; 24 cm. –
Tiraˇz 500. – Bibliografija: str. 366.
ISBN 86–81453–52–1
1. Simi, Slobodan
a) Diskretna matematika - Zadaci
COBISS.SR–ID 115360268
ISBN: 86–81453–52–1
°
c
Druxtvo matematiqara Srbije
Tira: 500 primeraka
Xtampa:
ALEXANDRIA, D.O.O
, Valjevo
4
Sumaciona formula . . . . . . . . . . . . . . . . . . . . . .
63
Negacija gornjeg indeksa . . . . . . . . . . . . . . . . . . .
64
Pojednostavljivanje proizvoda . . . . . . . . . . . . . . . .
65
Sume proizvoda . . . . . . . . . . . . . . . . . . . . . . . .
65
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
1.8. PRINCIP UKLjUQENjA-ISKLjUQENjA . . . . . . . . . . . . .
68
Kako elegantno zapisati matematiqku formulu? . . . . .
70
Princip ukljuqenja-iskljuqenja
. . . . . . . . . . . . . . .
71
Generalisani princip ukljuqenja-iskljuqenja . . . . . . .
74
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
2. NAPREDNE TEHNIKE PREBROJAVANjA
79
2.1. FUNKCIJE GENERATRISE . . . . . . . . . . . . . . . . . . . .
79
Stepeni redovi . . . . . . . . . . . . . . . . . . . . . . . . .
80
Novqii i polinomi . . . . . . . . . . . . . . . . . . . . .
81
Kombinatorno znaqenje binomne teoreme . . . . . . . . . .
83
Uopxtena binomna teorema . . . . . . . . . . . . . . . . . .
83
Nalaenje funkcija generatrisa . . . . . . . . . . . . . .
86
Neke poznate funkcije generatrise . . . . . . . . . . . . .
89
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
2.2. REKURENTNE JEDNAQINE . . . . . . . . . . . . . . . . . . . .
92
Linearna rekurentna jednaqina sa konstantnim
koeficijentima . . . . . . . . . . . . . . . . . . .
96
Linearna rekurentna jednaqina sa funkcionalnim
koeficijentima . . . . . . . . . . . . . . . . . . .
103
Neke nelinearne rekurentne jednaqine . . . . . . . . . . .
104
Primene rekurentnih jednaqina . . . . . . . . . . . . . . .
110
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
120
2.3. FUNKCIJE GENERATRISE I REXAVANjE
REKURENTNIH JEDNAQINA . . . . . . . . . . . . . . . . . . .
122
Primeri . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
125
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
131
2.4. FIBONAQIJEVI BROJEVI . . . . . . . . . . . . . . . . . . . .
132
Opxti qlan Fibonaqijevog niza . . . . . . . . . . . . . .
134
Osnovne osobine . . . . . . . . . . . . . . . . . . . . . . . .
136
Identiteti sa Fibonaqijevim brojevima . . . . . . . . .
142
Tribonaqijev niz . . . . . . . . . . . . . . . . . . . . . . .
144
Lukasov niz . . . . . . . . . . . . . . . . . . . . . . . . . . .
146
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
149
2.5. KATALANOVI BROJEVI . . . . . . . . . . . . . . . . . . . . . .
151
Rekurentna relacija . . . . . . . . . . . . . . . . . . . . . .
151
Rexenje pomou funkcije generatrise . . . . . . . . . . .
152
Dva direktna rexenja . . . . . . . . . . . . . . . . . . . . .
153
Xta jox prebrojava Katalan? . . . . . . . . . . . . . . . .
156
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
159
2.6. PARTICIJE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
163
Kompozicije . . . . . . . . . . . . . . . . . . . . . . . . . . .
163
Particije prirodnog broja . . . . . . . . . . . . . . . . . .
167
Particije i funkcije generatrise . . . . . . . . . . . . .
172
Identiteti sa particijama . . . . . . . . . . . . . . . . .
175
Neka svojstva broja particija . . . . . . . . . . . . . . . .
184
5
Particije skupa, Stirlingovi i Belovi brojevi . . . . .
187
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
194
3. TEORIJA GRAFOVA
199
3.1. XTA JE GRAF? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
199
Pojam grafa . . . . . . . . . . . . . . . . . . . . . . . . . . .
199
Posebne klase grafova . . . . . . . . . . . . . . . . . . . .
204
Izomorfizam grafova . . . . . . . . . . . . . . . . . . . . .
206
Podgrafovi . . . . . . . . . . . . . . . . . . . . . . . . . . .
208
Xetanje po grafu . . . . . . . . . . . . . . . . . . . . . . .
210
Povezanost . . . . . . . . . . . . . . . . . . . . . . . . . . .
211
Rastojanje . . . . . . . . . . . . . . . . . . . . . . . . . . . .
214
Predstavljanje grafova u raqunaru . . . . . . . . . . . . .
216
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
220
3.2. STABLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
224
Pojam stabla i osnovna svojstva . . . . . . . . . . . . . .
224
Korenska stabla . . . . . . . . . . . . . . . . . . . . . . . .
227
Stabla i pretrage grafova . . . . . . . . . . . . . . . . . .
231
Stabla minimalne teine . . . . . . . . . . . . . . . . . .
236
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
240
3.3. RAZAPINjUA STABLA . . . . . . . . . . . . . . . . . . . . . .
242
Malo istorije i osnovni pojmovi . . . . . . . . . . . . . .
242
Kejlijeva teorema . . . . . . . . . . . . . . . . . . . . . . .
243
Teorema o matricama i stablima . . . . . . . . . . . . . .
252
Odreivanje broja razapinjuih stabala . . . . . . . . .
253
Vektorski prostor kontura
. . . . . . . . . . . . . . . . .
256
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
261
3.4. OJLEROVI I HAMILTONOVI GRAFOVI . . . . . . . . . . .
262
Ojlerovi grafovi . . . . . . . . . . . . . . . . . . . . . . .
265
Hamiltonovi grafovi . . . . . . . . . . . . . . . . . . . . .
267
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
273
3.5. PLANARNI GRAFOVI
. . . . . . . . . . . . . . . . . . . . . . .
274
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
281
3.6. SPARIVANjE U GRAFOVIMA . . . . . . . . . . . . . . . . . . .
283
Pojam sparivanja . . . . . . . . . . . . . . . . . . . . . . . .
283
Sistem razliqitih predstavnika . . . . . . . . . . . . . .
288
Teorema o savrxenom sparivanju . . . . . . . . . . . . . .
290
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
292
3.7. BOJENjE GRAFOVA . . . . . . . . . . . . . . . . . . . . . . . . . .
294
Uvodna razmatranja . . . . . . . . . . . . . . . . . . . . . .
294
Hromatski broj grafa . . . . . . . . . . . . . . . . . . . . .
296
Grafovi sa velikim hromatskim brojem . . . . . . . . . .
302
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
304
4. DISKRETNA VEROVATNOA
305
4.1. ELEMENTARNA VEROVATNOA . . . . . . . . . . . . . . . . .
306
Pojam dogaaja . . . . . . . . . . . . . . . . . . . . . . . . .
306
Algebra dogaaja . . . . . . . . . . . . . . . . . . . . . . .
307
Prostor verovatnoe . . . . . . . . . . . . . . . . . . . . .
308
Dodela verovatnoe dogaajima . . . . . . . . . . . . . . .
310
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
317
Predgovor
U
Diskretnu matematiku
spadaju one oblasti matematike, qiji su predmet
prouqavanja strukture i relacije definisane uglavnom na konaqnim ili pre-
brojivim skupovima, kao xto su Logika, Teorija brojeva, Algebra, Kombina-
torika, Teorija grafova, Teorija kodova ili odreeni delovi Verovatnoe.
Diskretna matematika predstavlja matematiqku osnovu svih raqunarskih nau-
ka.
Knjiga pred vama je jedan od rezultata
eLearning
projekta
eLP001/2006
posveenog nastavi diskretne matematike, a koji je neophodnom opremom fi-
nansirao
WUS Austria
. U okviru ovog projekta je implementiran veb sajt
http://elearning.pmf.ni.ac.yu
na kome se mogu nai nastavni sadraji i materijali za predmete
Diskretne
strukture
I
i
II
. Ovi predmeti su namenjeni studentima raqunarstva ili in-
formatike na fakultetima i xkolama qiji nastavni program prati preporuke
ACM Computing Curricula
. Pristup ovim predmetima je omoguen i za xiroku
publiku pod
guest
nalogom, a nastavnici, koji budu zainteresovani da za svoje
studente implementiraju sliqan sajt, mogu da se obrate prvom autoru.
S obzirom da je pomenuti
eLearning
projekat bio vezan za nastavu iz dva
posebna, ali bliska predmeta, uqesnici projekta su se odluqili da napixu
dva odgovarajua ubenika. Ova knjiga je prvi od tih ubenika, dok drugi
treba da se pojavi iz xtampe do kraja 2007.
U ovoj knjizi su obraene teme koje se na fakultetima mogu quti u okviru
predmeta pod nazivom
Diskretne strukture
II
: osnove kombinatorike, teorije
grafova i diskretne verovatnoe. Od qitaoca se trai minimalno prethodno
znanje iz logike, algebre, analize i linearne algebre.
Uqesnici projekta su zajedno napravili izbor tema za obe knjige, a
zaduenja autora u ovoj knjizi su bila sledea:
•
D. Stevanovi je napisao poglavlja 1.4 do 1.8, 2.1, 2.5 i 3.1;
•
M. iri je napisao poglavlja 1.1, 1.2, 1.3;
•
S. Simi je napisao poglavlja 3.2, 3.6, 3.7 i celu glavu 4;
•
V. Balti je napisao poglavlja 2.2, 2.3, 2.4, 2.6, 3.3, 3.4, 3.5, izabrao
zadatke za celu knjigu, nacrtao najvei broj slika i uradio indekse:
algoritama, oznaka, pojmova, i matematiqara.
7
