Sok színnel, sokszínűen a gráfokról

Bevezető gondolatok

A magyarországi matematikának egyik kiemelkedő területe a gráfelmélet. A nemzetközi szakkönyvekben, példatárakban nagyon gyakran találkozhatunk hivatkozásokkal magyar matematikusok tételeire, hazánkban kitűzött versenyfeladatok bemutatásával. Ezek a példák megmozgatják a fiatalok fantáziáját, hiszen a problémák megoldása szinte minden esetben valamilyen speciális felismerésen, különleges fogalomtársításon alapul, így komoly szellemi kihívást jelent még a matematikailag képzettek számára is.

Az iskolai tanórákon a diákok többsége általában csak a legalapvetőbb megoldási lehetőségekkel ismerkedik meg, és egyszerű feladatok megoldására válik alkalmassá. A tanulók rutinszerű példákat oldanak meg, adott tulajdonságú egyszerű gráfokat hoznak létre, és vizsgálják a létezés feltételeit. Ebben a cikkben más szempontok szerint vizsgáljuk meg a gráfokat. Áttekintjük, hogy a gráfok milyen széles körben lehetnek segítségünkre a problémák megoldásában. Tesszük ezt a színek segítségével úgy, hogy kiderüljön, hogy egy ilyen szemléltetéssel még a nehezebb feladatok is könnyebben megoldhatóvá válnak. Elkalandozunk a játékok, a sík- és a kombinatorikus geometria, a poliéderek, a versenyek világába, foglalkozunk optimális útvonalak, elhelyezkedések, kapcsolatrendszerek kialakításával. Eközben találkozunk a gráfelmélet legfontosabb összefüggéseivel, a fokszámokra vonatkozó ismeretekkel, a Turán-tétellel, a fákkal, a síkgráfokkal, az Euler-féle poliédertétellel, a Ramsey-problémákkal és a versenygráfokkal.

Az egyes módszerek segítségével nagyon változatos nehézségű és érdekes feladatok megoldását mutatjuk meg. A cikk végén azt is bemutatjuk, hogy hogyan készíthetünk mi magunk is nevezetes tételek segítségével feladatokat mások számára. Összességében egy jól hasznosítható anyagot szeretnénk adni a kollégáknak az iskolai szakköri munkához.

A cikkben a következő fogalmakat ismertnek tekintjük: gráf, teljes gráf, körmentes gráf, reguláris gráf, izolált pont, csúcs fokszáma.

A cikkben említett tételek bizonyítása megtalálható ezekben a művekben: Katona Gyula–Recski András–Szabó Csaba: A számítástudomány alapjai, Xiong Bin–Zheng Zhongyi: Graph Theory.

1. Gráfok alkalmazása nem várt helyzetekben

A következő két feladat arra mutat be egy-egy példát, hogy mennyire eredményesen használhatók a gráfok a játékelméletben. Segítségükkel tudatosan, gyorsan alakíthatunk ki egy játékhelyzetet, és könnyen indokolhatóvá válik az is, ha egy állás nem hozható létre.

Egy $3\times 3$ -as négyzetrács négy sarokmezőjében a bal oldali ábra szerint két világos és két sötét huszár áll. A huszároknak a sakk szabályai szerinti mozgatásával elérhető-e, hogy a bábuk a jobb oldali ábra szerinti helyzetbe kerüljenek, ha a lépések során a bábuk csak üres mezőkre ugorhatnak?

Megoldás:

Számozzuk meg a négyzetrács mezőit az alábbi ábra szerint:

Rendeljük hozzá a rács négyzeteihez egy gráf $v_1$ , $v_2$ , ..., $v_9$ csúcsait, és kössük össze éllel azokat a csúcsokat, amelyekhez tartozó mezők elérhetők egymásból egy lóugrással. Ekkor a huszárok kezdeti és végső helyzetét is bejelölve az alábbi $G_1$ és $G_2$ gráfokat kapjuk:

Mivel a huszároknak megfelelő csúcsokat a mozgatás mindig csak szomszédos üres csúcsba viheti, ezért a forgásirány szerinti sorrendjük a lépegetések során nem változhat meg.

