Kombinatorika és gráfok

Tételszám: #2 | Kategória: Gondolkodási módszerek, halmazok, logika, kombinatorika, gráfok | Szint: Középszint (2026)

1. Bevezetés

A kombinatorika egyetlen kérdésre felel: hányféleképpen történhet meg valami. Hányféle sorrendben állhat be öt ember, hány számot lehet kirakni négy számjegyből, hányféleképpen választhatsz ki néhány dolgot egy csoportból. A gráf pedig egy rajz pontokból és vonalakból, amivel kapcsolatokat ábrázolsz: ki kivel fogott kezet, melyik város melyikkel van összekötve.

Az írásbelin ez a téma szinte minden feladatsorban előjön. A 2024 és 2026 közötti hat középszintű feladatsorban átlagosan 11 pont körül jött ebből a két témából. Az I. részben 2-3 pontos rövid feladat a jellemző (számjegyekből számok, egy gráf megrajzolása), a II. részben 4-6 pontos részkérdés egy hosszabb, szöveges feladaton belül.

A jó hír: kevés eszköz kell hozzá. Négy számolási szabály, két jelölés (a faktoriális és a binomiális együttható) és a gráfoknál egyetlen összefüggés. A nehéz rész a felismerés, hogy a feladatban számít-e a sorrend, és melyik eseteket kell külön számolni.

2. Mire jó ez, mikor ismerd fel

A kombinatorikai feladat szövegében szinte mindig ott van a „hányféleképpen”, a „hány olyan” vagy a „hányféle sorrendben”. Ezt könnyű észrevenni. Ami a pontot eldönti, az a következő négy döntés.

Árulkodó szavak a kombinatorikai feladatban

• „Sorrend”, „egymás után”, „sorba áll”, „ülésrend”, „számot alkot”. Ilyenkor számít a sorrend: a 123 és a 321 két különböző szám, az Anna-Béla és a Béla-Anna két különböző sorrend.
• „Kiválaszt”, „csoport”, „küldöttség”, „melyik kettőt viszi el”. Ilyenkor általában nem számít a sorrend: ha Annát és Bélát választod, ugyanaz, mint ha Bélát és Annát. Ide a binomiális együttható kell.
• „Különböző számjegyekből”, „mindenki egyszer”. Egy elem csak egyszer szerepelhet, tehát minden lépésnél eggyel kevesebb lehetőséged marad.
• „Legalább”, „legfeljebb”, „nem állhatnak egymás mellett”. Ilyenkor vagy szétszeded esetekre, vagy az összesből kivonod a rossz eseteket (ez a komplementer módszer).

A feladat gyakran zárójelben megmondja, mit tekint különbözőnek, például: „Két kiválasztást különbözőnek tekintünk, ha van legalább egy olyan függvény, amelyik az egyik kiválasztásban szerepel, a másikban pedig nem.” Ezt a zárójelet mindig olvasd el, mert ez dönti el, számít-e a sorrend.

Árulkodó jelek a gráfos feladatban

Gráfos feladatnál a szövegben pontok (vagy csúcsok), élek és fokszámok szerepelnek. Három kérdéstípus jön elő:

1. Rajzolj olyan gráfot, amelyben a pontok fokszáma adott (például 1, 2, 2, 3, 4).
2. Hány éle van, vagy mennyi a fokszámok összege, vagy mennyi a hiányzó fokszám.
3. Létezik-e ilyen gráf? Itt szinte mindig a fokszámösszeg párossága a kulcs.

Ha egy hétköznapi helyzetben valakik kapcsolatban állnak egymással (kézfogás, barátság, összekötött városok, egy áramkör elemei), azt is gráffal ábrázolhatod: az emberek a pontok, a kapcsolatok az élek.

3. Fogalmak és képletek

Ez a négy szabály és a két jelölés a teljes eszköztár. Mindegyik mellé odaírjuk, mikor kell elővenni.

A szorzási szabály: egymás utáni döntések

Ha egy feladat több egymás utáni döntésből áll, és minden döntésnél tudod, hány lehetőséged van, akkor a lehetőségek számát összeszorzod.

Példa (2026. október, I. rész 3. feladat): egy kártyajátékban minden lapon egy sárkány van. A sárkány színe 5-féle, a fejei száma 3-féle (1, 3 vagy 7), a mérete 2-féle (kicsi vagy nagy). Minden lehetséges sárkány egyszer szerepel. A lapok száma:

5 · 3 · 2 = 30

Ha egy lehetőség többször is választható, a szorzótényezők nem csökkennek. Egy 5 kérdéses teszt, ahol minden kérdésnél 4 válasz közül jelölsz meg egyet (2022. május, I. rész 6. feladat), 4 · 4 · 4 · 4 · 4 = 4⁵ = 1024-féleképpen tölthető ki. Ha viszont minden elem csak egyszer szerepelhet („különböző számjegyekből”), akkor minden lépésnél eggyel kevesebb lehetőség marad: 4 · 3 · 2.

