˝ ´ KOMBINATORIKA ELOAD AS osztatlan matematika tan´ar hallgat´ok sz´am´ara
Gr´afelm´eleti alapfogalmak 2015
El˝oad´o: Hajnal P´eter
1. Egyszer˝ u gr´ afok Nagyon sok helyzetben egy alaphalmaz elemei k¨oz¨ott kit˝ untetett p´arok vannak. P´ elda. Egy u ´ th´al´ozat csom´opontjai k¨oz¨ott bizonyosak k¨ozvetlen o¨sszek¨ottet´essel b´ırnak.
1. ´abra. Magyarorsz´ag vas´ uti t´erk´epe
2. ´abra. London metro t´erk´epe
Gr´afelm´eleti alapfogalmak-1
3. ´abra. Az USA jelent˝os l´egi u ´ tvonalainak t´erk´epe P´ elda. Az egyes szavakra a n´eh´any leggyakrabban asszoci´alt szavak egy egyszer˝ u gr´afot adnak.
4. ´abra. P´ elda. Egy molekul´at alkot´o elemek ´es k¨ort¨ uk l´ev˝o k¨ot´esek sokatmond´o egy k´emikus sz´am´ara. A legegyszer˝ ubb p´elda a v´ız:
5. ´abra.
Gr´afelm´eleti alapfogalmak-2
P´ elda. A Medicik kor´aban a nagy olasz csal´adok k¨oz¨otti kapcsolati h´al´o lerajzol´asa seg´ıt a kor meg´ert´es´eben:
6. ´abra.
L´assuk a form´alis defin´ıci´ot. Defin´ıci´ o. Egy G egyszer˝ u gr´af egy V v´eges cs´ ucshalmazb´ol (V elemeire mint cs´ ucsokra/pontokra hivatkozunk) ´es bizonyos ´eleknek nevezett cs´ u csp´ a rokb´ o l a ´ llnak. Az ´ e lek halmaz´ at V E-vel jel¨olj¨ uk. Azaz E ⊂ 2 . N´eh´any terminol´ogia: e = {u, v} ∈ E eset´en azt mondjuk ‘e o¨sszek¨oti u-t ´es v-t’, ‘u ´es v az e ´el k´et v´egpontja’, ‘u ´es v illeszkedik az e ´elre’, ‘u ´es v szomsz´edos (az e ´el ment´en)’, ‘u a v cs´ ucs egy szomsz´edja’.
2. Egyszer˝ u gr´ afok lerajzol´ asa Gr´afok (ahogy nev¨ uk is mutatja) grafikusak, k¨onnyen vizualiz´alhat´ok. Ha egy gr´afot nem form´alisan cs´ ucsainak ´es az ´eleket alkot´o cs´ ucsp´aroknak a felsorol´as´aval akarjuk le´ırni, akkor lerajzoljuk. Defin´ıci´ o. Egy gr´af lerajzol´as´an´al V elemeit/cs´ ucsokat k¨ ul¨onb¨oz˝o s´ıkbeli pontokkal azonos´ıtjuk. Egy v cs´ ucsnak megfelel˝o Pv pontot cs´ ucspontnak nevez¨ unk ´es kis karik´aval jel¨olj¨ uk. Minden e = {u, v} ´elt egy folyonos g¨orb´evel reprezent´alunk, ami k´et v´egpontj´anak megfelel˝o karik´at k¨oti ¨ossze. Az e ´elnek megfelel˝o γe g¨orbe az e ´el ´elg¨orb´eje. Az ´abra egy´ertelm˝ u olvashat´os´aga miatt feltessz¨ uk, hogy egy ´el ´elg¨orb´eje csak k´et v´egpontj´anak megfelel˝o cs´ ucsponton halad ´at, tov´abb´a k´et ´elg¨orbe csak v´eges sok ponrban tal´alkozik ´es k¨oz¨os bels˝o pontjaikban ´atmetszik egym´ast. P´ elda. Egy kilenc pont´ u gr´af lerajzol´as´at adjuk meg:
Gr´afelm´eleti alapfogalmak-3
7. a´bra. Egy gr´afot rajzoltunk le k´etszer. A bal oldalon a karik´ak ´es ´elek mell´e oda´ırtuk a nev¨ uket”. A jobb oldalon ugyanaz az ´abra szerepel az elnevez´esek ” n´elk¨ ul. Ezen az oldalon nem teljes a gr´af le´ır´asa, de az ¨osszek¨ot¨otts´egek strukt´ ur´aja j´ol l´athat´o. Sokszor csak ez az inform´aci´o is el´eg, hogy egy a gr´afra vonatkoz´o probl´em´at megoldjuk.
3. A gr´ af fogalma Gyakran az egyszer˝ u gr´af fogalma nem el´eg egy strukt´ ura le´ır´as´ara. P´ elda. Egy u ´ th´al´ozatban k´et csom´opont k¨oz¨ott t¨obbf´ele k¨ozvetlen el´erhet˝os´eg is lehet.
8. a´bra. T¨ort´enetileg legfontosabb p´elda a XIX. sz´azadi K˝onigsberg v´aros´anak k¨oz´eppontj´aban l´ev˝o sz´arazf¨oldi egys´egek ´es a k¨ozt¨ uk fekv˝o hidak rendszere P´ elda. Egy molekul´aban k´et atom k¨oz¨ott t¨obbsz¨or¨os k¨ot´es is el˝ofordulhat.
9. ´abra. A karbamid szerkezeti rajza Ha London metro h´al´ozat´anak gr´afj´aban k´et szomsz´edos cs´ ucs/´allom´as o¨sszek¨ot¨ott akkor k¨ozvetlen metro ¨osszek¨ottet´es van k¨ozt¨ uk. N´eha azonban t¨obb vonal kocsijaival Gr´afelm´eleti alapfogalmak-4
utazva is el´erhet¨ unk egyikb˝ol a m´asikba. Ezen inform´aci´o elveszik a k¨ozvetlen ” elk´erhet˝os´eg” egyszer˝ u gr´afj´aban. A gr´af ´altal´anos defin´ıci´oja: Defin´ıci´ o. Egy gr´af egy v´eges V cs´ ucshalmaz ´es egy v´eges E ´elhalmazb´ol a´ll. Tov´abb´a egy illeszked´esi rel´aci´o, amely bizonyos cs´ ucs-´el p´arokat kiemel, amelyek illeszkednek. Illeszked´es eset´en azt mondjuk, hogy az e ´elnek az u cs´ ucs v´egpontja. A gr´af eset´en, hogy minden ´elnek k´et v´egpontja van. Ez a k´et v´egpont azonban egybe is eshet. A defin´ıci´o l´enyege, hogy minden ´el eset´en a v´egpontok sz´ama 1 vagy 2. Ahogy m´asodfok´ u egyenlet gy¨okein´el is szok´asos multiplicit´assal sz´amolunk ´es egy ´elnek mindig k´et v´egpontot tulajdon´ıtunk. Ha ez egy darab csucs, akkor az ´el dupl´an/k´etszeresen illeszkedik r´a. Defin´ıci´ o. Egy ´el hurok´el, ha k´et v´egpontja egybesik. ugyanazon k´et cs´ ucsot k¨otik ¨ossze.
K´et ´el p´arhuzamos, ha
Szok´asos egy hurok´elek, p´arhuzamos ´elek n´elk¨ uli gr´afot egyszer˝ u gr´afnak nevezni. A mi fel´ep´ıt´es¨ unk szerint ez nem teljesen jogos, hiszen egyszer˝ u gr´af ´eleinek le´ır´as´ahoz nem haszn´altunk illeszked´esi rel´aci´ot, ami viszont egy gr´af defini´aici´oj´anak r´esze. Ennek ellen´ere a k´et fogalom (egyszer˝ u gr´afok, hurok´elek ´es p´arhuzamos ´elek n´elk¨ uli gr´afok) azonos´ıthat´ok. Val´oban, egy hurok´elek ´es p´arhuzamos ´elek n´elk¨ uli gr´af ´elei azonos´ıthat´ok k´et v´egpontjuk ´altal alkotott r´eszhalmazzal. Illetve egy egyszer˝ u gr´af eset´en bevezethet˝o a vIe illeszked´es, ha v ∈ e teljes¨ ul. Term´eszetesen az egyszer˝ u gr´afokn´al bevezetett nyelvezet most is haszn´alhat´o. A lerajzol´as gr´afok eset´en is ugyan´ ugy megtehet˝o. S˝ot ez megmagyar´azza a hurok´el elnevez´est. Egy hurok´elnek olyan ´elg¨orbe felel meg, amely ugyanahhoz a karik´ahoz” ” ´erkezik ahonnan elindult, azaz hurkot alkot.
4. Foksz´ am A foksz´am egy cs´ ucsra illeszked˝o ´eleket sz´amolja meg a hurok´elek k´etszeres illeszked´es´et sz´amba v´eve: Defin´ıci´ o. Legyen G egy gr´af ´es v egy cs´ ucsa. Ekkor v foksz´ama (r¨oviden foka) 2|{e ∈ E : vIe ´es e hurok´el}| + |{e ∈ E : vIe ´es e nem hurok´el}| Egy gr´af lerajzol´as´an´al a foksz´am j´ol szeml´eltethet˝o. Nagy´ıt´oval n´ezz¨ uk meg egy cs´ ucsot reprezent´al´o karika k¨orny´ek´et. A karik´ab´ol indul´o/´erkez˝o g¨orb´ek egy napocskaszer˝ u” ´abr´at adnak. A napocska sugarainak sz´ama az aktu´alis cs´ ucs foka. ” Minden a cs´ ucsra illeszked˝o hurok´el k´et ´agat, nem hurok´el pedig egy a´gat ad ehhez a sz´aml´al´ashoz. Eljutottunkoda, hogy az els˝o gr´afelm´eleti t´etelt kimondjuk ´es bebizony´ıtsuk. 1. T´ etel. Tetsz˝oleges gr´afban az ¨osszes cs´ ucs foksz´am´anak ¨osszege az ´elsz´am k´etszerese. Formul´aval: X d(v) = 2|E|. v:v∈V
Gr´afelm´eleti alapfogalmak-5
Bizony´ıt´ as. Rajzoljuk le a gr´afot ´es minden ´elg¨orbe k´et v´egpontj´ahoz ´ırjunk egy-egy darab 1-est. H´any darab 1-est ´ırtunk le? M´ask´eppen: Adjuk o¨ssze a le´ırt 1-eseket. Az 1-esek le´ır´as´anak k´etf´ele strukt´ ur´aja van. Egyr´eszt ´elek mell´e ´ırjuk o˝ket, m´asr´eszt az ´elg¨orb´ek v´egeihez, azaz cs´ ucsok k¨or´e ´ırjuk ˝oket. A k´etf´ele megk¨ozel´ıt´es k´etf´ele v´alaszt ad. A kett˝onek meg kell egyezni. Ha az ´elek szerint csoportos´ıtjuk ˝oket (az ¨osszead´asos nyelvezetet k¨ovetve z´a” r´ojelezz¨ uk” ˝oket), akkor minden ´elre k´et darab 1-est tartalamz´o csoporthoz jutunk. Az 1-esek sz´ama 2|E|. Ha a cs´ ucsok szerint csoportos´ıtjuk az 1-eseket, akkor minden csoportban a megfelel˝o cs´ ucs foksz´ama adja az odaker¨ ul˝o 1-esek sz´am´at. A teljes o¨sszesz´amol´as v´egeredm´emnye a fokok ¨osszege lesz. A k´et sz´amol´as eredm´eny´enek egyez˝os´ege ´eppen a bizony´ıtand´ot adja. Nagyon r¨oviden cs´ ucs-´el illeszked´eseket sz´amoltuk ¨ossze k´etf´elek´eppen (tekintettel a multiplicit´asra) ´es a k´etf´ele eredm´emyt ¨osszevett¨ uk. N´eh´any k¨ovetkezm´eny: 2. K¨ ovetkezm´ eny. Tetsz˝oleges gr´afban az ¨osszes cs´ ucs foksz´am´at ¨osszeadva p´aros sz´amot kapunk. 3. K¨ ovetkezm´ eny. Tetsz˝oleges gr´afban a p´aratlan fok´ u cs´ ucsok sz´ama p´ aros. 4. K¨ ovetkezm´ eny. Ha egy gr´afban van p´aratlan fok´ u cs´ ucs, akkor lennie kell m´asiknak is.
Gr´afelm´eleti alapfogalmak-6