Így a fehér–fehér–fekete–fekete huszár helyzete nem változhat át fehér–fekete–fehér–fekete sorrendre. Tehát a kívánt állapot nem érhető el.

Egy 4 kockából álló logikai építőjáték elemeinek lapjai az alábbiak szerint vannak színezve:

A játék célja az, hogy a kockákból úgy építsünk 4-szintes tornyot, hogy annak minden oldallapján az összes szín előforduljon.

Megoldás:

Rendeljünk az egyes kockákhoz egy-egy gráfot úgy, hogy ezen a kockák lapjainak a színezését át tudjuk tekinteni. Az egyes gráfoknak legyen négy csúcsa a négy színnek megfelelően. Két csúcs között akkor haladjon él, ha a kocka két szemben lévő lapja ilyen színű. Ha két ilyen lap azonos színű, akkor ezt az ábrán hurokél jelöli. Négy csúcsból és 3 élből álló gráfokat kapunk:

A négy gráfot egyesítve az alábbi $G$ gráf adódik. Minden élre ráírjuk, hogy melyik kockából került az egyesített gráfba.

A feladat megoldásához olyan $G_1$ , $G_2$ részgráfokat keresünk, amelyek megadják azokat a színeket, amelyek a torony elején-hátulján, illetve bal és jobb oldalán szerepelnek. $G_1$ , $G_2$ kiválasztásának szempontjai:

– A torony felépítésében mind a 4 kocka részt vesz, ezért $G_1$ és $G_2$ minden számozott gráfnak egy élét tartalmazza.

– A hasáb oldallapjain minden szín előfordul, ezért $G_1$ és $G_2$ pontjai a $P$ , $K$ , $Z$ és $S$ csúcsok.

– A hasáb szemközti oldallapjain minden szín egyszer-egyszer, összesen kétszer szerepel, ezért a csúcsok másodfokúak, $G_1$ és $G_2$ 2-regulárisak.

Egy lehetséges megoldás:



Elöl – hátul	Balra – jobbra

A két gráf mindegyikén szerepel az 1, 2, 3, 4 szám. Ez azt jelenti például, hogy az 1-es kockát úgy tegyük magunk elé, hogy elöl legyen a kék, hátul a sárga (vagy fordítva), balra legyen a piros, jobbra a zöld (vagy fordítva). A 2-es, 3-as, 4-es kocka elhelyezését hasonlóan olvashatjuk le a $G_1$ , $G_2$ gráfokról. A második kocka elhelyezésétől kezdve figyelnünk kell arra, hogy azonos oldalra ne kerüljön kétszer egy szín. A kockát megfelelő tengelye/tengelyei körül elforgatva ez a probléma megoldható.

Ha ilyen módon felépítettünk egy tornyot, akkor a kockák sorrendje függőlegesen tetszőlegesen permutálható.

Az alábbi torony ilyen elvek szerint épült:

	hátsó lap	bal oldali lap
4. kocka	P	Z
3. kocka	K	K
2. kocka	Z	S
1. kocka	S	P

2. Csúcsok fokszámának vizsgálata

Felhasznált tételek:

T1: Ha egy $G$ gráfban a $v_1$ , $v_2$ , ..., $v_n$ ( $n\in \mathbb{N}^+$ ) csúcsok fokszámai rendre $d(v_1)$ , $d(v_2)$ , ..., $d(v_n)$ és az élek száma $e$ ( $e\in \mathbb{N}$ ), akkor

$\displaystyle d(v_1)+d(v_2)+\ldots+d(v_n)=2e.$

T2: Bármely $G$ gráfban a páratlan fokú csúcsok száma páros.

Egy háromszög csúcsai piros, kék és zöld színekkel vannak kiszínezve. A nagy háromszög belsejében elhelyezünk néhány pontot, és így azt több kisebb háromszögre bontjuk. Két kis háromszögnek lehet közös csúcsa, közös oldala, vagy lehetnek közös pont nélküliek is. A kis háromszögek csúcsait is kiszínezzük a piros, kék vagy zöld színek valamelyikével. Bizonyítsuk be, hogy bármilyen színezés esetén kapunk olyan háromszöget, amelynek csúcsai különböző színűek.