Mindig a legszigorúbb feltételű helyen kezdd. Ha a szám páratlan legyen, előbb az utolsó számjegyet döntsd el, mert arra van feltétel, és csak utána a többit.

Az összeadási szabály és az esetszétválasztás

Ha a feladat egymást kizáró esetekre bomlik, akkor esetenként kiszámolod a lehetőségek számát, és a végén összeadod. Az esetek akkor zárják ki egymást, ha egy lehetőség csak egyetlen esetbe tartozhat.

Mikor szorzol és mikor adsz össze? Egyszerű próba:

• „és”, „utána”: egymás után jön a két döntés, mindkettő megtörténik. Szorzol.
• „vagy”, „vagy ez az eset, vagy az”: csak az egyik eset történik meg. Összeadsz.

Az esetszétválasztásnál írd le az esetek listáját is, mert az útmutató sokszor külön pontot ad azért, hogy felismerted, milyen esetek vannak. Ha a vizsgázó rendezetten felsorolja az összes lehetőséget, és ez alapján jól válaszol, az útmutatók szerint a teljes pontszám jár. Kis esetszámnál tehát a rendezett felsorolás is teljes értékű megoldás.

Sorbarendezés és a faktoriális

Ha n különböző dolgot sorba állítasz, az első helyre n, a másodikra n - 1, a harmadikra n - 2 elem közül választhatsz, és így tovább. A szorzási szabály szerint a sorrendek száma:

n! = n · (n - 1) · (n - 2) · ... · 2 · 1

Az n! jele így olvasandó: „n faktoriális”. Megállapodás szerint 0! = 1. Néhány érték, amit érdemes fejből tudni:

3! = 6      4! = 24      5! = 120      6! = 720

Öt ember tehát 5! = 120-féle sorrendben állhat sorba. A számológépen az n! gomb a vizsgán indoklás nélkül elfogadott gépi lépés, de azt le kell írnod, hogy mit számolsz ki vele (például „a sorrendek száma 5! = 120”).

Azonos elemek sorbarendezése. Ha a sorba állított elemek között egyformák is vannak, a sorrendek száma kevesebb, mint n!. Középszinten ezt úgy számolod ki a legegyszerűbben, hogy kiválasztod a különböző elemek helyét. Egy vonat 5 egyforma személykocsiból, egy kerékpárszállító kocsiból és egy étkezőkocsiból áll (2023. október, II. rész 17. a) feladat). A kerékpárszállító kocsi helye 7-féle lehet, az étkezőkocsié utána 6-féle, a személykocsik a maradék helyekre kerülnek. Tehát 7 · 6 = 42 sorrend van.

Kiválasztás, amikor a sorrend nem számít: a binomiális együttható

Ha n különböző elemből k darabot választasz ki, és a sorrend nem számít, a lehetőségek számát a binomiális együttható adja meg. A jele egy nagy zárójel, benne felül n, alatta k. Sima szövegben így írjuk: (n alatt k), és így olvasd: „n alatt a k”.

(n alatt k) = n! / (k! · (n - k)!)

Például 5 emberből 2 fő küldöttséget (5 alatt 2) = 5! / (2! · 3!) = 120 / (2 · 6) = 10-féleképpen választhatsz.

Érdemes összevetni a két esetet ugyanazon az öt emberen:

• Elnököt és titkárt választasz (számít, ki melyik): az elnök 5-féle, a titkár utána 4-féle, tehát 5 · 4 = 20.
• Két fős küldöttséget választasz (nem számít a sorrend): minden párt az előző számolás kétszer számolt (Anna-Béla és Béla-Anna), ezért 20 / 2 = 10 = (5 alatt 2).

Két érték, amit fejből tudj: (n alatt 0) = 1 (semmit nem választani egyféleképpen lehet) és (n alatt n) = 1 (mindet kiválasztani is egyféleképpen lehet). A binomiális együttható a gépen az nCr gombbal számolható, és ez is indoklás nélkül elfogadott lépés. A képletek rendszere (permutáció, variáció, kombináció néven) és a binomiális tétel már emelt szint, középszinten elég a szorzási szabály, a faktoriális és a binomiális együttható.

Komplementer esetek: az összesből kivonod a rosszakat

Ha a feladat a jó eseteket bonyolultan írja le, de a rossz esetek kevesen vannak, akkor számold ki az összes esetet, és vond ki belőle a rossz eseteket:

jó esetek száma = összes eset száma - rossz esetek száma

Ez a komplementer módszer. Akkor érdemes elővenni, ha a feladatban „legalább”, „legfeljebb” vagy „nem” szerepel. Például ha öt ember közül kettő ne álljon egymás mellett, akkor az összes sorrendből (120) kivonod azokat, ahol egymás mellett állnak (48), így 120 - 48 = 72 jó sorrend marad.

Egy segédeszköz az 1. tételből, ami a komplementer módszerhez gyakran kell: egy n elemű halmaznak 2ⁿ részhalmaza van, mert minden elemről külön eldöntöd, beválasztod-e (2 lehetőség), és ezt n-szer teszed meg. Négy elemből tehát 2⁴ = 16-féleképpen választhatsz ki valahány darabot, beleértve azt is, hogy egyet sem.

