Feladatok 1. H´ anyf´elek´eppen ´ allhat sorba n fi´ u ´es n l´ any u ´ gy, hogy azonos nem˝ uek ne ´alljanak egym´ as mellett? 2. H´ any olyan h´etsz´amjegy˝ u telefonsz´ am k´esz´ıthet˝o, amiben pontosan k´et k¨ ul¨onb¨ oz˝o sz´amjegy szerepel, ´es ezek egyike sem a 0? 3. H´ anyf´elek´eppen ´ allhat fel fot´oz´ashoz k´et egym´ as m¨og¨otti sorba 2n k¨ ul¨onb¨ oz˝o magass´ ag´ u ember u ´ gy, hogy minden h´ ats´ o sorban ´ all´ o magasabb legyen ann´al, aki az els˝ o sorban k¨ozvetlen¨ ul el˝otte ´all? 4. Jel¨ olje φ(n) az n-n´el kisebb, n-hez relat´ıv pr´ım pozit´ıv eg´eszek sz´am´ at. Bizony´ıtsuk be, hogy i az n pozit´ ıv eg´ e sz sz´ a m pr´ ımt´ e nyez˝ o s felbont´ a sa, akkor φ(n) = nΠki=1 (1− p1i ). ha n = Πki=1 pα i 5. Bizony´ıtsuk be, hogy Σni=0
n 2 i
=
2n n
.
¨ l´ 6. Ot any ´es h´ arom fi´ u r¨ oplabd´ azik. H´ anyf´elek´eppen oszthat´ok k´et n´egyf˝ os csapatba u ´ gy, hogy mindk´et csapatban legyen fi´ u? 7. T´ız rabl´o a kincseit egy t¨ obb lakattal lez´ arhat´o l´ ad´ aban gy˝ ujti. Az egyes lakatokat egy-egy (egym´ast´ ol elt´er˝ o) kulcs nyitja, ´es minden kulcsb´ol ak´ arh´ any p´eld´ any k´erhet˝o az al´abbiak el´er´es´ehez. A rabl´ok u ´ gy szeretn´ek kiosztani egym´ as k¨oz¨ott a kulcsokat, hogy b´ armely n´egy rabl´o gy˝ ulik ¨ ossze, ˝ ok egy¨ uttesen ki tudj´ak nyitni a l´ ad´ at, ugyanakkor ezt semelyik h´ arom rabl´o ne tudja megtenni. Minim´ alisan h´ any k¨ ul¨onb¨ oz˝o lakatra van sz¨ uks´eg ennek megval´os´ıt´ as´ ahoz? 8. Mutassuk meg, hogy egy v´eges egyszer˝ u gr´afnak mindig van k´et azonos foksz´ am´ u cs´ ucsa. 9. A Kov´acs h´ azasp´ ar h´ azibulit rendez, n´egy m´asik p´ art h´ıvnak meg, ´ıgy ¨osszesen t´ızen vannak. A r´esztvev˝ ok k¨oz¨ ul csak n´emelyek ismerik egym´ ast, m´asok nem, de term´eszetesen mindenki ismeri a h´ azast´ ars´ at. Kov´acs u ´ r megfigyeli, hogy ha a t¨ obbieket v´egigk´erdezn´e h´ any ismer˝os¨ uk van a jelenlev˝ ok k¨oz¨ott, mind a kilenc megk´erdezett m´as v´alaszt adna. Mondjuk meg, hogy ekkor h´ any ismer˝ ose van a jelenl´ev˝ ok k¨oz¨ott Kov´acsn´enak. (Felt´etelezz¨ uk, hogy az ismerets´egek k¨olcs¨ on¨ osek.) 10. Mutassuk meg, hogy tetsz˝ oleges v´eges egyszer˝ u gr´af p´ aros sok p´ aratlan foksz´ am´ u cs´ ucsot tartalmaz. 11. Bizony´ıtsuk be, hogy tetsz˝ oleges v´eges G gr´afra fenn´all, hogy |E(G)| ≥ |V (G)| − c(G), ahol c(G) a G gr´ af ¨ osszef¨ ugg˝ o komponenseinek sz´am´ at jel¨oli. 12. H´ any k¨ ul¨onb¨ oz˝o egyszer˝ u gr´ af adhat´ o meg n c´ımk´ezett ponton? 13. H´ any k¨ ul¨onb¨ oz˝o Hamilton-k¨ or van az n cs´ ucs´ u teljes gr´afban n ≥ 3 eset´en? (A pontokat c´ımk´ezettnek tekintj¨ uk.)
1
14. H´ any k¨ ul¨onb¨ oz˝o olyan fa adhat´ o meg n ≥ 4 c´ımk´ezett ponton, amelyben a nem-els˝ ofok´ u pontok sz´ ama pontosan kett˝ o? 15. H´ any k¨ ul¨onb¨ oz˝o olyan fa adhat´ o meg az 1, 2, . . . , 8 c´ımk´ezett cs´ ucsokon, ami az {1, 2}, {3, 4}, {5, 6}, {7, 8} teljes p´ aros´ıt´ as ´elei k¨oz¨ ul legal´ abb az egyiket nem tartamazza? 16. Mi lehet a G gr´ af, ha ∆(G) ≤ 2? 17. Legyen k ≤ n2 ´es jel¨ olje KG(n, k) a k¨ovetkez˝o gr´afot. KG(n, k) cs´ ucsai az {1, 2, . . . n} halmaz ¨osszes k-elem˝ u r´eszhalmazai. K´et cs´ ucs pontosan akkor van ¨osszek¨ otve, ha a k´et megfelel˝ o k-elem˝ u r´eszhalmaz diszjunkt. (KG(n, k) az n, k param´eter˝ u Kneser-gr´af.) Mutassuk meg, hogy a KG(5, 2) Kneser-gr´af izomorf a Petersen-gr´ affal. 18. Mutassuk meg, hogy ha egy n cs´ ucs´ u teljes gr´af ´eleit kisz´ınezz¨ uk k´et sz´ınnel, akkor biztosan keletkezik olyan r´eszgr´ afja, mely n cs´ ucs´ u fa, ´es minden ´ele azonos sz´ın˝ u. 19. Adjuk meg az ¨ osszes ¨ onkomplementer gr´afot ¨ot ´es hat ponton! 20. Adjuk meg az ¨ osszes ¨ onkomplementer f´at! 21. Tegy¨ uk fel, hogy T olyan fa, amelyhez hozz´ a lehet adni egyetlen ´elet u ´ gy, hogy az ´ıgy keletkez˝o gr´afban legyen z´ art Euler-s´eta. Mennyi a T -ben el˝ofordul´ o maxim´ alis foksz´ am? 22. Minim´ alisan h´ any t¨ or´essel t¨ orhet˝ o darabjaira egy 6 × 8-as t´ abla csokol´ad´e? 23. Adott r darab, egyenk´ent k cs´ ucs´ u pontdiszjunkt fa. H´ anyf´elek´eppen eg´esz´ıthet˝o ki ez az r fa egyetlen k · r cs´ ucs´ u f´ av´ a? (A kieg´esz´ıt´es u ´ gy ´ertend˝ o, hogy az r fa mindegyike r´eszgr´ afja lesz a keletkez˝o k · r cs´ ucs´ u f´ anak.) 24. Mennyi az optim´ alis k´ınai post´ as u ´ tvonal hossza a d dimenzi´ os hiperkocka gr´afj´ aban? 25. Egy gr´af cs´ ucsai egy 100 elem˝ u halmaz ¨osszes r´eszhalmazai az u ¨ res halmazt kiv´eve. K´et cs´ ucs pontosan akkor van ¨ osszek¨ otve, ha a megfelel˝ o halmazok egyike tartalmazza a m´asikat ´es az elemeik sz´ am´ anak k¨ ul¨onbs´ege 1. H´ any ´elb˝ ol ´all a legr¨ovidebb k´ınai post´ as u ´ tvonal ebben a gr´afban? 26. Legyen G olyan gr´ af, amiben minden foksz´ am 4. Bizony´ıtsuk be, hogy ekkor G ´elei kisz´ınezhet˝ ok k´et sz´ınnel, pirossal ´es k´ekkel, u ´ gy, hogy minden cs´ ucsba k´et piros ´es k´et k´ek ´el fusson be. 27. (R´edei t´etele) Mutassuk meg, hogy egy ir´ any´ıtott teljes gr´afban (tournamentben) mindig van ir´ any´ıtott Hamilton-´ ut. 28. Mutassuk meg, hogy egy ir´ any´ıtott teljes gr´afban (tournamentben) mindig van olyan pont, amib˝ol az ¨ osszes t¨ obbi legfeljebb k´et (az ´elek ir´ any´ıt´as´anak megfelel˝ o) l´ep´esben el´erhet˝o. 29. Mutassuk meg, hogy a KG(50, 3) Kneser-gr´af tartalmaz Hamilton-k¨ ort. (A Kneser-gr´af defin´ıci´ oj´ at ld. a 17. feladatn´ al.)
2
30. A G egyszer˝ u gr´ afr´ ol tudjuk, hogy d-regul´aris ´es a cs´ ucsainak sz´ama 2009. Mutassuk meg, hogy ha d > 1004, akkor G Hamilton-k¨ ort is ´es Euler-k¨ ort is tartalmaz. 31. A Gn gr´ af cs´ ucsai legyenek egy n elem˝ u halmaz ¨osszes r´eszhalmazai (a nem val´odi r´eszhalmazokat, teh´ at az u ¨ reshalmazt ´es a teljes halmazt is bele´ertve). K´et cs´ ucs pontosan akkor van ¨osszek¨ otve, ha a megfelel˝ o halmazok diszjunktak. Milyen n eset´en van a Gn gr´afban Euler-k¨ or, illetve Euler-´ ut? 32. A vil´ag 30 v´aros´ ar´ ol tudjuk, hogy ha kett˝ o k¨oz¨ott nincs k¨ozvetlen rep¨ ul˝oj´ arat, akkor a t¨ obbi huszonnyolc v´aros mindegyike k¨ozvetlen j´arattal el´erhet˝o valamelyik¨ ukb˝ ol, ´es legal´ abb k´et v´aros (szint´en a t¨ obbi huszonnyolc k¨oz¨ ul) mindkett˝ oj¨ ukb˝ ol. Bizony´ıtsuk be, hogy ekkor tehet˝o olyan k¨orutaz´ as rep¨ ul˝og´eppel, mely e harminc v´arost ´erinti (m´ ast nem), ´es mindegyiket pontosan egyszer, illetve a kiindul´ o v´arost a k¨orutaz´ as v´eg´en m´eg egyszer. 33. Egy hotelba egy 100 f˝ os t´ arsas´ ag ´erkezett, akik k¨oz¨ ul kezdetben b´ armely k´et ember j´oban volt egym´ assal. Est´enk´ent egyetlen nagy kerek asztal k¨or´e u ¨ l le mindenki vacsor´ azni. Sajnos egy-egy vacsora alkalm´aval az egym´ as mell´e ker¨ ult emberek ¨or¨okre ¨osszevesznek egym´ assal. A t´ arsas´ ag minden vacsora el˝ ott u ´ gy u ¨ l le, hogy mindenki j´oban legyen a szomsz´edaival. Ha ez lehetetlen, akkor az ¨ osszes r´esztvev˝ o m´eg aznap este hazamegy, el˝obb azonban nem. Bizony´ıtsuk be, hogy legal´ abb 25 ´ejszak´ at a hotelban t¨ olt a t´ arsas´ ag! 34. Egy G egyszer˝ u gr´ af cs´ ucsai v1 , . . . , v9 . Elk´esz´ıtj¨ uk bel˝ole a v1 , . . . , v9 , w1 , . . . , w9 cs´ ucsokon adott G′ gr´ afot a k¨ovetkez˝o m´odon. A vi ´es vj cs´ ucsok k¨oz¨ott pontosan akkor van ´el G′ -ben, ha ´el van k¨ozt¨ uk G-ben. A wi ´es wj cs´ ucsok minden i, j eset´en ¨osszek¨ otetlenek, v´eg¨ ul wi pontosan akkor van ¨ osszek¨ otve vj -vel, ha i 6= j. Tudjuk m´eg, hogy a G′ gr´af kromatikus sz´ama megegyezik a G gr´ af kromatikus sz´am´ aval. Megmondhat´ o-e ebb˝ol, hogy mi a G gr´af? 35. Legyen G a k¨ovetkez˝o gr´ af. V (G) = {1, 2, . . . , 2008} ´es k´et cs´ ucs pontosan akkor alkot ´elet, ha a nekik megfelel˝ o sz´ amok nem egyenl˝ ok ´es legnagyobb k¨oz¨os oszt´ojuk nagyobb 1-n´el. Mennyi G kromatikus sz´ ama? 36. Legyen G a k¨ovetkez˝o gr´ af. V (G) = {1, 2, . . . , 1023} ´es k´et cs´ ucs pontosan akkor alkot ´elet, ha az egyiknek megfelel˝ o sz´ am oszt´oja a m´asiknak megfelel˝ o sz´amnak (de a kett˝ o nem egyenl˝ o). Mennyi G kromatikus sz´ ama? 37. Legyen G olyan 2n + 1 cs´ ucs´ u gr´ af, amiben minden foksz´ am legal´ abb n. Mutassuk meg, hogy G tartalmaz Hamilton-utat. 38. Mutassuk meg, hogy egy r-regul´aris p´ aros gr´afban r ≥ 1 eset´en mindig van teljes p´ aros´ıt´as. 39. A G = (A, B; E) p´ aros gr´ afban |A| = |B| = m ´es az A-beli pontok d1 , . . . , dm foksz´ amaira di = i teljes¨ ul minden 1 ≤ i ≤ m eset´en. Bizony´ıtsuk be, hogy G-ben van teljes p´ aros´ıt´as. 40. Egy G = (A, B, E) egyszer˝ u p´ aros gr´afra |A| = |B| = n ´es ν(G) = k, ahol k ≤ n. Tudjuk tov´abb´a, hogy G ezen felt´etelek mellett a lehet˝o legt¨obb ´elet tartalmazza. H´ any ´ele van G-nek? Adjuk is meg G-t izomorfia erej´eig! 41. Mennyi a
τ (G) ν(G)
h´ anyados lehet˝ o legnagyobb ´ert´eke, ha G v´eges egyszer˝ u gr´af? 3
42. Bizony´ıtsuk be, hogy n cs´ ucs´ u egyszer˝ u gr´afra mindig f¨onn´all a 2ν(G) + α(G) ≥ n egyenl˝ otlens´eg. 43. Egy m´atrix dupl´ an sztochasztikus, ha minden eleme nemnegat´ıv, ´es az elemek ¨osszege minden sorban ´es minden oszlopban 1. Mutassuk meg, hogy dupl´ an sztochasztikus n´egyzetes m´atrix determin´ ans´ anak van pozit´ıv kifejt´esi tagja. 44. Egy szigeten n csal´ ad lakik. A sziget el¨olj´ar´oi felosztott´ak az eg´esz szigetet n egyenl˝ o ter¨ ulet˝ u vad´ aszati k¨orzetre ´es ezzel egyidej˝ uleg (az el˝obbit˝ol f¨ uggetlen¨ ul, ez´ert eg´eszen m´as m´odon) felosztott´ ak az eg´esz szigetet n egyenl˝ o ter¨ ulet˝ u mez˝ ogazdas´agi ter¨ uletre. Most azt szeretn´ek el´erni, hogy minden csal´ adhoz tartozzon egy vad´ aszati ´es egy mez˝ ogazdas´agi ter¨ ulet u ´ gy, hogy a k´et ter¨ uletnek legyen k¨oz¨os r´esze. Megoldhat´ o-e ez mindig? 45. Egy 7 × 7-es sakkt´ abla minden mez˝ oj´en u ¨ l egy m´okus. S´ıpsz´ora mindegyik ´atugrik egy a saj´atj´aval egyetlen cs´ ucsban ´erintkez˝o mez˝ ore. (Egy-egy mez˝ ore t¨ obben is ugorhatnak.) Minim´ alisan h´ any mez˝ o marad u ¨ resen? ¯ ≤ n + 1. 46. Legyen G n cs´ ucs´ u egyszer˝ u regul´ aris gr´af. Mutassuk meg, hogy ekkor χ(G) + χ(G) Mi az egyenl˝ os´eg felt´etele? ¯ nem teljes 47. Legyen G egy 2009 cs´ ucs´ u regul´ aris egyszer˝ u gr´af. Tegy¨ uk fel, hogy sem G, sem G ´ ¯ ¨osszeg ´ert´ek´et. gr´af. Allap´ ıtsuk meg a χe (G) + χe (G) 48. Mutassuk meg, hogy egy r-regul´aris p´ aros gr´af ´elhalmaza felbonthat´ o r darab diszjunkt teljes p´ aros´ıt´as uni´ oj´ ara. 49. Bizony´ıtsuk be, hogy ha G nem p´ aros gr´af, akkor megadhat´ ok a cs´ ucsain´ al olyan preferencia list´ ak, melyekre vonatkoz´oan G nem tartalmaz stabil p´ aros´ıt´ast! 50. Egy iskol´ aban k klub m˝ uk¨ odik, melyeknek di´akok a tagjai. Minden klubnak szeretn´enk a tagjai k¨oz¨ ul vezet˝ ot v´alasztani u ´ gy, hogy egy di´ak legfeljebb egy klubnak legyen a vezet˝ oje. Mutassuk meg, hogy annak sz¨ uks´eges ´es el´egs´eges felt´etele, hogy ez lehets´eges legyen az, hogy minden i ≤ k sz´ amra teljes¨ ulj¨on, hogy tetsz˝ oleges i klub tags´ag´anak uni´oja legal´ abb i di´akb´ ol ´ all. 51. Legyen G olyan v´eges egyszer˝ u, 3-regul´ aris gr´af, amely tartalmaz elv´ag´o´elet (azaz hidat). Mennyi G ´elkromatikus sz´ ama? 52. Mutassuk meg, hogy ha G p´ aratlan cs´ ucs´ u, legal´ abb egy ´elet tartalmaz´ o, egyszer˝ u regul´ aris gr´af, akkor G ´elkromatikus sz´ ama is p´ aratlan. 53. Legyen G olyan gr´ af, melynek kromatikus sz´ama 5, ´es tekints¨ uk G-nek egy j´o sz´ınez´es´et a piros, k´ek, z¨ old, s´ arga ´es lila sz´ınekkel. Mutassuk meg, hogy az ilym´odon sz´ınezett G-ben biztosan van olyan n´egy´ ag´ u csillag (teh´ at K1,4 ) r´eszgr´ af, melynek negyedfok´ u (teh´ at k¨oz´eps˝ o) pontja piros, a m´asik n´egy pontja pedig mind k¨ ul¨onb¨ oz˝ o sz´ın˝ u (vagyis az egyik k´ek, egy m´asik z¨ old, egy harmadik s´ arga ´es a negyedik lila). 54. Bizony´ıtsuk be, hogy tetsz˝ oleges v´eges egyszer˝ u G gr´afra fenn´all χ(G) ≥ 4
|V (G)| α(G) .
¯ ≥ n. 55. Bizony´ıtsuk be, hogy ha G egy n cs´ ucs´ u v´eges egyszer˝ u gr´af, akkor χ(G)χ(G) 56. Jel¨ olje Mk a Mycielski-konstrukci´ oval kapott azon gr´afot, melynek kromatikus sz´ama k. (M2 a k´et cs´ ucsot ´es egyetlen ´elet tartalmaz´ o gr´af, M3 az 5 hossz´ u, h´ ur n´elk¨ uli k¨or.) Bizony´ıtsuk be, hogy k > 2 eset´en ν(Mk ) = |V (M2k )|−1 . 57. Jel¨ olje Mk a Mycielski-konstrukci´ oval kapott azon gr´afot, melynek kromatikus sz´ama k. Milyen k ´ert´ekekre tartalmaz Mk Euler-k¨ ort? 58. Jel¨ olje Mk ism´et a k-adik Mycielski-gr´ afot. Milyen k ´ert´ekekre tartalmaz Mk Hamilton-k¨ ort? 59. Mutassuk meg, hogy χ(G) ≤ τ (G) + 1. 60. Bizony´ıtsuk be, hogy minden gr´ afra fenn´all, hogy χ(G) ≤ max{δ(G′ ) : G′ ⊆ G} + 1, ahol δ(F ) az F gr´ af minim´ alis foksz´ am´ at jel¨oli. 61. Bizony´ıtsuk be, hogy tetsz˝ oleges v´eges egyszer˝ u gr´afra fenn´all, hogy |E(G)| ≥
χ(G) 2
.
62. Bizony´ıtsuk be, hogy ha G egy n cs´ ucs´ u v´eges egyszer˝ u gr´af, melynek foksz´ amai d1 , d2 , . . . , dn , akkor Σni=1 di ≥ χ(G)(χ(G) − 1). 63. Bizony´ıtsuk be, ucs´ u v´eges egyszer˝ u gr´af, melynek foksz´ amai d1 , d2 , . . . , dn , hogy ha G egy n cs´ akkor Σni=1 d2i ≥ χe 2(G) . |V (G)| 64. Mutassuk meg, hogy tetsz˝ oleges v´eges egyszer˝ u gr´afra f¨onn´all az α(G) ≥ ∆(G)+1 egyenl˝ otlens´eg. (Szok´ as szerint α(G) a f¨ uggetlen pontok maxim´ alis sz´ama, ∆(G) pedig a maxim´ alis foksz´ am G-ben.)
65. Mutassuk meg, hogy χ(KG(n, k)) ≤ n−2k+2, ahol KG(n, k) az n, k param´eter˝ u Kneser-gr´af. (A Kneser-gr´af defin´ıci´ oj´ at ld. a 17. feladatn´ al. Az ott le´ırt defin´ıci´ ohoz h´ıven, feltessz¨ uk, hogy n ≥ 2k.) 66. Legyen adva a s´ıkon v´eges sz´ am´ u egyenes, melyek k¨oz¨ ul semelyik h´ arom sem metszi egym´ ast egy pontban. Tekints¨ uk az egyenesek metsz´espontjait egy G gr´af cs´ ucsainak, ´es ugyanezen gr´af ´elei legyenek az egyes egyeneseken szomsz´edosan elhelyezked˝ o metsz´espontokb´ ol l´eterej¨ ott cs´ ucsp´ arok. Mutassuk meg, hogy χ(G) ≤ 3. 67. Mutassuk meg, hogy tetsz˝ oleges G gr´af cs´ ucsainak van olyan sorrendje, amely sorrendben moh´ on sz´ınezve a cs´ ucsokat optim´ alis sz´ınez´est kapunk. Mutassuk meg azt is, hogy tetsz˝ oleges k sz´amhoz l´etezik olyan p´ aros gr´ af ´es cs´ ucsainak olyan sorrendje, hogy ebben a sorrendben moh´ on sz´ınezve a gr´ afot, a felhaszn´alt sz´ınek sz´ama k-n´al nagyobb lesz. ¯ = ω(G), ¯ vagyis G komplementer´eben a 68. Mutassuk meg, hogy ha G p´ aros gr´ af, akkor χ(G) kromatikus sz´ am ´es a klikksz´ am egyenl˝ o.
5
69. Legyen G k-kromatikus gr´ af. (Ez annyit jelent, hogy χ(G) = k). Legyen A ⊆ V (G) olyan r´eszhalmaza a cs´ ucsoknak, amire ∀a, b ∈ A eset´en az a ´es b pontok t´ avols´ aga G-ben legal´ abb 4. Bizony´ıtsuk be, hogy az A-beli cs´ ucsok tetsz˝ oleges, legfeljebb k + 1 sz´ınt felhaszn´al´o sz´ınez´ese kieg´esz´ıthet˝ o G-nek egy legfeljebb k + 1 sz´ınt felhaszn´al´o j´o sz´ınez´es´ev´e. 70. Legyen G1 ´es G2 k´et v´eges egyszer˝ u gr´af, melyek kromatikus sz´ama h´ arom. Defini´aljuk ´altaluk az al´ abbi F gr´ afot. F cs´ ucsai az ¨osszes olyan rendezett (u, v) p´ arok, melyekre u ∈ V (G1 ) ´es v ∈ V (G2 ). K´et ilyen cs´ ucs, (u1 , v1 ) ´es (u2 , v2 ) akkor ´es csak akkor van ¨osszek¨ otve F ben, ha {u1 , u2 } ∈ E(G1 ) ´es {v1 , v2 } ∈ E(G2 ) is teljes¨ ul. Bizony´ıtsuk be, hogy F kromatikus sz´ama is h´ arom. 71. Bizony´ıtsuk be, hogy K1,3 nem lehet fesz´ıtett r´eszgr´ afja semmilyen v´eges egyszer˝ u gr´af ´elgr´afj´ anak. 72. Mennyi Kn ´elkromatikus sz´ ama? 73. Mennyi az n-cs´ ucs´ u teljes gr´ af ´elgr´ afja komplementer´enek kromatikus sz´ama? (R¨ oviden: χ(L(Kn ) =?) 74. Legyen a G gr´ af a h´ aromdimenzi´ os kocka ´elh´ al´ozat´ anak gr´afja, melyen jel¨olj¨ uk ki egy test´atl´ o k´et ´atellenes cs´ ucs´ at, melyeket s-sel ´es t-vel jel¨ol¨ unk. Legyenek az ´elek u ´ gy ir´ any´ıtva, hogy s-hez k¨ozelebbi cs´ ucsukb´ ol mutassanak az s-t˝ol t´ avolabbiba. Az ´ıgy megadott ir´ any´ıtott gr´af legyen egy h´ al´ ozat gr´ afja, melyben s a forr´ as ´es t a nyel˝o. A kapacit´ asokat u ´ gy kell megadnunk, hogy n´egy ´el kapacit´ asa 1 egys´eg, n´egy ´el kapacit´ asa 2 egys´eg ´es n´egy ´el kapacit´ asa 3 egys´eg legyen, tov´abb´a, hogy a h´ al´ ozat ´atereszt˝ ok´epess´ege maxim´ alis legyen ezen felt´etelek mellett. Mekkora lesz az ´ıgy kapott h´ al´ozatban megadhat´ o maxim´ alis folyam? 75. Egy h´ al´ ozat gr´ afja az {1, 2, . . . , n} cs´ ucsokon adott ir´ any´ıtott teljes gr´af, melynek minden ´ele a kisebb c´ımk´ej˝ u cs´ ucsb´ ol a nagyobb c´ımk´ej˝ u fel´e van ir´ any´ıtva. A forr´ as az 1, a nyel˝o az n c´ımk´et visel˝ o cs´ ucs. Az (i, j) ´el kapacit´ asa j − i minden i < j p´ arra. Mekkora a h´ al´ozatban megadhat´ o maxim´ alis folyam ´ert´eke? 76. A G gr´af cs´ ucsai legyenek az n hossz´ us´ag´ u 0 − 1 sorozatok, ´es az x = x1 . . . xn sorozatb´ ol mutasson ´el az y = y1 . . . yn sorozatba, ha a k´et sorozat pontosan egy koordin´at´aban k¨ ul¨onb¨ ozik ´es erre az i koordin´ at´ara xi = 0, yi = 1 ´all. Az ´ıgy kapott ´el kapacit´ asa legyen egyenl˝ o i-vel. Legyen s = (0 . . . 0), t = (1 . . . 1). Mutassuk meg, hogy az ´ıgy megadott (G, s, t, c) h´ al´ozatban a maxim´ alis folyam ´ert´eke semmilyen n-re nem nagyobb 2n−1 -n´el, n ≥ 5 eset´en pedig hat´ arozottan kisebb ann´al. 77. Legyen G 3-regul´ aris gr´ af, amire χe (G) = 3. Tudjuk tov´abb´a, hogy G ´eleinek (a sz´ınek egym´ as k¨oz¨otti trivi´ alis permut´ aci´ oj´ at´ol eltekintve) egyetlen j´o h´ arom sz´ınnel val´o sz´ınez´ese l´etezik. Bizony´ıtsuk be, hogy G-nek van Hamilton-k¨ ore. 78. Mutassuk meg, hogy ha G ¨ osszef¨ ugg˝o r-regul´aris p´ aros gr´af, aminek legal´ abb h´ arom cs´ ucsa van, akkor G k´etszeresen is ¨ osszef¨ ugg˝o. 79. Mutassuk meg, hogy ha egy 3-regul´ aris gr´af 3-szorosan ´el¨osszef¨ ugg˝o, akkor h´ aromszorosan ¨osszef¨ ugg˝ o is. 6
80. Mutassuk meg, hogy ha G1 ´es G2 k´et gr´af ugyanazon a V cs´ ucshalmazon ´es G1 ∪ G2 a (V, E(G1 ) ∪ E(G2 )) m´odon megadhat´ o gr´afot jel¨oli, akkor χ(G1 ∪ G2 ) ≤ χ(G1 )χ(G2 ). 81. Mutassuk meg, hogy 2n−1 darab 0 ´es 2n−1 darab 1-es elrendezhet˝ o olyan ciklikus sorrendben, hogy az ´ıgy kapott k¨or ment´en egym´ as mellett ´all´ o bin´ aris sz´amjegyekb˝ ol l´etrej¨ov˝ o bin´aris n-esek k¨oz¨ott mind a 2n lehets´eges bin´aris n-es pontosan egyszer el˝oforduljon.
7