Megoldás:

Válasszunk ki egy pontot ( $v_1$ ) a nagy háromszögön kívül, és kössük össze azt a nagy háromszög piros-kék oldalára illeszkedő részháromszögének egy belső pontjával ( $v_2$ ). Továbbá keressük meg belül az összes piros-kék végpontú oldalt, és kössük össze az azokra illeszkedő két háromszögnek egy-egy belső pontját egy-egy szakasszal [az ábra szerint $(v_3;v_4)$ , $(v_4;v_5)$ , $(v_5;v_6)$ ].

Tekintsük a kiválasztott $v_i$ pontokat egy $G$ gráf csúcsainak, a berajzolt szakaszokat $G$ éleinek.

$G$

Ekkor a $G$ gráf azon belső csúcsai, amelyek foka 1 és a nagy háromszög belsejében találhatók, egy háromszínű háromszög belsejében vannak.

$d(v_i)=1$

Másrészt $G$ azon belső csúcsai, amelyek foka 2, egy piros-kék háromszög belsejében helyezkednek el.

$d(v_i)=2$

$G$ csúcsainak fokszámát vizsgálva, mivel a nagy háromszögön kívüli csúcs foka 1, és a gráfban a páratlan fokú csúcsok száma páros, ezért $G$ tartalmaz még legalább egy 1-fokú csúcsot. A korábbi megállapításunk szerint ez a pont egy háromszínű háromszög belsejében helyezkedik el.

3. Turán-tétel

Egyszerűbb formában:

Ha egy $n$ csúcspontú $G$ gráfban nincs $K_{k+1}$ (teljes $(k+1)$ -es), akkor éleinek száma legfeljebb

$\displaystyle \frac{k-1}{2k}n^{2}.$

Teljes formában:

Ha $n=kq+r$ , ahol $0\leqslant r<k$ ( $r$ , $q\in \mathbb{N})$ , és az $n$ csúcspontú $G$ gráfban nincs $K_{k+1}$ , akkor az élek $e$ számára teljesül, hogy

$\displaystyle e\leqslant \frac{k-1}{2k}n^{2}-\frac{r(k-r)}{2k}.$

Az egyenlőség olyan $T(n, k)$ Turán-gráfra teljesül, amely $k$ közös elem nélküli $A_1$ , $A_2$ , ..., $A_k$ ponthalmazból áll, ahol $\vert A_1\vert=\ldots=\vert A_r\vert=q+1$ , $\vert A_{r+1}\vert=\ldots=\vert A_k\vert=q$ , és két pontot pontosan akkor kötünk össze, ha azok különböző ponthalmazokhoz tartoznak.

Egy bridzsklubnak van egy speciális szabálya, amely szerint 4 tag csak abban az esetben játszhat együtt, ha a párokon belül egyik játékos sem volt korábban a párjának partnere.

Egy találkozón 14 tag jelent meg, akik közül mindenki korábban 5 társának volt partnere. Az est folyamán 3 mérkőzés lejátszása után a tagok szomorúan tapasztalták, hogy a klubszabály miatt be kell fejezniük a játékot. Már készülnek a befejezésre, amikor beállít egy új tag, akit egyikük sem ismer. Mutassuk meg, hogy az ő érkezésével még legalább egy játék lejátszható.

Megoldás:

Rendeljük hozzá az eredetileg jelen levő 14 taghoz egy $G$ gráf egy-egy csúcsát. Kössük össze éllel azokat a csúcsokat, amelyekhez tartozó emberek még nem volt partnerei egymásnak, majd vizsgáljuk a gráf $\bar{G}$ komplementerét.

Figyelembe véve, hogy a 14 személy mindegyikének korábban 5 partnere volt, és az est folyamán az új tag érkezéséig már 3 mérkőzést lejátszottak, ezért $\bar{G}$ éleinek száma:

$\displaystyle e\left(\bar{G}\right)=\frac{14\cdot 5}{2}+3\cdot 2=41$ , és

