Teljes gráf

A gráfok csúcsokból és őket összekötő élekből állnak.

Az olyan gráfokat, ahol minden csúcs össze van kötve minden csúccsal, teljes gráfoknak nevezzük. Ez azt jelenti, hogy az összes lehetséges élet behúzzuk a gráfba.

teljes gráf

Az élek száma egy teljes gráfban:  fraction numerator n times left parenthesis n minus 1 right parenthesis over denominator 2 end fraction
Indoklás: A gráf minden csúcsából a többi (n - 1) csúcshoz húznunk tehát élt. Így elvileg n (n - 1) élt kapnánk, ám ezt osztani kell kettővel, mert különben duplán számolnánk minden élt. Például  A és B csúcs között futó élt kétszer számolnánk: egyszer, amikor az A-ból induló éleket nézzük, és egyszer, amikor a B-ből kiinduló éleket.

Példa teljes gráfra

Feladat: Egy 8 tagú baráti társaság találkozik. Érkezéskor mindenki kezet fog mindenkivel. Hány kézfogás történt összesen?

Megoldás: A feladatot tudjuk gráf segítségével ábrázolni. A csúcsok az emberek, az élek a kézfogások. Mivel mindenki kezet fog mindenkivel, ezért ezt egy teljes gráffal tudjuk szemléltetni. A kézfogások (azaz az élek) száma a kérdés, ehhez tudjuk használni a képletet:  fraction numerator n times left parenthesis n minus 1 right parenthesis over denominator 2 end fraction equals fraction numerator 8 times left parenthesis 8 minus 1 right parenthesis over denominator 2 end fraction equals fraction numerator 8 times 7 over denominator 2 end fraction equals 28

Tehát 28 kézfogás történt a találkozó elején.

A következő Matek Oázis videókkal tanulhatsz a teljes gráfról

Halmazok, számelmélet, logika, gráfok
Gráfok
Gráfok
Gráfokkal kapcsolatos érettségi feladatok
Gráfok
KISOKOS III. rész  (5 témakör)
Gráfok - fogalmak, alapfeladatok
Gráfok - gyakorló feladatok 1. rész
Gráfok - gyakorló feladatok 2. rész
Gráfok - alapok
Gráfok - teljes gráf