DRUˇ
STVO MATEMATI ˇ
CARA SRBIJE
Materijali za mlade matematiˇ
care, sv. 43
Dragan Stevanovi´c
Marko Miloˇsevi´c
Vladimir Balti´c
DISKRETNA
MATEMATIKA
OSNOVE KOMBINATORIKE
I TEORIJE GRAFOVA
Zbirka reˇsenih zadataka
B E O G R A D
2004
2
Autori:
dr Dragan Stevanovi´c
, docent Prirodno-matematiˇckog fakulteta u Niˇsu
Marko Miloˇsevi´c
, asistent Prirodno-matematiˇckog fakulteta u Niˇsu
Vladimir Balti´c
, asistent Ekonomskog fakulteta u Beogradu
DISKRETNA MATEMATIKA, Osnove kombinatorike i teorije grafova
Zbirka reˇsenih zadataka
Materijali za mlade matematiˇcare, sveska 43
Izdavaˇc: DRUˇ
STVO MATEMATI ˇ
CARA SRBIJE
Beograd, Kneza Mihaila 35/IV
dmsmatf.bg.ac.yu
,
http://www.matf.bg.ac.yu/dms/
Recenzenti:
dr Dragoˇs Cvetkovi´c
dr Vojislav Petrovi´c
Urednik:
dr Zoran Kadelburg
Za izdavaˇca:
dr Rade Doroslovaˇcki
Crteˇzi 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 : zbirka
reˇsenih zadataka / Dragan Stevanovi´c, Marko
Miloˇsevi´c, Vladimir Balti´c ; [crteˇzi
autori]. – Beograd : Druˇstvo matematiˇcara
Srbije, 2004. (Valjevo : Alexandria). –
195 str. : graf. prikazi ; 24 cm. –
(Materijali za mlade matematiˇcare ; sv.
43 / Druˇstvo matematiˇcara Srbije)
Tiraˇz 500. – Bibliografija: str. 195.
ISBN 86–81453–52–1
1. Miloxevi², Marko
a) Diskretna matematika - Zadaci
COBISS.SR–ID 115360268
ISBN: 86–81453–52–1
°
c Druˇstvo matematiˇcara Srbije
Tiraˇz: 500 primeraka
ˇ
Stampa: ALEXANDRIA, D.O.O, Valjevo
Uvod
Iako je matematika u potpunosti apstraktna nauka, njen razvoj je velikim de-
lom uslovljen njenim primenama. Na primer, u doba industrijske revolucije i
pojave brojnih mehaniˇckih maˇsina doˇslo je do velikog procvata matematiˇcke
analize, jer je ona bila u stanju da reˇsava optimizacione probleme koji su se
javljali pri radu sa takvim maˇsinama. S obzirom da su maˇsine tada bile konti-
nualnog dejstva, nije bilo velike potrebe za reˇsavanjem optimizacionih problema
na konaˇcnim skupovima i takvi problemi su tretirani kao rekreativna mate-
matika. Situacija se menja sa pojavom raˇcunara sredinom proˇslog veka, koji
stvaraju mogu´cnost efektivnog reˇsavanja mnogih optimizacionih problema na
velikim konaˇcnim skupovima. Takva mogu´cnost name´ce potrebu za boljim
upoznavanjem matematiˇckih struktura definisanih nad konaˇcnim ili prebro-
jivim skupovima i dovodi do naglog razvitka diskretne matematike u posled-
njih pedesetak godina.
ˇ
Staviˇse, svi matematiˇcki problemi u raˇcunarskim
naukama pripadaju diskretnoj matematici, pa je zbog toga diskretna matem-
atika obavezan predmet na raˇcunarskim fakultetima ˇsirom sveta.
Namena zbirke je da prati program predmeta “Diskretna matematika” na
Prirodno-matematiˇckom fakultetu u Niˇsu. Neke oblasti diskretne matematike,
kao ˇsto su matematiˇcka logika, algebra i (diskretna) verovatno´ca, prouˇcavaju
se u okviru posebnih predmeta na ovom fakultetu. Zbog toga se prvi autor,
koji i predaje ovaj predmet, koncentrisao samo na dve vaˇzne oblasti diskretne
matematike: kombinatoriku i teoriju grafova. Inaˇce, postoje i drugi vaˇzni delovi
diskretne matematike (npr. teorija kodova), ali oni nisu uˇsli u nastavni program
zbog nedostatka vremena.
Zbirka sadrˇzi 253 zadatka, svaki sa viˇse ili manje iscrpnim reˇsenjem. Zadaci
su rasporedjeni u tri glave: prebrojavanje sa stilom, funkcije generatrise i teorija
grafova, dok su reˇsenja svih zadataka data u ˇcetvrtoj glavi. U svakoj glavi
zadaci su dalje rasporedjeni u odeljke, a na poˇcetku svakog odeljka nalazi se
kratak teorijski uvod, koji ˇcine definicije i neke poznate teoreme, iznete bez
dokaza. Unutar odeljaka, zadaci su rasporedjeni po teˇzini. Lakˇsi zadaci, za ˇcije
reˇsavanje je dovoljna direktna upotreba definicija i rezultata iznetih u teorijskom
uvodu, oznaˇceni su sa
−
. Zadaci uobiˇcajene teˇzine (a ponekad i malo teˇzi od
njih) dati su bez oznake, dok su teˇski zadaci, za ˇcije reˇsavanje je potrebno viˇse
mu´ckanja glavom, oznaˇceni sa
+
.
S obzirom da su svi autori bivˇsi, viˇse ili manje uspeˇsni, takmiˇcari, delovi
5
Glava 1
Prebrojavanje sa stilom
1.1
Principi prebrojavanja
Matematiˇcka definicija prebrojavanja.
Neka je
N
skup prirodnih brojeva. Za
proizvoljan prirodni broj
n
∈
N
, neka je
N
n
=
{
1
,
2
,
3
, . . . , n
}
. Ako je
X
proizvoljan konaˇcan skup, tada se pod
prebrojavanjem
skupa
X
podrazumeva
konstruisanje bijektivne funkcije
f
, koja za neko
n
0
∈
N
preslikava
N
n
0
u
X
.
Broj
n
0
zovemo brojem elemenata skupa
X
i oznaˇcavamo sa
|
X
|
.
Princip jednakosti.
Ako za dva konaˇcna skupa
A
i
B
postoji bijekcija
f
:
A
7→
B
, tada je
|
A
|
=
|
B
|
.
Princip zbira.
Ako su
A
i
B
neprazni i disjunktni konaˇcni skupovi (
A
∩
B
=
∅
),
tada je
|
A
∪
B
|
=
|
A
|
+
|
B
|
.
Princip proizvoda.
Neka su
X
i
Y
konaˇcni neprazni skupovi, i neka je
S
pod-
skup
X
×
Y
. Neka je
r
x
(
S
) =
|
S
∩ {
(
x, y
) :
y
∈
Y
}|
, a
c
y
(
S
) =
|
S
∩ {
(
x, y
) :
x
∈
X
}|
. Tada vaˇzi:
(i)
|
S
|
=
P
x
∈
X
r
x
(
S
) =
P
y
∈
Y
c
y
(
S
).
(ii) Ako je
r
x
(
S
) =
r
za svako
x
i
c
y
(
S
) =
c
za svako
y
, tada je
r
|
X
|
=
c
|
Y
|
.
(iii)
|
X
×
Y
|
=
|
X
| · |
Y
|
.
Dirihleov princip, I.
Ako je
m
loptica smeˇsteno u
n
kutija i
m > n
, tada se
bar u jednoj kutiji nalaze bar dve loptice.
Dirihleov princip, II.
Ako je
m
loptica smeˇsteno u
n
kutija i
m > nr
, tada se
bar u jednoj kutiji nalazi bar
r
+ 1 loptica.
Prebrojavanje sa stilom.
Prebrojavanje konaˇcnih skupova uz koriˇs´cenje ovih
i drugih kombinatornih principa smatramo (neformalno) prebrojavanjem sa
stilom.
7