$\displaystyle e(G)=e\left(K_{14}\right)-e\left(\bar{G}\right)=\frac{14\cdot 13}{2}-41=50.$

Az új tag érkezésével akkor nyílik lehetőség új partira, ha $G$ tartalmaz háromszöget. A Turán-tétel alapján, ha $G$ -ben nincs $K_3$ , akkor

$\displaystyle e(G)\leqslant \frac{k-1}{2k}\cdot n^{2}=\frac{{14}^{2}}{4}=49.$

Mivel $G$ -ben az élek száma meghaladja a 49-et, így $G$ tartalmaz háromszöget. Ehhez a háromszöghöz tartozó személyek és az új tag között tehát lebonyolítható a szabályoknak megfelelő mérkőzés.

4. Fagráfok

Fontosabb definíciók, tételek:

D1: Az összefüggő, körmentes gráfokat fáknak nevezzük.

T1: Minden legalább 2 pontú $T$ fagráfban van legalább 2 elsőfokú pont.

T2: Ha a $T$ fagráf csúcsainak száma $n$ ( $n\in \mathbb{N}^+$ ), akkor éleinek száma $e=n-1$ .

T3: Legyen a $T$ fagráf csúcsainak száma $n$ , éleinek száma $e$ . Ekkor az alábbi tulajdonságok ekvivalensek egymással:

a) $T$ fagráf,

b) $T$ körmentes és $e=n-1$ ,

c) $T$ összefüggő és $e=n-1$ .

Egy csúcsú teljes gráf éleit Dia és Viki a megadott sorrend szerint felváltva színezi ki pirosra. Az veszít, aki először hoz létre piros kört. Melyik lánynak van nyerő stratégiája?

Megoldás:

A feladatban szereplő játéknak csak $n\geqslant 3$ esetén van értelme, hiszen $n=1$ , $n=2$ esetén senki sem veszít, tehát a játék döntetlen eredménnyel ér véget.

Használjuk fel a feladat megoldásához az alábbi két gráfelméleti tételt:

– Egy $n$ csúcsú összefüggő gráfnak legalább $n-1$ éle van.

– Egy $n$ csúcsú körmentes gráfnak legfeljebb $n-1$ éle van.

Azt fogjuk belátni, hogy $n\geqslant 3$ esetben helyes játék esetén az veszít, akinek az $n$ . élt kell pirosra színeznie. Állításunk igazolásához elég belátni, hogy ha $k<n$ , akkor az a játékos, aki a $k$ élt színezi, még meg tudja tenni, hogy ne ő hozzon létre piros élekből álló kört.

Tekintsük azt a $G_{k-1}$ gráfot, amit az addig kiszínezett $k-1$ él alkot az $n$ csúccsal.

Ha $k<n$ , akkor $k-1<n-1$ , így $G_{k-1}$ nem összefüggő. Ez azt jelenti, hogy szétbomlik két vagy több $T_1$ , $T_2$ , ..., $T_j$ fára, amelyek között nem fut él.

Pl. $n=12$ , $k=9$

Az éppen következő játékosnak nem kell mást tennie, mint két fa egy-egy pontját kell összekötnie egy piros éllel. Ha $G_{k-1}$ -ben nem volt piros kör, akkor $G_k$ -ban sem lesz, mivel a kör kialakításához fel kellene használni az újonnan behúzott élt, illetve a két fa között kellene lennie még egy összekötő élnek. Ilyen pedig nincs.

Így beláttuk, hogy ha az egyik leánynak a $k<n$ sorszámú élt kell kiszíneznie, akkor el tudja kerülni a piros kör kialakulását. Az a játékos viszont, akinek az $n$ . él jut, ezt már nem tudja megtenni. Ezért helyes stratégia esetén páros $n$ -re Dia, páratlanra pedig Viki nyer.

5. Euler-vonal

Felhasználható definíciók, tételek:

D1: Vonalnak nevezzük egy gráf éleinek egymáshoz csatlakozó sorozatát, amelyben minden él legfeljebb egyszer szerepelhet, de lehetnek olyan pontok, amelyek többször is előfordulnak.

