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.
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.
A projektív geometria eredete a reneszánsz idejére tehető, amikor nem matematikusok, hanem festők kezdték tanulmányozni a valósághű ábrázolás és ezen keresztül a középpontos vetítés szabályait.
A félszemű festő szerencsére nem volt gyakori a reneszánsz idején sem. De az igen, hogy egy festő egyik szemével hunyorítva nézte a tájat, tárgyakat, így próbálván felderíteni a perspektivikus képüket. Ennek a „hunyorításnak” az absztrakt megfelelője lesz most a Félszemű Festő, \(\displaystyle FF\), aki szeretne realista képet készíteni a vásznára (jelölje \(\displaystyle \mathcal{V}_0\)) az Alföld (jelölje \(\displaystyle \mathcal{A}\)) egy darabjáról. Mit kell tennie? Az egyszerűség kedvéért tegyük fel, hogy \(\displaystyle \mathcal{V}_0\) valamilyen átlátszó anyagból készült téglalap, \(\displaystyle \mathcal{A}\) egy \(\displaystyle \mathcal{V}_0\)-t nem tartalmazó sík, \(\displaystyle FF\) egyetlen szeme, \(\displaystyle E\) pedig egy olyan pont, amely sem \(\displaystyle \mathcal{A}\)-ra, sem a \(\displaystyle \mathcal{V}_0\)-t tartalmazó \(\displaystyle \mathcal{V}\) síkra nem illeszkedik. A festőnek szeme sem rebben, tehát az \(\displaystyle E\) pont helye rögzített.