Gráf, pont, él, fokszám

A gráf pontokból és a pontokat összekötő vonalakból áll. A pontokat csúcsoknak is hívják, a vonalak az élek. Egy él mindig két pontot köt össze. Az nem számít, hogy egyenes vagy görbe vonalat rajzolsz, és hogy két él keresztezi-e egymást: csak az számít, melyik pont melyikkel van összekötve.

Egy pont fokszáma a belőle kiinduló élek száma. Ha egy ponthoz egyetlen él sem fut, a fokszáma 0.

A középszintű feladatokban úgy rajzolj, hogy két pont között legfeljebb egy él legyen, és egyetlen él se fusson vissza ugyanabba a pontba. Az ilyen különleges élek (többszörös él, hurokél) fogalma emelt szintű, ezért középszinten ne rajzolj ilyet. Ugyanígy emelt szintű a teljes gráf, a fa, a kör és az összefüggő gráf fogalma is.

A fokszámösszeg és az élszám összefüggése

Ez a gráfos feladatok egyetlen, de szinte mindig előkerülő tétele: bármely gráfban a pontok fokszámának összege az élek számának kétszerese.

fokszámok összege = 2 · élek száma

Miért? Mert minden él két pontot köt össze, tehát a fokszámok összeadásakor minden élt pontosan kétszer számolsz: egyszer az egyik végénél, egyszer a másiknál.

Ebből három dolog következik, és mindhárom előjön az írásbelin:

• Az élek száma a fokszámösszeg fele. Egy hétpontú gráfban minden pont fokszáma 4 (2025. október, I. rész 4. feladat). A fokszámok összege 7 · 4 = 28, tehát az élek száma 28 / 2 = 14.
• A fokszámösszeg mindig páros szám. Hiszen egy egész szám kétszerese.
• Ezért nincs olyan gráf, amelyben páratlan sok páratlan fokszámú pont van. Van-e olyan gráf, amelynek 5 pontja van, és mindegyik pont fokszáma 3 (2026. október, I. rész 11. feladat)? Nincs, mert ekkor a fokszámok összege 5 · 3 = 15 lenne, ami páratlan, a fokszámösszeg pedig mindig páros. A 3 pontból 1 pont jár a „nincs” válaszért és 2 pont az indoklásért, tehát a puszta „nincs” csak 1 pontot ér.

A teljes gráf (amelyben minden pont minden ponttal össze van kötve) élszámának képlete emelt szintű. Középszinten ilyen helyzetben is a fokszámokból számolsz, ahogy fent.

4. Mintapélda 1 - számjegyekből páratlan számok

A feladat (2026. május, I. rész 11. feladat, 3 pont). Hány háromjegyű, különböző számjegyekből álló páratlan természetes szám alkotható az 1, 2, 3, 4 számjegyekből? Indokold a válaszod!

Felismerés. Számot alkotunk, tehát számít a sorrend. „Különböző számjegyekből”: egy számjegy csak egyszer szerepelhet. A „páratlan” feltétel az utolsó számjegyre vonatkozik, ezért ott kezdjük.

Megoldás.

1. lépés: az egyesek helye (itt van a feltétel, ezért ezzel kezdünk).
   Páratlan szám páratlan számjegyre végződik: az 1 vagy a 3.
   Ez 2 lehetőség.

2. lépés: a százasok helye.
   A négy számjegyből egy már elfogyott, 3 maradt.
   Ez 3 lehetőség.

3. lépés: a tízesek helye.
   Már két számjegy elfogyott, 2 maradt.
   Ez 2 lehetőség.

4. lépés: szorzási szabály, mert a három döntés egymás után jön.
   2 · 3 · 2 = 12

Tehát 12 ilyen szám alkotható. A rendezett felsorolás ugyanezt adja: 123, 143, 213, 231, 241, 243, 321, 341, 413, 421, 423, 431.

Amire pont jár. Egy pont jár azért, hogy az utolsó helyre 2 lehetőség van (1 vagy 3), egy a többi helyiérték 3 · 2 = 6 lehetőségéért, és egy a 12-es végeredményért. A „Válaszát indokolja!” miatt a puszta 12 nem ér teljes pontot.

Gyakorold. Hány négyjegyű, különböző számjegyekből álló páratlan szám alkotható az 1, 2, 3, 4 számjegyekből (2024. május, I. rész 3. feladat)? Az utolsó számjegy most is 2-féle, az első három helyre a maradék három számjegy 3! = 6-féle sorrendben kerülhet. A válasz 2 · 6 = 12.

5. Mintapélda 2 - két ember közvetlenül egymás után

A feladat (2025. május, II. rész 18. d) feladat, 4 pont). Egy ötfős hegymászócsapat egymás után halad a csúcs felé. A csapatban van Ágnes és László. Hányféle sorrendben haladhatnak öten egymás után, ha Ágnes és László (valamilyen sorrendben) közvetlenül egymás után halad?

