T´ etelek, defin´ıci´ ok v´ eges matematika alapszint˝ u vizsg´ ahoz
Lesz´ aml´ al´ asi alap¨ otletek ´ es alapfeladatok 1. Alap¨ otlet f¨ uggetlen d¨ ont´esek ´es szorz´as. (Ha egy esetet olyan d¨ont´essorozattal lehet legy´artani, melyben minden d¨ ont´esn´el a lehet˝os´egek sz´ama f¨ uggetlen a m´ar meghozott d¨ont´esekt˝ ol, ´es minden eset egyetlen konkr´et d¨ont´essorozattal j¨ohet ki.) 1. Alapfeladat k f´ele jelb˝ ol h´any n hossz´ u sorozat k´esz´ıthet˝o (ism´etl´eses vari´ aci´ ok)? n Megold´as: k . 2. Alapfeladat n k¨ ul¨ onb¨ oz˝ o dolgot h´anyf´elek´eppen lehet sorbatenni (permut´ aci´ ok)? Megold´as: n!. 3a. Alapfeladat H´ any r´eszhalmaza van egy n-elem˝ u halmaznak? Megold´as: 2n . 3b. Alapfeladat H´ any p´ aros elemsz´am´ u r´eszhalmaza van egy n-elem˝ u halmaznak? n−1 Megold´as: 2 . 4. Alapfeladat n dolog k¨ oz¨ ul h´anyf´elek´eppen lehet k-t kiv´alasztani, ha a sorrend sz´ am´ıt (ism´etl´es n´elk¨ uli vari´ aci´ ok)? Megold´as: n(n − 1) · · · (n − k + 1). 2. Alap¨ otlet Teh´en m´ odszer. Olyankor, amikor az 1. alap¨otlet csak az´ert nem m˝ uk¨ odik, mert minden esetet t¨ obbsz¨ or sz´ amolunk (t¨obb konkr´et d¨ont´essorozat is adhatja ugyanazt az esetet). Ha minden eset ugyanannyi konkr´et d¨ont´essorozattal j¨ohet l´etre, akkor a szorz´ assal kapott ´ert´eket leosztjuk ezzel a sz´ammal. 5. Alapfeladat n-elem˝ u halmaz k-elem˝ u r´eszhalmazainak sz´ama (ism´etl´es n´elk¨ uli kom n(n−1)···(n−k+1) n . bin´ aci´ ok). Megold´ as k = k(k−1)···1 6. Alapfeladat n dolgot, melyek k¨ozt vannak egyform´ak, h´anyf´elek´eppen lehet sorbatenni (ism´etl´eses permut´ aci´ ok)? Megold´as: n1 !n2n!!...nr ! . 3. Alap¨ otlet: dobjuk ki a rosszat! Egy b˝ovebb halmazb´ol kidobjuk azokat, melyeket nem akarunk megsz´ amolni. 4. Alap¨ otlet: esetsz´etv´ alaszt´ as. A megsz´amoland´o dolgokat valamilyen szempont szerint csoportokra osztjuk, a csoportok m´eret´et k¨ ul¨on-k¨ ul¨on hat´arozzuk meg, majd a kapott m´ereteket ¨ osszeadjuk. k−1 7a. Alapfeladat (p´ enzoszt´ as) n embernek k darab (egyforma) 100-forintost n−1 f´elek´eppen lehet kiosztani, ha mindenkinek kapnia kell legal´abb egyet. n embernek k n+k−1 darab (egyforma) 100-forintost f´elek´eppen lehet kiosztani, ha nincs megk¨ ot´es. k 7b. Alapfeladat n k¨ ul¨ onb¨ oz˝ o dolog k¨oz¨ ul h´anyf´elek´eppen v´alaszthatunk k-t, ha ism´etl´es is lehet ´es a sorrend nem sz´ am´ıt (ism´etl´eses kombin´ aci´ ok)? Megold´as: n+k−1 . Bijekci´ o k l´etes´ıthet˝ o a feladat ´es a p´enzoszt´asi feladat k¨oz¨ott. Binomi´ alis t´ etel (Omar Khayyam) (x + y)n =
n 0
xn +
n 1
xn−1 y 1 + · · · +
n k
xn−k y k + · · · +
n n
yn .
Pascal h´ aromsz¨ og T´ etel A k¨ ovetkez˝ ok mindegyike az n. sor k. elem´et adja (mindk´et esetben 0-val kezdve a sz´amol´ast), melyet itt pn,k -val jel¨ol¨ unk: 1
a) A h´ aromsz¨ og tetej´er˝ ol minden l´ep´esben egyet jobbra le vagy balra le l´epve, pn,k f´elek´eppen lehet lejutni az n. sor k. poz´ıci´oj´aba ; b) pn,k az egy¨ utthat´ oja (x + y)n -ben az xn−k y k tagnak; c) pn,k ker¨ ul az n. sor k. poz´ıci´oj´aba, ha a h´aromsz¨oget u ´gy k´epezz¨ uk, hogy minden sor k´et sz´el´ere 1-et ´ırunk, a bels˝ o elemeket pedig u ´gy kapjuk, hogy a felette l´ev˝o k´et ´ert´eket ¨osszeadjuk; d) pn,k egy n-elem˝ u halmaz k-elem˝ u r´eszhalmazainak sz´ama; n(n−1)···(n−k+1) n . e) pn,k = k = k(k−1)···1 Skatulya-elv Ha kr + 1 goly´ ot tesz¨ unk k skatuly´aba, akkor lesz olyan skatulya, melyben legal´abb r + 1 goly´ o van.
Logikai szita formula Tetsz˝oleges X alaphalmaz ´es A1 , ..., An ⊆ H r´eszhalmazokra azon elemek sz´ama, melyek egyik Ai -ben sincsenek benne |X|−(|A1 |+. . .+|An |)+(|A1 ∩A2 |+. . .+|An−1 ∩An |)+· · ·+(−1)k (|A1 ∩. . .∩Ak |+· · ·)+· · · + +(−1)n |A1 ∩ · · · ∩ An |. Gr´ afok alapjai gr´ af, ir´ any´ıtott gr´ af, foksz´ am, ki-fok, be-fok: ... Egyszer˝ u gr´ af: nincs benne se hurok´el, se t¨obbsz¨or¨os ´el. Egyszer˝ u, ir´ any´ıtatlan gr´ af prec´ız def.: G = (V, E), ahol V tetsz˝oleges halmaz (cs´ ucsok halmaza), E pedig V k´etelem˝ u r´eszhalmazainak tetsz˝oleges r´eszhalmaza (´elek halmaza). r´ eszgr´ af: b´ armilyen gr´ af, amit u ´gy nyer¨ unk az eredeti gr´afb´ol, hogy ´eleket ´es cs´ ucsokat t¨orl¨ unk. (Cs´ ucs t¨ orl´esekor a r´ a illeszked˝o ´elek is t¨orl˝odnek. Speci´alisan 0 cs´ ucs ´es ´el is t¨or¨olhet˝ o, azaz minden gr´ af r´eszgr´afja saj´at mag´anak.) T´ etel B´ armely gr´ afban a p´ aratlan fok´ u cs´ ucsok sz´ama p´aros. T´ etel B´ armely gr´ afban a fokok ¨osszege az ´elsz´am k´etszerese. T´ etel B´ armely ir´ any´ıtott gr´ afban a ki-fokok ¨osszege= be-fokok ¨osszege= az ´elek sz´ ama. s´ eta: olyan v1 , v2 , . . . , vk cs´ ucssorozat, melyre v1 − v2 , v2 − v3 ,...,vk−1 − vk ´el. u ´ t: olyan v1 , v2 , . . . , vk cs´ ucssorozat, melyre v1 − v2 , v2 − v3 ,...,vk−1 − vk ´el, ´es a cs´ ucsok k¨ ul¨onb¨oz˝ ok. k¨ ors´ eta: olyan s´eta, melynek els˝o ´es utols´o cs´ ucsa megegyezik. k¨ or: olyan k¨ ors´eta, melynek az els˝o ´es utols´o cs´ ucs megegyez´es´et lesz´am´ıtva k¨ ul¨onb¨ oz˝ ok a cs´ ucsai. Foksz´ amsorozatok realiz´ al´ asa 2
T´ etel Egy d1 , . . . , dn nemnegat´ıv sz´amokb´ol ´all´o sorozathoz annak sz¨ uks´eges ´es el´egs´eges felt´etele, hogy l´etezzen olyan n cs´ ucs´ u gr´af, melyben ´eppen ezek a foksz´amok az, hogy d1 + · · · + dn p´ aros legyen. T´ etel Egy d1 , . . . , dn nemnegat´ıv sz´amokb´ol ´all´o sorozathoz annak sz¨ uks´eges ´es el´egs´eges felt´etele, hogy l´etezzen olyan n cs´ ucs´ u, hurok´elet nem tartalmaz´o gr´af, melyben ´eppen ezek a foksz´amok az, hogy (i) d1 + · · · + dn p´ aros legyen; ´es (ii) a legnagyobb di ne legyen nagyobb, mint a t¨obbi ¨osszege. T´ etel Egy d1 ≤ d2 ≤ · · · ≤ dn nemnegat´ıv sz´amokb´ol ´all´o sorozathoz annak sz¨ uks´eges felt´etele, hogy l´etezzen olyan n cs´ ucs´ u, egyszer˝ u gr´af, melyben ´eppen ezek a foksz´amok az, hogy (i) d1 + · · · + dn p´ aros legyen; ´es (ii) b´armely k-ra d1 + · · · + dn−k ≥ dn−k+1 − (k − 1) + · · · + dn − (k − 1). (Az el´egs´egess´eghez picit m´odos´ıtani kell a felt´etelt, de azt nem kell tudni.) Hakimi algoritmus ... T´ etel Ha egy foksz´ amsorozat realiz´alhat´o egyszer˝ u gr´affal, akkor a Hakimi algoritmus is lerajzol egyet. (Nem kell biz.) ¨ Osszef¨ ugg˝ os´ eg, komponensekre bont´ as ´ All. Ha k´et cs´ ucs k¨ ozt van s´eta, akkor van u ´t is. ´ All. Ha van u ´t az a cs´ ucsb´ ol a b cs´ ucsba ´es van u ´t a b cs´ ucsb´ol a c cs´ ucsba, akkor van u ´t az a cs´ ucsb´ ol a c cs´ ucsba. A G gr´ af ¨ osszef¨ ugg˝ o, ha b´ armely k´et cs´ ucsa k¨ozt van u ´t. A G gr´af ¨ osszef¨ ugg˝ o komponensei a maxim´alis ¨osszef¨ ugg˝o r´eszgr´afjai. (Azaz olyan r´eszgr´afok, melyek ¨ osszef¨ ugg˝ ok, de b´armely ´elet vagy cs´ ucsot hozz´ajuk v´eve (G-b˝ ol) m´ ar nem ¨osszef¨ ugg˝ o gr´ afot kapunk.) T´ etel Minden gr´ af egy´ertelm˝ uen ¨osszef¨ ugg˝o komponensekre bonthat´o. (Nem kell prec´ızen biz., de ´erteni kell.) F´ ak Fa: k¨ormentes, ¨ osszef¨ ugg˝ o gr´ af. T´ etel Minden ¨ osszef¨ ugg˝ o gr´ afb´ ol elhagyhatunk u ´gy ´eleket (de cs´ ucsokat nem !), hogy f´ at kapjunk. (Seg´ ed´ all´ıt´ as Egy ¨ osszef¨ ugg˝ o gr´af egy k¨or´enek ´el´et elhagyva a gr´af ¨osszef¨ ugg˝o marad.) Egy G ¨ osszef¨ ugg˝ o gr´ af F fesz´ıt˝ o f´ aja olyan r´eszgr´af, melynek cs´ ucsai megegyeznek G cs´ ucsaival, ´es F fa. (Azaz aminek a l´etez´es´et az el˝oz˝o t´etel bizony´ıtja.) T´ etel Egy gr´ af akkor ´es csak akkor fa, ha ¨osszef¨ ugg˝o, de b´armely ´elt elhagyva m´ ar nem ¨osszef¨ ugg˝ o. T´ etel Egy gr´ af akkor ´es csak akkor fa, ha k¨ormentes, de b´armely u ´j ´elt beh´ uzva keletkezik k¨or. T´ etel Egy gr´ af akkor ´es csak akkor fa, ha b´armely k´et pontja k¨ozt pontosan egy u ´t van. (Seg´ ed´ all´ıt´ as Ha k´et pont k¨ ozt k´et u ´t is van, akkor a gr´afban van k¨or.) Gy¨ okeres fa: egy fa, melynek kijel¨olt¨ uk egy cs´ ucs´at (ezt gy¨ ok´ ernek h´ıvjuk). 3
´ ıt´ All´ as B´ armely legal´ abb k´et cs´ ucs´ u f´aban van legal´abb k´et 1 fok´ u cs´ ucs. Fan¨ oveszt´ esi elj´ ar´ as Az egy cs´ ucs´ u gr´afb´ol indulva a k¨ovetkez˝o l´ep´est ism´etelgetj¨ uk: a m´ar megl´ev˝ o gr´ af mell´e felvesz¨ unk egy u ´j cs´ ucsot ´es ¨osszek¨otj¨ uk a gr´af egyik cs´ ucs´ aval. T´ etel 1. A fan¨ oveszt´esi elj´ ar´ as minden l´ep´es´eben f´at kapunk. 2. Minden fa el˝ o´ all´ıthat´ o fan¨oveszt´esi elj´ar´assal. T´ etel n cs´ ucs´ u f´ anak n − 1 ´ele van. Pr¨ ufer k´ od, Cayley t´ etel Vigy´ azat: nem u ´gy volt, ahogy a Lov´asz-Pelik´an-Vesztergombi k¨onyvben van! Cayley t´ etel n c´ımk´ezett ponton nn−2 fa van. Legyen F fa az 1, 2, ..., n cs´ ucsokon. F b˝ ov´ıtett Pr¨ ufer k´ odj´ at u ´gy kapjuk, hogy addig ism´etelj¨ uk a k¨ovetkez˝o l´ep´est, am´ıg egyetlen cs´ ucs´ u gr´ afot nem kapunk: a fa legkisebb c´ımk´ej˝ u 1 fok´ u cs´ ucs´at let¨or¨olj¨ uk a r´a illeszked˝o ´ellel egy¨ utt, ´es fel´ırjuk egym´as al´ a az ´el k´et v´egpontj´ anak a c´ımk´ej´et (fel¨ ulre a let¨or¨olt cs´ ucsot). ´Igy egy n − 1 hossz´ u ”k´etemeletes” sorozatot kapunk. Jel¨olj¨ uk a1 , a2 , . . . , an−1 -gyel az als´ o ´es b1 , b2 , . . . bn−1 -gyel a fels˝ o emeletet. ´ ıt´ All´ as 1. Mindig n lesz a v´eg¨ ul ottmaradt cs´ ucs; 2. A f¨ ols˝ o sorban (emeleten) mindenki egyszer szerepel, kiv´eve az n-et, aki nem szerepel. 3. Alul az els˝ o n − 2 sz´ amot n´ezve (teh´at nem figyelembe v´eve az utols´o n-et), az i sz´am eggyel kevesebbszer szerepel, mint az i cs´ ucs foka F -ben. T´ etel Ha tudjuk, hogy egy a1 , a2 , . . . , an−2 sorozat egy fa b˝ov´ıtett Pr¨ ufer k´odj´anak als´ o sora (az utols´ o an−1 -et nem v´eve figyelembe), akkor egy´ertelm˝ uen ki tudjuk tal´ alni a hi´anyz´o an−1 -et ´es b1 , b2 , . . . , bn−1 -et, ´es ´ıgy a f´at is. F Pr¨ ufer k´ odja: az a1 a2 . . . an−2 sorozat. T´ etel A k¨ ovetkez˝ o elj´ ar´ as tetsz˝ oleges a1 , a2 , . . . , an−2 sorozatb´ol (melynek elemei 1 ´es n k¨ozti sz´amok) olyan f´ at ´ all´ıt el˝ o, melynek Pr¨ ufer k´odja a1 a2 . . . an−2 : a gr´af cs´ ucsai az 1, 2, . . . n sz´ amok, ´elei pedig a1 − b1 , a2 − b2 , . . . an−1 − bn−1 , ahol an−1 legyen n; b1 legyen a legkisebb olyan sz´ am, mely nem szerepel az {a1 , a2 , . . . , an−1 } halmazban; b2 legyen a legkisebb olyan sz´ am, mely nem szerepel a {b1 , a2 , . . . , an−1 } halmazban; ´es ´altal´aban, ha m´ ar b1 , b2 , . . . , bi−1 megvan, bi legyen a legkisebb olyan sz´ am, mely nem szerepel a {b1 , b2 , . . . , bi−1 , ai , . . . , an−1 } halmazban. Cayley t´ etel bizony´ıt´ asa: ... Euler vonalak Ny´ılt Euler vonal: Olyan s´eta, mely a gr´af minden ´el´en pontosan egyszer megy ´ at (´es nem k¨ors´eta). Z´ art Euler vonal: Olyan k¨ ors´eta, mely a gr´af minden ´el´en pontosan egyszer megy ´ at. 4
¨ Euler t´ etel 1. Osszef¨ ugg˝ o gr´ afban ny´ılt Euler vonal l´etez´es´enek sz¨ uks´eges ´es el´egs´eges felt´etele: pontosan k´et p´ aratlan fok´ u cs´ ucs van. ¨ 2. Osszef¨ ugg˝ o gr´ afban z´ art Euler vonal l´etez´es´enek sz¨ uks´eges ´es el´egs´eges felt´etele: nincs p´ aratlan fok´ u cs´ ucs. Er˝ osen ¨ osszef¨ ugg˝ o ir´ any´ıtott gr´ af: b´ armely k´et cs´ ucs k¨ozt van u ´t u ´gy, hogy csak a ny´ıl ir´any´ aban szabad egy ´elen l´epni. Euler t´ etel Er˝ osen ¨ osszef¨ ugg˝ o ir´any´ıtott gr´afban akkor ´es csak akkor van olyan k¨ ors´eta, mely minden ´elen pontosan egyszer, a ny´ıl ir´any´aban megy ´at, ha minden cs´ ucsra a be-fok egyenl˝o a ki-fokkal. Hamilton u ´t ´ es k¨ or Hamilton k¨ or: olyan k¨ or, mely a gr´af minden cs´ ucs´an ´atmegy. Hamilton u ´ t: olyan u ´t, mely a gr´af minden cs´ ucs´an ´atmegy. Megjegyz´ es Itt nincs olyan k¨ onnyen ellen˝orizhet˝o sz¨ uks´eges ´es el´egs´eges felt´etel, mint az Euler vonalakn´ al. ´ All. 1. A Hamilton k¨ or l´etez´es´enek sz¨ uks´eges felt´etele, hogy k pontot elhagyva a gr´ afb´ ol legfeljebb k komponens keletkezzen. 2. A Hamilton u ´t l´etez´es´enek sz¨ uks´eges felt´etele, hogy k pontot elhagyva a gr´ afb´ ol legfeljebb k + 1 komponens keletkezzen. Dirac t´ etel Ha egy n cs´ ucs´ u, egyszer˝ u gr´afban minden pont foka legal´abb n/2, akkor van benne Hamilton k¨ or. P´ aros´ıt´ asok p´ aros gr´ afban P´ aros gr´ af: olyan gr´ af, melyben a cs´ ucshalmaz k´et nem¨ ures r´eszre bonthat´o u ´gy, hogy ´el csak a k´et r´esz k¨ oz¨ ott megy. P´eld´aul a h´ aromsz¨ og (az a h´ arom cs´ ucs´ u egyszer˝ u gr´af, melyben mind a h´arom ´el be van h´ uzva) nem p´ aros, mert ak´ arhogy osztjuk k´et nem¨ ures r´eszre a h´arom cs´ ucsot, az egyik r´eszen bel¨ ul megy ´el. ´ Altal´ aban a k´et r´eszt A ´es B jel¨ oli, a gr´afot r¨oviden G = (A∪B, E) p´aros gr´afnak ´ırjuk, ahol E az ´elek halmaza. A-t ´es B-t u ´gy is emlegetj¨ uk, hogy a p´ aros gr´ af k´ et cs´ ucsoszt´ alya. P´ aros´ıt´ as: az ´elek olyan r´eszhalmaza, melyben semelyik k´et ´elnek nincs k¨oz¨os v´egpontja. Egy M ⊆ E p´ aros´ıt´ as ´ atal fedett cs´ ucsok: azon cs´ ucsok, melyekre illeszkedik ´el M ben. Teljes p´ aros´ıt´ as: olyan p´ aros´ıt´ as, mely minden cs´ ucsot fed. A-t fed˝ o p´ aros´ıt´ as: olyan p´ aros´ıt´as, mely A minden cs´ ucs´at fedi. Hall felt´ etel az A cs´ ucsoszt´ alyra: b´armely X ⊆ A-ra |N (X)| ≥ |X|. Itt N (X) azon B-beli cs´ ucsokat jel¨oli, melyeknek van legal´abb egy X-beli szomsz´edja. (Egy U halmaz eset´en |U | jel¨ oli U elemeinek sz´am´at.) Frobenius t´ etel Teljes p´ aros´ıt´as l´etez´es´enek sz¨ uks´eges ´es el´egs´eges felt´etele a k¨ovetkez˝ o k´et felt´etel egy¨ utt: (i) |A| = |B|; (ii) a Hall felt´etel A-ra. 5
Hall t´ etel A-t fed˝ o p´ aros´ıt´ as l´etez´es´enek sz¨ uks´eges ´es el´egs´eges felt´etele a Hall felt´etel teljes¨ ul´ese A-ra. Deficites Hall t´ etel Ha b´ armely X ⊆ A-ra |N (X)| ≥ |X| − k, akkor van olyan p´ aros´ıt´ as, mely A cs´ ucsait legfeljebb k kiv´etellel fedi. Megjegyz´ es A fentin´el nagyobb p´aros´ıt´as nem is l´etezhet ha van olyan X ⊆ A-ra, melyre |N (X)| = |X| − k. Magyar m´ odszer Elj´ ar´ as (algoritmus), mely megkeres egy lehet˝o legnagyobb p´ aros´ıt´ ast. Legyen M egy p´ aros´ıt´ as. Egy M -re n´ ezve jav´ıt´ o u ´ t olyan u ´t a gr´afban, melynek v´egpontjai M ´ altal fedetlenek, ´es felv´altva tartalmaz M -beli ´es nem M -beli ´elt. M -re n´ ezve majdnem jav´ıt´ o u ´ t: olyan u ´t a gr´afban, mely felv´altva tartalmaz M -beli ´es nem M -beli ´elt. Majdnem jav´ıt´ ou ´tnak tekint¨ unk egy 1 cs´ ucsb´ol ´es 0 ´elb˝ol ´all´o utat. ´ Eszrev´ etel Ha egy jav´ıt´ o u ´t azon ´eleit, melyek M -beliek, kivessz¨ uk M -b˝ol, az u ´t azon ´eleit pedig, melyek nem M -beliek, betessz¨ uk M -be, akkor M tov´abbra is p´aros´ıt´as marad, de a m´erete eggyel n˝ o.
6