D2: Euler-vonalnak nevezünk egy gráfban egy vonalat, ha az a gráf minden élén áthalad. Az Euler-vonal lehet nyitott, ha a kezdő- és végpontja nem azonos, és lehet zárt, ha kezdő- és végpontja megegyezik.

T1: Izolált pontot nem tartalmazó gráfban akkor és csak akkor van zárt Euler-vonal, ha a gráf összefüggő és minden pont fokszáma páros.

T2: Izolált pontot nem tartalmazó gráfban akkor és csak akkor van nyitott Euler-vonal, ha a gráf összefüggő és két pont fokszáma páratlan, a többi pont fokszáma páros.

Az ábra szerint Atom Anti és Zé, a két hangya az és pontokban állnak. Azt mondja Anti Zé-nek: „Versenyezzünk, nézzük meg, hogy melyikünk halad át először a 9 élen és ki ér előbb a csúcsba.” A két hangya egyszerre indul, és azonos sebességgel halad. Ki nyeri meg a versenyt?

Megoldás:

Tekintsük a pontokat egy $G$ gráf csúcsainak, a köztük húzott szakaszokat pedig az éleinek. $G$ összefüggő, és az egyes csúcsok fokszámai: $d_Z=d_B=3$ , $d_A=d_C=d_D=4$ .

Tehát $G$ -ben pontosan két páratlan fokú csúcs van ( $B$ és $Z)$ . Így T2 alapján a gráfban van nyílt Euler-vonal, amelynek két végpontja $B$ és $Z$ .

Ezért, ha Zé például $Z$ -ből indulva a $ZDCADBAZCB$ nyílt Euler-vonalon halad, akkor 9 él érintésével eljuthat $B$ -be (lásd a fenti ábrát). Anti a páros fokszámú $A$ pontból indul, így ő nem juthat el élismétlés nélkül $B$ -be. Tehát a megfelelő útvonalválasztás esetén Zé nyeri meg a versenyt.

6. Hamilton-kör

Fontosabb definíciók, tételek:

D: Egy $G$ gráfban egy kört Hamilton-körnek nevezünk, ha $G$ minden pontját pontosan egyszer tartalmazza.

T1 (Ore-tétel): Legyen $G$ egyszerű gráf csúcsainak száma $n$ ( $n\geqslant 3$ , $n\in \mathbb{N}^+$ ). Ha bármely $v$ , $v'$ nem szomszédos csúcspár esetén $d(v)+d(v')\geqslant n$ , akkor $G$ tartalmaz Hamilton-kört.

T2 (Dirac-tétel): Legyen $G$ egyszerű gráf csúcsainak száma $n$ ( $n\geqslant 3$ , $n\in \mathbb{N}^+$ ). Ha a gráfban minden pont foka legalább $n/2$ , akkor a gráfban létezik Hamilton-kör.

Egy kör alakú asztal körül legalább 5 ember ül. Lehetséges-e, hogy úgy módosítsuk az ülésrendet, hogy mindenkinek két új szomszédja legyen?

Megoldás:

5 fő esetén egy lehetséges megoldás:

5-nél több személy esetén rendeljük a társaság tagjaihoz egy gráf csúcsait, és kössük össze éllel azokat a csúcsokat, amelyekhez tartozó emberek az eredeti helyzet szerint nem voltak szomszédok. Így olyan $G$ gráfot kapunk, amelyben minden csúcs foka $\left\vert V(G)\right\vert-3=n-3$ ( $n\geqslant 6$ , $n\in \mathbb{N}^+$ ). Ekkor a gráfban bármely két csúcs fokszámának összege $2n-6$ .

$n\geqslant 6$ esetén $2n-6\geqslant n$ , és az Ore-tétel miatt $G$ tartalmaz Hamilton-kört. Ez alapján alakítható ki a helyes ülésrend. Az ábra $n=6$ esetén mutatja be a megoldást:

7. Síkba rajzolható gráfok

D: Egy gráf síkba rajzolható, ha lerajzolható a síkban úgy, hogy élei kizárólag a csúcspontokban találkoznak.