Felismerés. Sorrendről van szó, tehát faktoriális kell. A feltétel két embert összeköt. A trükk: a két embert egyetlen „csomagnak” tekintjük, és csak a végén nézzük meg, a csomagon belül hányféle sorrendben lehetnek.

Megoldás.

1. lépés: a pár egy egységnek számít.
   Ágnes és László együtt egy egység, mellettük van még 3 hegymászó.
   Így 4 egységet kell sorba rendezni.

2. lépés: a 4 egység sorrendje.
   4! = 24-féle sorrend van.

3. lépés: a páron belüli sorrend.
   A csomagon belül Ágnes lehet elöl vagy László: 2 lehetőség.

4. lépés: szorzási szabály.
   2 · 4! = 2 · 24 = 48

Tehát 48-féle sorrendben haladhatnak.

Egy másik út ugyanehhez. A pár a sorban az 1-2., a 2-3., a 3-4. vagy a 4-5. helyen állhat, ez 4 lehetőség. A páron belül 2-féle a sorrend, a többi három ember 3! = 6-féle sorrendben áll. Tehát 4 · 2 · 6 = 48. Mindkét megoldást elfogadja az útmutató.

Amire pont jár. Két pont jár azért, hogy a párt egy egységnek véve 4! sorrendet kapsz, egy a páron belüli 2-féle sorrendért, és egy a 48-as végeredményért.

Ha a kérdés fordított lenne: „Hányféle sorrendben haladhatnak, ha Ágnes és László nem halad közvetlenül egymás után?” Ilyenkor jön a komplementer módszer: az összes sorrend 5! = 120, ebből 48-ban állnak egymás után, tehát 120 - 48 = 72-ben nem.

Gyakorold. Négyen várnak a tanterem előtt: az osztályfőnök és három diák (2025. október, I. rész 6. feladat). Hányféle sorrendben léphetnek be, ha az osztályfőnök elsőként vagy utolsóként lép be? Az osztályfőnök helye 2-féle, a három diák 3! = 6-féle sorrendben jön. A válasz 2 · 6 = 12.

6. Mintapélda 3 - legalább kettő kiválasztása

A feladat (2024. május, II. rész 16. a) feladat, 5 pont). Péter tanára négy függvény ábrázolását tűzte ki szorgalmi feladatnak. Péter ezek közül legalább kettőt meg akar csinálni. Hányféleképpen választhat ki legalább kettőt a négy függvény közül? (Két kiválasztás különböző, ha van olyan függvény, amelyik az egyikben szerepel, a másikban nem.)

Felismerés. A zárójel megmondja, hogy nem számít a sorrend, csak az, melyik függvények vannak benne. Tehát binomiális együttható kell. A „legalább kettő” azt jelenti: kettő, három vagy négy. Ez két úton is megoldható.

Első megoldás: esetszétválasztás.

1. lépés: az esetek felírása.
   Péter 2, 3 vagy 4 függvényt választhat. Ezek kizárják egymást,
   tehát a végén összeadunk.

2. lépés: kettőt választ.
   (4 alatt 2) = 6-féleképpen.

3. lépés: hármat választ.
   (4 alatt 3) = 4-féleképpen.

4. lépés: mind a négyet választja.
   (4 alatt 4) = 1-féleképpen.

5. lépés: összeadás, mert az esetek kizárják egymást.
   6 + 4 + 1 = 11

Második megoldás: komplementer módszer.

1. lépés: az összes kiválasztás.
   Minden függvényről eldönti, megcsinálja-e: 2 lehetőség, négyszer.
   2⁴ = 16 (ebben benne van az is, hogy egyet sem választ).

2. lépés: a rossz esetek, vagyis legfeljebb egy függvény.
   Pontosan egyet 4-féleképpen, egyet sem 1-féleképpen: 4 + 1 = 5.

3. lépés: kivonás.
   16 - 5 = 11

Tehát Péter 11-féleképpen választhat ki legalább két függvényt.

Amire pont jár. Az első megoldásnál egy pont jár azért, hogy felismered a 2, 3, 4 eseteket (ez akkor is jár, ha csak a megoldásból derül ki), egy-egy pont a 6, a 4 és az 1 lehetőségért, és egy a 11-es végeredményért. A második megoldásnál egy-egy pont jár a komplementer gondolatért, azért, hogy minden függvényről külön döntés születik, a 2⁴ = 16-ért, a rossz esetek számáért (4 + 1) és a végeredményért.

Gyakorold (2026. május, II. rész 17. e) feladat). Egy futballcsapat 11 kezdőjátékosa közül egy mérkőzésen legfeljebb 5 játékost lehet lecserélni. Hányféleképpen választhatók ki a lecserélt játékosok? Most az esetek: 0, 1, 2, 3, 4 vagy 5 játékost cserélnek le.

(11 alatt 0) + (11 alatt 1) + (11 alatt 2) + (11 alatt 3) + (11 alatt 4) + (11 alatt 5)
= 1 + 11 + 55 + 165 + 330 + 462 = 1024

