Paulovics Zoltán
A cikk egy feladatsorozaton keresztül meséli el, hogyan jött rá a szerző egy Erdős Pálhoz köthető, kisebb állításra. A cikk elsősorban azoknak lehet hasznos, akik már ismernek néhány, a gráfokkal kapcsolatos alapfogalmat – de ennyi elég is, a megértéséhez nincs szükség további gráfelméleti ismeretekre. Aki megoldja az egymásra épülő feladatokat, az joggal állíthatja, hogy ő is bebizonyította ezt a tételt!
Még élénken él bennem az, ahogyan először találkoztam a gráfelmélettel. A Zalaegerszegi Zrínyi Miklós Gimnázium diákjaként néha betévedtem a könyvtárba, és a matekos részlegen nézegettem a könyveket. Ifjú kilencedikesként lenyűgözött a rengeteg könyv számomra érthetetlen címe, és csak reméltem, hogy talán valamikor majd megérthetem őket. Egyszer Andrásfai Béla Ismerkedés a gráfelmélettel című művét emeltem le a polcról, és nézegettem a már tizenöt évvel ezelőtt is nagyon réginek tűnő könyvet. (Az 1971-es kiadással találkoztam.)
Egy teljesen új világ tárult fel előttem. Nem sokkal később találtam más, újabb könyveket is, amelyeket nyáron olvasgatva elmerülhettem a témában. Andrásfai Béla könyvének ez a feladata valamiért nagyon megfogott:
1. feladat. Bizonyítsuk be, hogy bármely tetszőlegesen irányított teljes gráfban van olyan pont, amelyből a gráf bármely más pontja elérhető 2-nél nem hosszabb irányított úttal. ([3] 58. o. 16. feladat)
Sokáig gondolkoztam rajta, de nem tudtam megoldani, és végül feladtam. Megnéztem a megoldás első gondolatát, megértettem, és a homlokomra csaptam: „Ó, ez milyen egyszerű!” Kicsit csalódott voltam, hogy nem jöttem rá magamtól, de kárpótolt a megoldás szépsége: annyira egyszerű és frappáns volt!
Aki nem ismeri a feladat megoldását, és van kedve gondolkodni rajta, az még ne nézze meg a máris következő bizonyítást.
1 pontú gráfra igaz az állítás. Legyen \(\displaystyle \overrightarrow{T_n}\) egy \(\displaystyle n \ (>1)\) pontú irányított teljes gráf, az \(\displaystyle (x; y)\) jelölés azt az élet jelenti, amelynek az \(\displaystyle x\) pont a kezdőpontja és az \(\displaystyle y\) pont a végpontja. Válasszuk ki a gráfnak egy olyan \(\displaystyle v\) csúcsát, amely maximálisan sok kilépő éllel rendelkezik, azaz maximális a „kifoka”, jelölje ezt a maximumot \(\displaystyle k\). Indirekt módon bebizonyítjuk, hogy \(\displaystyle v\) megfelel a feladat követelményeinek. Jelölje a \(\displaystyle v\) kezdőpontú élek végpontját \(\displaystyle v_1, v_2, \ldots, v_k\) (1. ábra). Tegyük fel tehát, hogy \(\displaystyle v\) nem felel meg, azaz van \(\displaystyle \overrightarrow{T_n}\)-nek olyan \(\displaystyle u\) pontja, ahová sem egy (irányított) élen, sem két egymáshoz csatlakozó élen nem lehet eljutni \(\displaystyle u\)-ból, azaz a következő élek nem fordulnak elő a gráfban:
\(\displaystyle (v;u), (v_1;u), (v_2;u), \ldots, (v_k;u). \)
1. ábra
Mivel az irányítás nélküli \(\displaystyle T\) gráfban bármely két különböző pont szomszédos, ezért ezeknek az éleknek nem vég-, hanem kezdőpontja az \(\displaystyle u\), így szükségképpen szerepelnek \(\displaystyle \overrightarrow{T_n}\)-ben a következő élek:
\(\displaystyle (u;v), (u;v_1), (u;v_2), \ldots, (u;v_k). \)
Tehát \(\displaystyle v\) legalább \(\displaystyle k+1\) élnek a kezdőpontja, tehát \(\displaystyle v\) kifoka \(\displaystyle (k)\) nem lehetett maximális, ami ellentmondás. \(\displaystyle \Box\)
Eltelt pár év, és az ELTE Matematika BSc szakon újra találkoztam ezzel a feladattal, igaz kicsit más köntösben. Azt észrevettem, hogy ez nem más, mint az a régi feladat, de a megoldásra már nem emlékeztem, így örömet okozott, hogy most meg tudtam oldani.
2. feladat Bizonyítsuk be, hogy minden tournamentben létezik pszeudogyőztes.
Na, de mi is az a tournament? És ki a pszeudogyőztes?
A tournament szó angolul bajnokságot jelent, ezért szokás az \(\displaystyle n\) csúcsú irányított teljes gráfot tournamentnek nevezni, és általában \(\displaystyle T_n\)-nel jelölni (esetleg \(\displaystyle \overrightarrow{T_n}\)-nel). Hiszen ha van egy olyan versenyünk, ahol az \(\displaystyle n\) résztvevő közül mindenki mindenkivel pontosan egyszer játszik, és döntetlen nem alakul ki, akkor azt egy \(\displaystyle n\) csúcsú irányított teljes gráffal jól modellezhetjük. A csúcsok a versenyzők, továbbá az \(\displaystyle u\) csúcsból irányított él megy a \(\displaystyle v\) csúcsba, ha az \(\displaystyle u\)-nak megfelelő játékos legyőzte a \(\displaystyle v\)-nek megfelelő játékost.
Pszeudogyőztesnek nevezünk egy csúcsot, ha minden másik csúcsba vezet belőle legfeljebb kettő hosszú irányított út (a nemzetközi szakirodalomban királynak is nevezik). Azaz – a versenyt modellező példával megfogalmazva – a pszeudogyőztes egy olyan versenyző, aki minden másik játékost vagy legyőzött, vagy legyőzött valakit, aki az őt legyőzőt legyőzte.
Könnyen látható, hogy csak a megfogalmazás tér el egymástól: az 1. és a 2. feladat igazából ugyanaz.
Később megtudtam, hogy ez a feladat Landau [1] nevéhez köthető, aki azt látta be 1953-ban, hogy bármelyik legnagyobb kifokú csúcs pszeudogyőztes (habár a megfogalmazásban ő még nem ezt a nyelvezetet használta).
Érdemes itt egy kicsit megállni, és felrajzolni, hogyan is néz ki tehát a tournamentek struktúrája, honnan merre mennek élek.
A \(\displaystyle v\) csúcsból kimutató élek végpontjainak halmazát jelölje \(\displaystyle N^+(v)\), míg a \(\displaystyle v\)-be mutató élek kezdőpontjainak halmazát \(\displaystyle N^-(v)\) (2. ábra). A feladat(ok) szerint tehát egy tournament csúcshalmaza három részre osztható az alábbiak szerint: egy \(\displaystyle v\) maximális kifokú csúcsra, valamint \(\displaystyle N^+(v)\) és \(\displaystyle N^-(v)\) halmazokra. Avagy más megfogalmazásban: \(\displaystyle N^+(v)\) (illetve \(\displaystyle N^-(v)\)) jelöli a \(\displaystyle v\)-ből 1 hosszú úton elérhető (illetve 1 hosszú úton nem, de 2 hosszún elérhető) csúcsok halmazát. \(\displaystyle N^+(v)\) csúcshalmazon belül, illetve \(\displaystyle N^-(v)\) csúcshalmazon belül bárhogyan mehetnek az élek, viszont minden \(\displaystyle N^+(v)\) és \(\displaystyle N^-(v)\) közötti él \(\displaystyle N^+(v)\)-ből \(\displaystyle N^-(v)\) felé van irányítva. Mivel bármely csúcsnál a kiinduló és befutó élek száma összesen \(\displaystyle n-1\), ezért ha \(\displaystyle v\) egy maximális kifokú csúcs, úgy \(\displaystyle N^+(v) \geq \frac{n-1}{2}\), és így \(\displaystyle N^-(v) \leq \frac{n-1}{2}\).
Természetesen előfordulhat, hogy a 2. szint hiányzik, tehát \(\displaystyle N^-(v)\) üres halmaz. Ekkor a \(\displaystyle v\) csúcs kifoka \(\displaystyle n-1\).
Tegyünk itt egy kis kitérőt, és nézzük meg a KöMaL 2025. februári számában megjelent C.1844-es feladatot!
3. feladat. (C. 1844.) Ági pirossal, Laci kékkel színezgeti az \(\displaystyle n \times n\)-es (\(\displaystyle n>1\)) fehér táblázatuk mezőit, mely \(\displaystyle i\)-edik sorának \(\displaystyle j\)-edik mezőjét \(\displaystyle (i;j)\)-vel jelöljük. Első lépésben Ági pirosra festi a főátló (bal felsőtől a jobb alsóig) mezőit. Ezután felváltva jönnek: ha Laci \(\displaystyle (i;j)\)-t színezi, akkor Ági \(\displaystyle (j;i)\)-t. Minden mezőt pontosan egyszer színeznek be. A \(\displaystyle k\)-adik sort különlegesnek hívjuk, ha bármely kék \(\displaystyle (k;j)\) esetén létezik \(\displaystyle l\), hogy \(\displaystyle (k;l)\) és \(\displaystyle (l;j)\) is piros. Bizonyítsuk be, hogy a színezgetés végeztével Ági talál különleges sort.
Javaslom, hogy aki első olvasásra nem jött rá, hogy ez a feladat is pontosan ugyanaz, mint az első kettő, az olvassa el még egyszer, mielőtt megnézné a következő megfeleltetést!
4. ábra. A különlegesség feltétele:bármely kék \(\displaystyle (k;j)\) esetén létezzen \(\displaystyle l\), hogy \(\displaystyle (k;l)\) és \(\displaystyle (l;j)\) is piros
Bevezetjük a szomszédsági mátrix (vagy másnéven adjacencia-mátrix) fogalmát, amely egy lehetséges formája a gráfok elkódolásának. Adott egy \(\displaystyle n\) csúcsú, egyszerű gráf, csúcsai az \(\displaystyle 1, 2, \ldots, n\) pozitív egészekkel vannak címkézve. Ekkor egy \(\displaystyle {n \times n}\)-es táblázat \(\displaystyle i\)-edik sorának \(\displaystyle j\)-edik mezőjébe – \(\displaystyle (i;j)\) – írjunk \(\displaystyle 1\)-et, ha mutat él az \(\displaystyle i\) csúcsból a \(\displaystyle j\) csúcsba, különben pedig \(\displaystyle 0\)-át. (Ha a gráf nem egyszerű, úgy az a szám kerül oda, ahány éllel össze van kötve az \(\displaystyle i\) és a \(\displaystyle j\) csúcs.) Rögtön látható, hogy a táblázatunk szimmetrikus (a ,,főátlóra''), azaz \(\displaystyle (i;j)\)-be és \(\displaystyle (j;i)\)-be ugyanaz a szám kerül. Ha viszont a gráf irányított, akkor nem feltétlenül lesz szimmetrikus, mert irányított gráf esetén ha az \(\displaystyle i\) csúcsból mutat él a \(\displaystyle j\) csúcsba, de fordítva nem, akkor \(\displaystyle (i;j)\)-be \(\displaystyle 1\)-et írunk, \(\displaystyle (j;i)\)-be viszont \(\displaystyle 0\)-át. (Egy legalább kétpontú tournament szomszédsági mátrixa például soha sem lesz szimmetrikus.)
Például az 5. ábra jobb oldali gráfjának adjacencia-mátrixa a középső számtáblázat.
5. ábra. Színes táblázat, szomszédsági mátrix, irányított gráf
Ennek alapján jól látható, hogy minden színezés ekvivalens egy \(\displaystyle n\) csúcsú irányított gráffal, ahol az, hogy egy \(\displaystyle (i;j)\) mező piros, azt jelenti, hogy az \(\displaystyle i\)-ből él megy \(\displaystyle j\)-be, kivéve az \(\displaystyle (i,i)\) számozású piros mezőket (5. ábra). Ekkor a különleges sor létezése éppen a pszeudogyőztes létezésének felel meg.
A KöMaL múlt havi számában megjelent a C.1844-es feladat mintamegoldása, ebben több szép megoldás is olvasható. A teljesség kedvéért itt is közlünk egy (nagyon tömör) bizonyítást.
A 3. feladat megoldása. Indirekt módon bizonyítunk: tegyük fel, hogy Ági nem talál különleges sort, azaz bármely \(\displaystyle k\) sorra teljesül, hogy létezik olyan \(\displaystyle j\), melyre \(\displaystyle (k;j)\) kék, és ha valamely \(\displaystyle l\)-re \(\displaystyle (k;l)\) piros, úgy \(\displaystyle (l;j)\) kék. Ha viszont \(\displaystyle (l;j)\) kék, akkor \(\displaystyle (j;l)\) piros. Azaz, ha \(\displaystyle k\) sorában az \(\displaystyle l\) oszlop piros, akkor \(\displaystyle j\) sorában is piros. Azaz a \(\displaystyle j\)-edik sorban legalább annyi piros van, mint a \(\displaystyle k\)-adik sorban. Sőt, több is, hiszen \(\displaystyle (k;j)\) kék, míg \(\displaystyle (j;k)\) piros. Ebből következik, hogy bármely sorhoz létezik olyan sor, amelyben több piros mező található, mint benne. Mivel véges sok sor van, ezért ez ellentmondás. \(\displaystyle \Box\)
Visszakanyarodva az egyetemi évekhez, az MSc alatt megint találkoztam ezzel a feladattal. Régi ismerősként üdvözöltem, felelevenítettem a megoldást, majd olyat tettem, amit addig egyszer sem: elgondolkoztam, hogyan lehetne általánosítani, milyen variánsát tudnám bizonyítani. Például igaz lehet, hogy minden tournamentben létezik legalább két pszeudogyőztes? Feltéve persze, hogy van legalább két csúcs. És három, ha van legalább három csúcs?
Most is javasoljuk a megoldást nem ismerőknek, hogy továbbolvasás előtt próbálják meg magunk megválaszolni a kérdéseket.
Persze, ha létezik olyan csúcs, amelyből \(\displaystyle n-1\) él indul ki (az ilyen \(\displaystyle n-1\) kifokú csúcsot abszolút győztesnek nevezzük), akkor csak egy pszeudogyőztes létezik a tournamentben, ez a csúcs. De ha nincs ilyen? Akkor bizony lesz legalább két pszeudogyőztes.
4. feladat. Ha egy tournamentben nincs abszolút győztes, akkor létezik legalább két pszeudogyőztes.
Vegyük észre, hogy nem kell explicit módon megkövetelnünk az állítás feltételeiben a két csúcs létezését, hiszen ez abból, hogy nincs abszolút győztes, már következik. (Az egy csúcsú tournament egyetlen csúcsa abszolút győztes.)
A bizonyítás első lépésében a már ismert módon találunk egy pszeudogyőztest. A második lépésben pedig a 3. ábra alapján rájöhetünk, hogy hol kell keresni a másodikat. Érdemes kitalálni magunktól, mert az ábra alapján nem nehéz, és a későbbiekre nézve döntő jelentőségű lesz ez az észrevétel!
Bizonyítás. Mivel nincs abszolút győztes, így a tournamentünk tényleg az 1. ábra szerinti, vagyis \(\displaystyle N^-(v)\) sem üres halmaz, és mindegyik csoportból indul ki él. Azt állítjuk, hogy \(\displaystyle N^+(v)\) elemei között találunk pszeudogyőztest!
Az \(\displaystyle N^+(v)\)-ből való csúcsokat csak akkor van esélyünk ugyanerről a szintről legfeljebb kettő hosszú irányított úton elérni, ha a „szinten maradunk”, azaz nem lépünk ki \(\displaystyle N^+(v)\)-ből. Melyik csúcsot válasszuk \(\displaystyle N^+(v)\) csúcsai közül? Természetes módon adódik, hogy ugyanazt az ötletet alkalmazzuk, amit az előbb is. Hiszen \(\displaystyle {N^+(v)}\) csúcsai a köztük lévő élekkel együtt szintén egy tournamentet alkotnak (az eredeti egy résztournamentjét), az 1. feladatban pedig láttuk, hogy a maximális kifokú csúcs választásával a résztournament egy pszeudogyőztesét találjuk meg. Ez a csúcs a kezdeti tournamentünkben is pszeudogyőztes lesz, hiszen belőle minden \(\displaystyle N^-(v)\)-beli csúcsba egy, \(\displaystyle v\)-be pedig kettő hosszúságú irányított út vezet. \(\displaystyle \Box\)
Ha egy üzlet beindul... Találhatunk hármat is? Moon 1968-ban bebizonyította, hogy amennyiben nincs abszolút győztes, úgy mindig létezik legalább három pszeudogyőztes [2]. A fentiek után könnyen bizonyítható az állítás.
5. feladat. Ha egy tournamentben nincs abszolút győztes, akkor létezik három pszeudogyőztes.
Bizonyítás (vázlat). Az egy-, illetve kétcsúcsú tournamentben mindig van abszolút győztes, vagyis a gráfnak legalább három csúcsa van. Most ne az 1. szinten nézzünk körül, hanem a 2. szinten, tehát \(\displaystyle N^-(v)\) csúcsai között. Ez nemüres, a csúcsok a köztük lévő élekkel együtt szintén tournamentet alkotnak, így az 1. feladat miatt itt is fogunk találni olyan csúcsot, ami \(\displaystyle N^-(v)\)-n pszeudogyőztes. Könnyű látni, hogy ez a csúcs az eredeti tournamentben is pszeudogyőztes lesz. \(\displaystyle \Box\)
Természetes módon adódik a kérdés, hogy van-e mindig négy pszeudogyőztes. És öt? Hiszen ha az 1. és a 2. szinten vannak még további csúcsok, akkor ott akár találhatnánk még pszeudogyőzteseket!
A válasz viszont az, hogy az 5. feladat állítása éles: konstruálható olyan abszolút győztest nem tartalmazó tournament, amelyben csak három pszeudogyőztes van. (Már öt csúcs esetén is létezik ilyen tournament, érdemes rajzolni egyet.) Cserébe viszont az is igaz – miként ezt 1982-ben Reid igazolta [4] –, hogy néhány kivételtől eltekintve tetszőleges \(\displaystyle k\) és \(\displaystyle n\) esetén meg lehet adni egy olyan \(\displaystyle n\)-csúcsú tournamentet, amelyben \(\displaystyle k\) pszeudogyőztes csúcs van, ha \(\displaystyle n \geq k\). A „két” kivétel:
[labelwidth=3mm]
Mivel nem tudtam továbbmenni \(\displaystyle 4\)-re, ezért azon gondolkoztam el, hogy ezzel a hárommal mit tudnék kezdeni. A pszeudogyőztes definíciója úgy szólt, hogy legfeljebb \(\displaystyle 2\)-hosszú irányított úton minden más csúcs elérhető belőle. Vajon a pszeudogyőztesek halmazából minden más csúcs elérhető \(\displaystyle 1\)-hosszú irányított úton? Azaz bármely, a halmazon kívüli csúcsba vezet valamely pszeudogyőztesből él? Egy (irányított) gráf csúcsainak olyan halmazát, melyből minden más csúcsba vezet él, domináló halmaznak nevezzük. (Ilyen csúcshalmaza több is lehet a gráfnak.) Egy \(\displaystyle G\) gráf legkisebb domináló halmazának elemszáma \(\displaystyle G\) dominálási száma, amelyet \(\displaystyle \gamma(G)\)-vel jelölünk.
6. feladat. Egy tournamentben a pszeudogyőztesek domináló halmazt alkotnak.
Bizonyítás (vázlat). Az 1. ábrát nézve nyilvánvaló az állítás: ha a pszeudogyőztesek halmazától lenne néhány (legalább egy) 2 távolságra lévő csúcs, akkor e csúcs(ok) között is lenne pszeudogyőztes. \(\displaystyle \Box\)
Mielőtt a célegyenesbe érkeznénk, még vegyük be a kanyart, és mutassunk egy könnyen adódó felső becslést a tournamentek dominálási számára.
7. feladat. (C. 1865.) Az iskolai szkanderbajnokságon \(\displaystyle 17\) fő indult el. Mindenki pontosan egyszer játszott mindenkivel, döntetlen nem született. A versenyzők egy csoportját erősnek hívjuk, ha teljesül rájuk, hogy bármely rajtuk kívüli versenyzőt legyőzött közülük valaki. Bizonyítsuk be, hogy kiválasztható legfeljebb \(\displaystyle 9\) fős erős csoport.
Ennek a feladatnak is megjelent a mintamegoldása a KöMaL múlt havi számában. Az ott szereplő bizonyításokból azt az észrevételt most külön is megfogalmazzuk, hogy a(z egyik) legtöbb győzelmet arató diák és az őt legyőzők halmaza erős lesz és legfeljebb \(\displaystyle 9\) elemű. Ennek általánosítása feladatként így hangzik:
8. feladat. Mutassuk meg, hogy ha \(\displaystyle T_n\) egy \(\displaystyle n\)-csúcsú tournament, akkor
\(\displaystyle {\gamma (T_n) \leq \frac{n+1}{2}}. \)
A speciális eset bizonyításában szereplő gondolat pedig általánosan is használható: az egyik maximális kifokú \(\displaystyle v\) csúcs és az \(\displaystyle N^-(v)\) csúcshalmaz elemei nyilván domináló halmazt alkotnak, hiszen \(\displaystyle v\) az \(\displaystyle N^+(v)\) minden elemét legyőzte, és ez a halmaz legfeljebb \(\displaystyle \frac{n-1}{2}+1=\frac{n+1}{2}\) elemű.
De ennél erősebbet is lehet állítani \(\displaystyle \gamma(T_n)\)-ről. Ekkor persze nem érdemes bevenni a teljes \(\displaystyle N^-(v)\) csúcshalmazt, hiszen az nagy méretű is lehet. Mit válasszunk helyette?
Akinek van kedve törnie a fejét ezen, az a következő feladatnak még az állítását se nézze meg, hanem gondolkozzon el azon, hogy ha \(\displaystyle v\)-t kiválasztottuk, akkor hol érdemes keresni további pszeudogyőzteseket, és legfeljebb mennyit érdemes kiválasztani, hogy minimális számú csúcsból álló domináló halmazt kapjunk. Akinek ez sikerült, az már el is jutott Erdős Pál állításához.
Az igazság az, hogy Erdős sohasem publikálta ezt az eredményt – talán mert túl egyszerűnek tartotta ahhoz –, de a szakirodalom egységesen neki tulajdonítja: például a [6] cikk absztraktjának legelső sora állítja, hogy Erdős az [5] cikkben publikálta ezt az eredményt. [7] is Erdősnek tulajdonítja, és közli a bizonyítást is.
9. feladat. (Erdős Pál tétele) Ha \(\displaystyle T_n\) egy \(\displaystyle n\)-csúcsú tournament, akkor
\(\displaystyle \gamma (T_n) \leq \lceil \log_2 n \rceil. \)
Bizonyítás. Legyen \(\displaystyle v_1\) egy maximális kifokú csúcs. A korábbiak szerint \(\displaystyle v_1\) pszeudogyőztes. Töröljük a tournamentből \(\displaystyle v_1\)-et és az \(\displaystyle N^+(v_1)\) csúcshalmazt. (Természetesen a hozzájuk csatlakozó élekkel együtt.) Láttuk, hogy a megmaradó \(\displaystyle N^-(v_1)\) csúcsaira teljesül, hogy \(\displaystyle \vert N^-(v_1)\vert \leq \frac{n-1}{2}\). Ha \(\displaystyle N^-(v_1)\) üreshalmaz, akkor készen vagyunk, beláttuk az állítást, hiszen \(\displaystyle \gamma(T_n)=1\). Különben a törlés után kapott, legfeljebb \(\displaystyle \frac{n-1}{2}\) csúcsú tournamentben válasszuk ki a maximális fokú csúcsot, jelölje \(\displaystyle v_2\), ez a csúcs \(\displaystyle N^-(v_1)\)-ben pszeudogyőztes. A fentiekhez hasonlóan járjunk el: töröljük \(\displaystyle v_2\)-t és az \(\displaystyle N^+(v_2)\) csúcshalmazt. Ekkor a megmaradó tournamentünk csúcsszáma legfeljebb
\(\displaystyle \dfrac{\frac{n-1}{2}-1}{2} \leq \dfrac{n}{4}. \)
Ismételjük a fentieket, amíg el nem fogynak a csúcsok. Minden lépésben a csúcsszám felénél kevesebb csúcs marad meg, a \(\displaystyle k\)-adik után kevesebb mint \(\displaystyle \frac{n}{2^k}\), ezért
\(\displaystyle \left\lceil\log_2(n)\right\rceil \)
lépés után már biztosan elfogynak a csúcsok.
Minden lépésben találtunk egy-egy, vagyis összesen legfeljebb \(\displaystyle \lceil\log_2(n)\rceil\) darab pszeudogyőztest, amelyek együtt – a korábbiak szerint – domináló halmazt alkotnak. \(\displaystyle \Box\)
A mai napig emlékszem arra, amikor a hátamon fekve, a plafont bámulva végighaladtam a fenti gondolatlánc egyes elemein, és eljutottam az utolsó állításig. Először nagy öröm volt bennem, aztán jött a realista gondolat: „Ezt már biztos, hogy tudja a világ!” Rövid keresés után kiderült, hogy Erdős Pálhoz köthető ez az eredmény. Ennek a felismerésnek talán még jobban örültem, mintha én publikálhattam volna ezt a felfedezésemet.
Köszönetnyilvánítás. Nagy hálával tartozom gimnáziumi matematikatanáraimnak, Horváth Attilának és Kovács Tibornak, hogy annak idején megszerettették velem a matematikát!
[1] Landau, H. G. (1953). On dominance relations and the structure of animal societies: III The condition for a score structure. Bulletin of Mathematical Biophysics 15, 143–148. https://doi.org/10.1007/BF02476378
[2] Moon, J. W. (1962). Solution to problem 463. Math. Mag, 35(189), 12. https://doi.org/10.1007/BF02476378
[3] Andrásfai, B. (1971). Ismerkedés a gráfelmélettel. Tankönyvkiadó. https://doi. org/10.1007/BF02476378
[4] Reid, K. B. (1982). Every vertex a king. Discrete Mathematics, 38(1), 93–98. https://doi.org/10.1016/0012-365X(82)90173-X
[5] Erdős, P. (1963). On a problem of Schütte. The Mathematical Gazette, 47, 220–222. https://www.renyi.hu/~p_erdos/1963-08.pdf
[6] Caro, Y., & Hansberg, A. (2019). Directed domination in oriented hypergraphs. Communications in Combinatorics and Optimization, 4(2), 173–183. https://arxiv.org/abs/1904.02351
[7] Reid, K. B., McRae, A. A., Hedetniemi, S. M., & Hedetniemi, S. T. (2004). Domination and irredundance in tournaments. Australasian Journal of Combinatorics, 29, 157–172. https://ajc.maths.uq.edu.au/pdf/29/ajc_v29_p157.pdf
A KöMaL levelezős versenyei azon kevesek közé tartoznak, amelyek ingyenesek – immár több mint 130 éve! Sajnos azonban a KöMaL állami támogatásának rendszere az elmúlt évben jelentősen átalakult, a következő években az előre látható bevételeink várhatóan nem tudják fedezni a költségeinket.
Ezért kérünk mindenkit, aki szereti a KöMaL-t, létezését fontosnak tartja, hogy lehetőségéhez mérten támogassa a KöMaL-t kiadó MATFUND Alapítványt. Ha teheti, rendelkezzen adója 1%-áról az Alapítvány javára. Ezen kívül pedig, ha saját vagy céges lehetőségei megengedik, támogassa a KöMaL kiadását, a KöMaL tudáskincsének gondozását!
A KöMaL kiadásának, a versenyek teljes lebonyolításának, díjazásának és a díjkiosztóval egybekötött Ifjúsági Ankétok szervezésének költségeit 2007 óta a MATFUND Középiskolai Matematikai és Fizikai Alapítvány fizeti.
Kérjük, személyi jövedelemadója 1%-ának felajánlásával álljon a több, mint 125 éve alapított Középiskolai Matematikai és Fizikai Lapok mellé!
A KöMaL 2022 őszi számaiban Tóthmérész Lilla egy alapos cikksorozatot ([1]) közölt a négyszín-sejtés történetéről, benne kiemelten Alfred Kempe 1879-ben közölt bizonyítási kísérletéről, amelyben Heawood 1890-ben találta csak meg a hibát. A cikkben leírtakat érdemes kiegészíteni azzal, hogy 1880-ban egy másik, rendkívül érdekes bizonyítási kísérlet is történt. Egy Peter Guthrie Tait nevű skót matematikus ugyanis a következő szép állítást bizonyította, mindössze 1 évvel Kempe kísérlete után ...
A KöMaL 2025 szeptemberi számában (Tait tétele és a 3-reguláris gráfok – a B. 5403. feladat háttere) kimondtuk Tait alábbi tételét.
Tétel (Tait tétele). Legyen \(\displaystyle G\) egy 3-reguláris, hídélmentes, síkbarajzolt gráf. Ekkor \(\displaystyle G\) tartományai \(\displaystyle 4\)-színezhetők akkor és csak akkor, ha élei \(\displaystyle 3\)-színezhetők.
A tételben \(\displaystyle k\)-színezésen olyan színezést értünk, amely \(\displaystyle k\)-féle színt használ, és az egymással szomszédos tartományok (illetve élszínezés esetén az egy csúcsban találkozó élek) mindig különböző színűek.
A szeptemberi számba nem került be a tétel bizonyítása (azzal a céllal, hogy akinek van kedve, gondolkodhasson rajta), ezt most pótoljuk.