Euler-formula: Ha adott egy véges összefüggő síkgráf, ahol $c$ a csúcsok, $e$ az élek, $l$ pedig a tartományok számát jelöli, beleértve a külső nagy területet is, akkor $\displaystyle c+\ell=e+2$

Adott egy körön pont (, $n\in \mathbb{N}^+$ ). Bármelyik két pontot összekötjük egy-egy szakasszal. Ezen szakaszok között nincs 3 olyan, amelyek a körön belül egy pontban metszik egymást. Határozzuk meg a körön belül kialakult tartományok számát.

Megoldás:

A kör $n$ ívének eltávolítása után egy egyszerű síkgráfot kapunk, amelynek csúcsai a körön levő pontok és a szakaszok körön belüli metszéspontjai.

A körön levő pontok közül bármelyik 4 pontosan egy belső metszéspontot határoz meg, így

$\displaystyle c=n+\binom{n}{4}.$

A körön levő pontok mindegyikéhez $n-1$ , a belső pontokhoz 4-4 él tartozik, és minden élnek két végpontja van, ezért

$\displaystyle e=\frac{1}{2}\cdot \left[n(n-1)+4\binom{n}{4}\right].$

A síkgráfokra vonatkozó Euler-formula alapján a tartományok száma:

$\displaystyle \ell'=e+2-c=\left[\frac{n\left(n-1\right)}{2}+2\binom{n}{4}\right]+2-\left[n+\binom{n}{4}\right].$

Az így kimaradt tartományokhoz hozzáadva a körívek által határolt $n$ tartományt és levonva a körön kívüli részt:

$\displaystyle \ell=\ell'+n-1=\frac{n\left(n-1\right)}{2}+\binom{n}{4}+1=\binom{n}{2}+\binom{n}{4}+1.$

8. Ramsey-számok

Fontosabb ismeretek:

T (Ramsey-tétel): Adott $k$ és $p$ pozitív egészekhez létezik egy olyan legkisebb $r(k;p)$ szám, hogy bármely $n\geqslant r(k;p)$ ( $n\in \mathbb{N}^+$ ) esetén az $n$ pontú $K_n$ teljes gráf éleit két színnel – kékkel és pirossal – kiszínezve van a gráfban egy kék $K_k$ vagy egy piros $K_p$ .

T1: $r(k;1)=r(1;p)=1$

T2: $r(k;2)=k$ , $r(2;p)=p$

T3: $r(k;p)\leqslant r(k-1;p)+r(k;p-1)$

T4: (Erdős–Szekeres): $r(k;p)\leqslant \dbinom{k+p-2}{k-1}$

Néhány Ramsey-szám:

$\displaystyle r(3;3)=6, \quad r(3;4)=9, \quad r(3;5)=14, \quad r(4;4)=18, \quad r(4;5)=25.$

Az 1, 2, 3, 4, 5 számokat véletlenszerűen két csoportba ( és ) osztjuk. Bizonyítsuk be, hogy az egyik csoportba kerül két olyan szám, amelyek különbsége megegyezik a csoport egyik számával.

Megoldás:

Az $i=1, 2, 3, 4, 5, 6$ számokhoz rendeljük hozzá egy $G$ gráf $v_i$ csúcsait. Bármely $1\leqslant i<j\leqslant 6$ esetén kössük össze a $v_i$ , $v_j$ csúcsokat kék éllel, ha $j-i\in A$ , és pirossal, ha $j-i\in B$ . Így egy kétszínű $K_6$ teljes gráfot kapunk, amely $r(3;3)=6$ miatt tartalmaz monokromatikus háromszöget. Legyenek ennek csúcsai $v_i$ , $v_j, v_k$ ( $1\leqslant i<j<k\leqslant 6$ ). Ekkor az $a=j-i$ , $b=k-j$ , $c=k-i$ számok egy csoportban vannak, és

$\displaystyle c-b=(k-i)-(k-j)=j-i=a.$

Például $A=\{1; 3\}$ , $B=\{2; 4; 5\}$ esetén:

Piros háromszög $v_1v_3v_5$ , ( $3-1=5-3=2$ , $5-1=4$ ) és $4\in B$ , $2\in B$ és $4-2=2\in B$ .