A lecserélt játékosok tehát 1024-féleképpen választhatók ki.

7. Mintapélda 4 - érmék bedobása, ahol számít a sorrend

A feladat (2025. május, II. rész 17. a) feladat, 6 pont). Egy automatába 300 Ft-ot kell bedobni. A gép csak 100 Ft-os és 50 Ft-os érmét fogad el. Hányféleképpen lehet ilyen érmékből 300 Ft-ot bedobni, ha a bedobás sorrendje is számít? (Az azonos címletű érméket nem különböztetjük meg.)

Felismerés. Ez egy összetett, II. részes feladat, és két eszköz kell hozzá. Először esetekre bontod, hogy milyen érmékből jöhet ki a 300 Ft. Utána esetenként megszámolod a sorrendeket, és ehhez a helyek kiválasztása kell: azt kell eldönteni, a bedobások közül melyik legyen 100-as.

Megoldás.

1. lépés: milyen érmékből jön ki 300 Ft? (esetszétválasztás)
   3 db 100-as                     (3 bedobás)
   2 db 100-as és 2 db 50-es       (4 bedobás)
   1 db 100-as és 4 db 50-es       (5 bedobás)
   6 db 50-es                      (6 bedobás)

2. lépés: csupa egyforma érme.
   3 db 100-assal és 6 db 50-essel is csak 1-1-féleképpen
   lehet bedobni, mert az egyforma érmék sorrendje nem számít.

3. lépés: 2 db 100-as és 2 db 50-es.
   4 bedobás van, ebből 2 lesz a 100-as. Azt kell kiválasztani,
   melyik két bedobás a 100-as: (4 alatt 2) = 6-féleképpen.

4. lépés: 1 db 100-as és 4 db 50-es.
   5 bedobás van, ebből 1 a 100-as: ez 5-féle helyen lehet.

5. lépés: összeadás, mert az esetek kizárják egymást.
   1 + 6 + 5 + 1 = 13

Tehát 13-féleképpen lehet 300 Ft-ot bedobni az automatába.

Miért binomiális együttható, ha számít a sorrend? Mert a bedobások sorrendjét az dönti el, hogy a négy bedobás közül melyik helyekre kerül a két 100-as. A 100-100-50-50 és az 50-100-50-100 különböző sorrend, de mindkettőt az határozza meg, hogy melyik két helyre tettük a 100-asokat. A helyek kiválasztásánál pedig a helyek sorrendje már nem számít.

Amire pont jár. Egy pont jár a négy eset felismeréséért (akkor is, ha csak a megoldásból derül ki), egy azért, hogy a két szélső eset 1-1 lehetőség, két pont a (4 alatt 2) = 6-ért, egy az 5 lehetőségért, és egy a 13-as összegért. Ha valaki rendezetten felsorolja mind a 13 sorrendet, és ebből jól válaszol, az útmutató szerint teljes pontot kap.

8. Mintapélda 5 - tartományok kiszínezése

A feladat (2025. október, II. rész 14. d) feladat, 5 pont). Egy körlapot három tartományra osztottak. A három tartományt pirossal, sárgával és zölddel színezzük ki úgy, hogy két vagy három színt használunk fel. Egy tartományt egy színnel színezünk, és a szomszédos tartományok azonos színűek is lehetnek. Hányféleképpen színezhető ki az ábra?

A színezés szempontjából csak annyi számít, hogy három különböző tartomány van (nevezzük őket első, második, harmadik tartománynak), és mindegyik kap egy színt a háromból.

Felismerés. A „két vagy három szín” két esetre bontja a feladatot. Az első eset egy sorbarendezés, a második esetben előbb a színpárt választod ki, utána színezel.

Megoldás.

1. lépés: három színnel színezünk.
   Mindhárom szín pontosan egyszer szerepel, tehát a három színt
   osztjuk szét a három tartományra: 3! = 6-féleképpen.

2. lépés: két színnel színezünk - melyik két szín?
   A két felhasznált szín 3-féle lehet: piros-sárga, sárga-zöld,
   piros-zöld.

3. lépés: két adott színnel hányféleképpen?
   Például pirossal és sárgával:
   p-p-s, p-s-p, s-p-p, s-s-p, s-p-s, p-s-s.
   Ez 6 eset (mindkét szín legalább egyszer szerepel).

4. lépés: két színnel összesen (szorzási szabály).
   3 · 6 = 18

5. lépés: a két eset összeadása.
   6 + 18 = 24

Tehát az ábra 24-féleképpen színezhető ki.

Rövidebb út komplementerrel. Ha mindhárom tartomány bármelyik színt kaphatja, az 3 · 3 · 3 = 27 színezés. Ebből a rossz esetek azok, ahol csak egy színt használunk: csupa piros, csupa sárga, csupa zöld, ez 3 eset. Tehát 27 - 3 = 24. A 3. lépés 6 esete is így jön ki: két színnel 2 · 2 · 2 = 8 színezés van, ebből 2 egyszínű, tehát 8 - 2 = 6.

