Fagráfok

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:

Nagyapáim dédapjai
Dédapáim nagyapjai

A megoldás leolvasható: nagyapáink dédapjai nem teljesen ugyanazok a személyek, mint dédapáim nagyapjai.

 

Print Friendly, PDF & Email

Comments are closed, but trackbacks and pingbacks are open.