10. évfolyam
Teljes gráf éleinek száma
Információ ehhez a munkalaphoz
Szükséges előismeret
Gráfelméleti alapfogalmak: csúcs, él, teljes gráf.
Módszertani célkitűzés
A teljes gráf élei számának meghatározása.
Az alkalmazás nehézségi szintje, tanárként
Könnyű, nem igényel külön készülést.
Módszertani megjegyzés, tanári szerep
LEHETSÉGES HÁZI FELADATOK
Szilveszterkor egy 15 fős baráti társaságban éjfélkor mindenki mindenkivel koccint. Hány koccintás történt összesen?
Egy 10 gépből álló számítógépes hálózatnál minden gép minden géppel össze van kötve. Összesen hány kapcsolatot kellett kiépíteni?
TOVÁBBHALADÁSI LEHETŐSÉGEK
- Komplementer gráf: egy egyszerű G gráf komplementere az a G’ gráf, amely a G-t teljes gráffá egészíti ki. Vagyis: amelyik két csúcs össze van kötve a G-ben, azok a G’-ben nincsenek, illetve amelyek nincsenek összekötve a G-ben, azok G’-ben össze vannak kötve. (G és G’ uniója a teljes gráf.)
- Komplementer gráf éleinek száma: ha egy n csúcsú egyszerű G gráfnak k éle van, akkor a komplementerének
éle van.
KAPCSOLÓDÓ ÉRDEKESSÉGEK
A 2 csúcsú teljes gráf éleinek száma 1. A 3 csúcsú teljes gráf éleinek száma 3. A 4 csúcsú teljes gráf éleinek száma 6.
Az 5 csúcsú teljes gráf éleinek száma 10. A 6 csúcsú teljes gráf éleinek száma
15, és így tovább.
1-3-6-10-15-stb. számú pont szabályos háromszögalakzatban helyezhető el, emiatt ezeket a számokat háromszögszámoknak nevezik.
Felhasználói leírás
Egy 8 fős társaságban mindenki kézfogással üdvözli a másikat. Összesen hány kézfogás történik? Indítsd el a bemutatót!
Tanácsok az interaktív alkalmazás használatához
A panelen lévő csúszkával megadható a teljes gráf csúcsainak száma.
A Lejátszás gombbal (
) kirajzolhatók a teljes gráf élei, a gráf melletti csúszkával a bemutató bármely állapota megjeleníthető.
Az Újra gombbal (
) törölhetők az élek.
Feladatok
- Figyeld meg az alábbiakat:
a) Az első személy hány személlyel fog kezet?
b) A második személy hány olyan személlyel fog kezet, akit még nem üdvözölt?
c) A harmadik személy hány olyan személlyel fog kezet, akit még nem üdvözölt?
d) Gondold végig ugyanezt mindegyik személy esetében!INFORMÁCIÓMegoldás:
a) 7
b) 6
c) 5
d) 4, 3, 2, 1, 0.) - Összesen hány kézfogás történt?
INFORMÁCIÓMegoldás: 28
- Egy n fős társaság esetén hány kézfogás történne összesen?
INFORMÁCIÓMegoldás:
Ez adódik a számtani sorozat összegképletéből.
Megemlíthető, hogy mivel a teljes gráfban minden él minden éllel össze van kötve, ezért összesen annyi éle van a teljes gráfnak, ahányféleképpen n csúcsból kiválasztható 2, vagyis