Amire pont jár. Egy pont jár a 3! = 6 háromszínű színezésért, egy a három színpárért, egy a 6 kétszínű esetért, egy a 3 · 6 = 18-ért, és egy a 24-es végeredményért.

9. Mintapélda 6 - a hiányzó fokszám és a gráf megrajzolása

A feladat (2024. május, II. rész 18. a) feladat, 4 pont). Egy áramköri elem egy olyan hatpontú gráffal szemléltethető, amelynek hat éle van, és amelyben öt pont fokszáma ismert: 1, 2, 2, 3, 3. Add meg a hatodik pont fokszámát, és rajzolj egy olyan gráfot, amely megfelel a feltételeknek!

Felismerés. Ismert az élek száma és öt fokszám. A fokszámösszeg és az élszám összefüggése adja meg a hiányzó fokszámot.

Megoldás.

1. lépés: a fokszámok összege az élek számából.
   fokszámok összege = 2 · élek száma = 2 · 6 = 12

2. lépés: a megadott öt fokszám összege.
   1 + 2 + 2 + 3 + 3 = 11

3. lépés: a hatodik fokszám.
   12 - 11 = 1

Tehát a hatodik pont fokszáma 1.

A gráf megrajzolása. Nevezd el a pontokat: A és F legyen a két 1-es, B és C a két 2-es, D és E a két 3-as fokszámú pont. Egy jó gráf ezzel a hat éllel:

A-D,  D-B,  D-E,  B-C,  C-E,  E-F

Ellenőrizd pontonként, hány él fut bele:

A: A-D                 -> 1
B: D-B, B-C            -> 2
C: B-C, C-E            -> 2
D: A-D, D-B, D-E       -> 3
E: D-E, C-E, E-F       -> 3
F: E-F                 -> 1
Élek száma: 6.  Fokszámösszeg: 12 = 2 · 6.

Lerajzolva: D és E egymás mellett áll, egy éllel összekötve. D-ből lóg ki az A, E-ből az F. Alattuk B és C áll, B a D-vel, C az E-vel van összekötve, és B-C között is van él. Így D-E-C-B egy négyszöget alkot, amelyhez két „farok” (A és F) csatlakozik.

Amire pont jár. Egy pont jár a 2 · 6 = 12-es fokszámösszegért, egy a hatodik fokszámért (1), és két pont egy megfelelő gráf rajzáért. Ha valaki előbb jó gráfot rajzol, és abból olvassa le helyesen a hatodik fokszámot, az útmutató szerint az is teljes pontot ér.

Rajzolási tipp. Kezdd a legnagyobb fokszámú pontokkal: kösd őket össze egymással és a többiekkel, amíg el nem fogynak az éleik. Utána a kisebbekre maradt fokszámot pótold. A végén pontonként számold meg az éleket, mert egy hiányzó vagy fölösleges él a rajzon pontot visz.

10. Tipikus hibák

Itt a legtöbben elrontják: összeadnak, amikor szorozni kell, vagy fordítva. Ha a két döntés egymás után jön, és mindkettő megtörténik (első számjegy ÉS utolsó számjegy), szorzol. Ha egymást kizáró esetekről van szó (két színnel VAGY három színnel), összeadsz. A Mintapélda 5-ben a színpár kiválasztása és a színezés szorzás (3 · 6), a két eset pedig összeadás (6 + 18).

Nem a feltételes hellyel kezdik. Ha a páratlan számnál az első helyiértékkel kezdesz, nem tudod, hány páratlan számjegy marad az utolsó helyre, mert az attól függ, mit tettél előre. Mindig azt a helyet döntsd el először, amelyre feltétel vonatkozik.

Faktoriálist írnak, amikor nem minden elem kerül sorba. Öt emberből elnök és titkár választása 5 · 4 = 20, nem 5! = 120. A faktoriális csak akkor kell, ha mindegyik elemet sorba állítod.

Összekeverik, hogy számít-e a sorrend. Két fős küldöttség 5 emberből (5 alatt 2) = 10, nem 5 · 4 = 20. A 20-as szám minden párt kétszer számol. Ha bizonytalan vagy, nézd meg, hogy Anna-Béla és Béla-Anna különböző lehetőség-e a feladat szerint.

A páron belüli sorrendet elfelejtik. A Mintapélda 2-ben a 4! = 24 még nem a válasz: a két embert a csomagon belül is fel lehet cserélni, ezért 2 · 24 = 48. Aki csak 24-et ír, pontot veszít.

A komplementernél rossz dolgot vonnak ki. A „legalább kettő” ellentéte a „legfeljebb egy”, tehát a „pontosan egy” ÉS az „egy sem” együtt. A Mintapélda 3-ban 16 - 4 = 12 hibás, mert kimaradt az az eset, amikor egyet sem választ: a helyes 16 - 5 = 11.

