Ha szemléltetni szeretnénk, hogy Európa mely fővárosai között van közvetlen repülőjárat, azt legkönnyebben gráffal tehetjük meg. Ugyanez a módszer vethető be olyan egyszerűbb matematikai példában is, mint például kézfogások, koccintások vagy ismeretségek szemléltetésére.
Ebben a leckében a gráffal kapcsolatos alapfogalmakkal, összefüggésekkel és néhány példával fogunk megismerkedni.
Térjünk vissza a lecke elején említett példára: Európa mely fővárosai között van közvetlen repülőjárat. Elkezdhetnénk ezeket megadni hosszasan, szövegesen: Budapest-Berlin, Budapest-Amszterdam, Amszterdam-Bukarest, Berlin-Bécs stb… De ez eléggé átláthatatlan és unalmas lenne így. Helyette érdemes bevetni a gráffal való szemléltetést, pl. így:
Gráf alapfogalmak
A gráfokat pontok (csúcsok) és élek alkotják: a pontok az egyes városok, míg az élek jelképezik azt, ha van közöttük közvetlen repülős kapcsolat (ha nincs, akkor nem kötjük össze őket). Az egyes csúcsokhoz fokszámokat rendelhetünk: ez azt jelenti, hogy hány másik csúccsal áll összeköttetésben. Például, ha Budapestről 20 európai fővárosba juthatunk el repülővel, akkor Budapest fokszáma 20.
Összefüggés a fokszámösszeg és élek száma között
A fokszámokat összeadhatjuk, ekkor pontosan a behúzott élek számának kétszeresét kapjuk. Miért is? Gondolj bele: a Budapest-Berlin összeköttetést két csúcshoz is hozzászámoljuk, Budapesthez és Berlinhez is, de az valójában csak egy él (megjegyzés: emelt szinten és az egyetemi matek során már irányt, sőt számokat (pl. távolság (km), vagy repjegy ára (Ft)) is rendelhetünk az egyes élekhez, de erre középszinten nincs szükségünk).
n-pontú teljes gráf éleinek száma
Egy n-pontú teljes gráfban (amikor minden csúcs minden másikkal össze van kötve) az élek száma így adható meg:
A magyarázat egyszerű: minden egyes csúcsot saját magán kívül mindegyik másik csúccsal össze tudjuk kötni, azaz ha „n” csúcs van, akkor „n-1” darabbak tudjuk összekötni. Ezt mindegyik csúcsnál megtehetjük, azaz „n” alkalommal: n*(n-1). Igen ám, de ahogy fentebb említettem, ilyenkor minden élt kétszer számolunk, ezért ezt osztjuk kettővel.
Gráf témakörhöz két gyakorló feladat
1. feladat: Készíts egy olyan ötpontú gráfot, melyben az egyes csúcsok fokszáma: 0; 1; 1; 2; 2.
Ha van 0 fokszámú csúcs, érdemes először őt megjelölni, például egy pipával (ábrán: 1. lépés). Ezzel jelezzük magunknak, hogy ide nem húzunk élt. Ezt követi a magasabb fokszámú csúcsok felrajzolása: egy 2-es fokszámúnak behúzzuk az éleit, de a 0-ssal semmiképp sem köthetjük össze. Ezt követően ezt kipipáljuk (ábrán: 2. lépés) és valamelyik olyat is, amivel összekötöttük, mert meglett az egyik 1-es fokszámú csúcsunk is (ábrán: 3. lépés). Ezután már csak egyetlen élt húzunk be és létrejön a megoldás (ábrán: 4. és 5. lépés):
2. feladat: Egy iskolai kézilabda bajnokságon 6 csapat vesz részt, minden csapat minden másikkal pontosan egyszer játszik. Hány mérkőzés zajlott eddig le, ha még 8 van hátra?
Először számoljuk ki, hogy összesen hány mérkőzés zajlik le a bajnokság alatt. Minden csapat 5 másikkal játszik, azaz 6*5 = 30. Ne felejtsük el, minden játékot két csapat szemszögéből is beleszámoltunk (A csapat B csapattal és B csapat A csapattal), így ezt osztjuk kettővel: 30/2 = 15.
Ha 8 van még hátra, akkor 15 – 8 = 7 mérkőzés zajlott le eddig.
