Definíció:
Körnek nevezzük a gráf egy adott pontjába visszavezető utat, azaz olyan élsorozatot, amely a kiindulási pontba tér vissza és benne minden él csak egyszer szerepel.
Definíció:
Ha egy gráf összefüggő és nem tartalmaz kört, akkor azt fának nevezzük.
Például: A számítógépeknél használt menü struktúrák vagy a családfák is fagráfok.
Definíció:
Egy gráfot erdőnek (ligetnek) nevezünk, ha nem tartalmaz kört. A liget komponensei (összetevői) fák.
Tételek:
• A fa bármely két pontját egyetlen út köti össze.
• Ha egy fának bármely élét elhagyjuk, akkor a gráf nem összefüggő.
• Ha egy fának bármely két olyan pontját összekötjük, amelyek között eddig nem volt él, akkor a gráf már tartalmaz kört.
• Az „n” pontú fának n-1 éle van.
Egy tanulságos feladat:
Vajon nagyapáink dédapjai ugyanazok a személyek-e, mint dédapáim nagyapjai?
Próbáljuk ezt gráfon szemléltetni:
A megoldás leolvasható: nagyapáink dédapjai nem teljesen ugyanazok a személyek, mint dédapáim nagyapjai.
Comments are closed, but trackbacks and pingbacks are open.