Gráfnál a fokszámösszeget tekintik élszámnak. A hétpontú, csupa 4-ed fokú gráfnak nem 28 éle van, hanem 28 / 2 = 14. A fokszámösszeg minden élt kétszer számol.

Gráfot rajzolnak, de nem számolják meg a fokszámokat. Egy elfelejtett vagy fölöslegesen behúzott él az egész rajzot rosszá teszi. Rajzolás után minden pontnál számold meg az éleket, és vesd össze a feladattal.

11. Ellenőrzés

1. Egész szám-e az eredmény? A lehetőségek száma mindig egész szám, és nem lehet negatív. Ha tört vagy negatív szám jön ki, elrontottál valamit.

2. Kis esetben sorold fel. Ha a lehetőségek száma kicsi (néhány tucatnál kevesebb), írd fel rendezetten az összeset, és számold meg. A Mintapélda 1 12 száma vagy a Mintapélda 4 13 sorrendje egy perc alatt felírható. Az útmutatók szerint a rendezett felsorolás alapján adott helyes válasz teljes pontot ér, tehát ez nem csak ellenőrzés, hanem önálló megoldás is.

3. Számold ki két úton. A Mintapélda 3-at esetszétválasztással és komplementerrel is megoldottuk, mindkettő 11-et adott. A Mintapélda 2-t csomaggal és helyekkel is, mindkettő 48-at. Ha a két út ugyanazt adja, szinte biztosan jó.

4. Nézd meg a felső korlátot. A feltételes eset nem lehet több, mint az összes. Ha öt ember összesen 5! = 120-féle sorrendben állhat, a feltételesen kapott 48 kevesebb, tehát ésszerű. Ha 150 jönne ki, az biztosan hibás.

5. Gráfnál pontonként ellenőrizz. Minden pontnál számold meg a belőle kiinduló éleket, add össze, és nézd meg, hogy az összeg pontosan az élszám kétszerese-e. Ha nem páros szám jön ki, valahol tévedtél.

6. Írd ki a választ szövegesen. A feladatlap tudnivalói szerint a végeredményt szöveges válaszban is közölni kell: „Tehát 13-féleképpen lehet bedobni a 300 Ft-ot.”

12. Összefoglaló

• Szorzási szabály: egymás után jövő döntéseknél a lehetőségek számát összeszorzod, például 5 · 3 · 2 = 30.
• Összeadási szabály: egymást kizáró eseteknél esetenként számolsz, és a végén összeadod a lehetőségeket.
• Feltételes feladatnál a feltételes hellyel kezdesz, például páratlan számnál az utolsó számjeggyel.
• n különböző elem sorrendjeinek száma n!, ahol n! = n · (n - 1) · ... · 2 · 1, és 0! = 1.
• Ha két elemnek egymás mellett kell állnia, egy csomagnak veszed őket, és a végén a csomagon belüli 2-féle sorrenddel is szorzol.
• Kiválasztásnál, ha nem számít a sorrend, (n alatt k) = n! / (k! · (n - k)!) a lehetőségek száma.
• Azonos elemek sorrendjénél a különböző elemek helyét választod ki, például (4 alatt 2) = 6 sorrend két 100-asra és két 50-esre.
• Komplementer módszer: jó esetek száma = összes eset - rossz esetek; „legalább” és „legfeljebb” esetén érdemes elővenni.
• Egy n elemű halmaznak 2ⁿ részhalmaza van.
• A gépen az n! és az nCr gomb indoklás nélkül elfogadott, de le kell írnod, mit számolsz vele.
• A gráf pontokból (csúcsokból) és élekből áll; egy pont fokszáma a belőle kiinduló élek száma.
• Bármely gráfban a fokszámok összege az élek számának kétszerese, ezért a fokszámösszeg mindig páros.
• Nincs olyan gráf, amelyben páratlan sok páratlan fokszámú pont van, például öt darab 3-ad fokú pont.

13. Kulcsfogalmak

• Szorzási szabály - ha egy feladat egymás utáni döntésekből áll, a lehetőségek száma a döntésenkénti lehetőségek szorzata.
• Esetszétválasztás - a feladatot egymást kizáró esetekre bontod, esetenként számolsz, és az eredményeket összeadod.
• Faktoriális - n! = n · (n - 1) · ... · 2 · 1, az n különböző elem összes sorrendjének száma; 0! = 1.
• Binomiális együttható - (n alatt k) = n! / (k! · (n - k)!), ennyiféleképpen választhatsz ki n különböző elemből k darabot, ha a sorrend nem számít.
• Komplementer módszer - az összes eset számából kivonod a feltételnek nem megfelelő esetek számát.
• Rendezett felsorolás - minden lehetőséget szabályos sorrendben felírsz; helyes válasszal teljes pontot ér.
• Gráf - pontokból és a pontokat összekötő élekből álló alakzat, amely kapcsolatokat ábrázol.
• Gráf csúcsa (pontja) - a gráf egy pontja, például egy ember vagy egy város.
• Gráf éle - két pontot összekötő vonal, például egy kézfogás vagy egy út.
• Csúcs fokszáma - a csúcsból kiinduló élek száma.
• Fokszámösszeg - a gráf összes pontjának fokszámát összeadva kapott szám; mindig az élszám kétszerese, ezért páros.
• Ne keverd össze: sorbarendezés és kiválasztás - sorbarendezésnél számít a sorrend (5 · 4 = 20 elnök-titkár pár), kiválasztásnál nem ((5 alatt 2) = 10 küldöttség).
• Ne keverd össze: fokszámösszeg és élszám - a fokszámösszeg minden élt kétszer számol, az élszám ennek a fele.