9. Versenygráfok

Fontosabb ismeretek:

D: Egy gráfot irányított versenygráfnak nevezünk, ha $n$ ( $n\geqslant 2$ , $n\in \mathbb{N}^+$ ) csúcsot tartalmaz, és bármely két csúcsot pontosan egy irányított él köt össze.

Jelölése: $\overrightarrow{K}_n$ .

Az él a győztestől mutat a vesztes felé.

A $v$ csúcs kifoka az adott csúcsból kiinduló, befoka pedig az oda befutó élek száma. Jelölésük: $d^+(v)$ , illetve $d^{-}(v)$ .

$\overrightarrow{K}_5$ , $d^+\left(v_1\right)=3$ , $d^{-}\left(v_1\right)=1$

T1: Legyenek $v_1$ , $v_2$ , ..., $v_n$ egy $\overrightarrow{K}_n$ versenygráf csúcsai. Ekkor

$\displaystyle d^+\left(v_1\right)+d^+\left(v_2\right)+\ldots+d^+\left(v_n\right... ...\right)+d^{-}\left(v_2 \right)+\ldots+d^{-}\left(v_n\right)=\frac{n(n-1)}{2}.$

T2: Egy versenygráfban mindig létezik olyan csúcs, ahonnan vezet irányított út bármely más csúcsba. Az ilyen utak maximális hossza 2.

T3: A $\overrightarrow{K}_n$ versenygráf mindig tartalmaz $n-1$ hosszú Hamilton-utat.

T4: Egy $\overrightarrow{K}_n$ versenygráf ( $n\geqslant 3$ , $n\in \mathbb{N}^+$ ) akkor és csak akkor tartalmaz kört, ami háromszög, ha létezik két olyan $v$ és $v'$ csúcs, melyekre teljesül, hogy

$\displaystyle d^+(v)=d^+\left(v'\right).$

A tételek alapján nagyon könnyen készíthetünk magunk is versenyfeladatokat. A feladatok megoldása a tételek bizonyítása szerint történik, amelyekre a cikk terjedelme miatt nem térünk ki. Lássuk tehát a versenyeken kitűzhető, nem túl könnyű példákat!

Egy egyfordulós körmérkőzéses tornán ( $n\geqslant 2$ , $n\in \mathbb{N}^+$ ) játékos vesz részt, és mindenki a többiekkel egy-egy mérkőzést játszik. A mérkőzéseken nincs döntetlen eredmény. Bizonyítsuk be, hogy a versenyzők között van olyan személy, hogy ő, az általa legyőzött személyek és az általa legyőzött személyek által legyőzött ellenfelek az összes sportolót tartalmazzák.

Megoldás: T2-ből következik az állítás.

Egy asztalitenisz tornán bármely két játékos pontosan egyszer játszik a többi versenyzővel. Bizonyítsuk be, hogy a játékosokat lehet úgy sorszámozni, hogy minden játékos legyőzte a közvetlenül utána következőt.

Megoldás: T3-ból következik az állítás.

Egy körmérkőzéses egyfordulós röplabda tornán ( $n\geqslant 3$ , $n\in \mathbb{N}^+$ ) csapat vesz részt. A tornán egyetlen csapat sem győzte le az összes ellenfelét. Bizonyítsuk be, hogy a résztvevők között található három olyan , , csapat, hogy legyőzte -t, legyőzte -t és legyőzte -t.

Megoldás: A skatulyaelvből és T4-ből következik az állítás.

Ez az írás a 2022-ben az egri Rátz László Vándorgyűlésen elhangzott szemináriumi foglalkozás alapján készült. A bemutatott feladatokkal felkelthetjük a középiskolás tanulók érdeklődését a gráfelméleti feladatok iránt. A cikkben közölt példák között amerikai, kínai, magyar versenyfeladatok mellett saját feladatok is szerepelnek. Ezekkel próbáltunk jól hasznosítható anyagot biztosítani a középiskolában tanító és a tehetséggondozásban résztvevő kollégáknak.

Fonyó Lajos – Fonyóné Németh Ildikó