14. Lehetséges vizsgakérdések és rövid válaszok

1. Mikor szorzod és mikor adod össze a lehetőségek számát?

Akkor szorzol, ha a feladat egymás után jövő döntésekből áll, és mindegyik megtörténik, például előbb az utolsó számjegyet, aztán a többit választod ki. Akkor adsz össze, ha a feladat egymást kizáró esetekre bomlik, és csak az egyik eset valósul meg. Például a háromtartományos színezésnél a két színnel és a három színnel való színezés kizárja egymást, ezért 18 + 6 = 24. A két színnel való színezésen belül viszont a színpár kiválasztása és a színezés egymás után jön, ezért 3 · 6 = 18.

2. Hány háromjegyű, különböző számjegyekből álló páros szám alkotható az 1, 2, 3, 4, 5 számjegyekből?

A feltételes hellyel kezdünk: az utolsó számjegy páros, tehát 2 vagy 4, ez 2 lehetőség. A százasok helyére a maradék 4 számjegy közül választunk, a tízesek helyére a maradék 3 közül. A szorzási szabály szerint 2 · 4 · 3 = 24 ilyen szám van. Ugyanígy ment a 2026. májusi I. rész 11. feladata (Mintapélda 1).

3. Hányféle sorrendben állhat sorba öt ember, ha két adott ember egymás mellett áll?

A két embert egy csomagnak tekintjük, így 4 egységet kell sorba rendezni, ez 4! = 24 lehetőség. A csomagon belül a két ember 2-féle sorrendben állhat. A szorzási szabály szerint 2 · 24 = 48 sorrend van. Ha azt kérdezik, hányban nem állnak egymás mellett, az összes 5! = 120 sorrendből kivonjuk a 48-at, és 72 marad.

4. Mi a különbség az 5 · 4 és az (5 alatt 2) között?

Mindkettő öt emberből két ember kiválasztásáról szól. Az 5 · 4 = 20 akkor kell, ha számít a sorrend, például elnököt és titkárt választunk. Az (5 alatt 2) = 10 akkor kell, ha nem számít a sorrend, például két fős küldöttséget választunk. A 20 azért kétszer akkora, mert minden párt kétszer számol, egyszer egyik, egyszer másik sorrendben.

5. Mikor érdemes a komplementer módszert használni? Mutasd meg egy példán!

Akkor, ha a rossz esetek kevesebben vannak, vagy egyszerűbben számolhatók, mint a jók; jellemzően „legalább” vagy „legfeljebb” esetén. Négy függvény közül legalább kettőt kell kiválasztani. Az összes kiválasztás 2⁴ = 16, mert minden függvényről eldöntjük, benne van-e. A rossz esetek: pontosan egy függvény 4-féleképpen, egyet sem 1-féleképpen, ez 5. Tehát 16 - 5 = 11 jó kiválasztás van. Esetszétválasztással ugyanez: 6 + 4 + 1 = 11.

6. Mi az összefüggés egy gráf fokszámainak összege és éleinek száma között, és miért?

Bármely gráfban a pontok fokszámának összege az élek számának kétszerese. Azért, mert minden él két pontot köt össze, így a fokszámok összeadásakor minden élt kétszer számolunk, egyszer mindkét végénél. Ebből következik, hogy a fokszámösszeg mindig páros szám. Például egy hétpontú gráfban, ahol minden pont 4-ed fokú, a fokszámösszeg 28, tehát az élek száma 14.

7. Van-e olyan ötpontú gráf, amelyben minden pont fokszáma 3?

Nincs. Ha lenne, akkor a fokszámok összege 5 · 3 = 15 lenne, ami páratlan szám. Bármely gráfban viszont a fokszámok összege az élszám kétszerese, tehát páros. Ezért ilyen gráf nem létezik. Ez a 2026. októberi I. rész 11. feladata volt.

8. Egy hétpontú, hétélű gráfban hat pont fokszáma 1, 1, 2, 2, 3, 3. Mennyi a hetedik pont fokszáma?

A fokszámok összege az élszám kétszerese, tehát 2 · 7 = 14. A megadott hat fokszám összege 1 + 1 + 2 + 2 + 3 + 3 = 12. A hetedik pont fokszáma ezért 14 - 12 = 2. Rajzolás után pontonként ellenőrizd, hogy minden fokszám stimmel. Ugyanez volt a gondolat a 2024. májusi II. rész 18. a) feladatában (Mintapélda 6).