A gráfelméletről V.
Tarcsay Tamás
2007/11/22 14:52
824 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.
Az előző cikkünk végén az iránt érdeklődtünk, hogy hány éle van egy n pontú teljes gráfnak?

A teljes gráf olyan egyszerű gráf, amelyekben bármely két pont szomszédja egymásnak. Ebből következően az ilyen gráfoknak pontosan annyi éle van, ahány kételemű részhalmazt tudunk létrehozni a pontjaikból:

Leonhard Euler

Ha a gráfelmélet eredetéhez nyúlunk vissza, akkor feltétlenül említést kell tenni a Königsbergi hidak problémájáról. Erről a témáról részletesen írt néhány évvel ezelőtt Dr. Munkácsy Katalin tanárnő egy cikkében. Mielőtt továbblépünk, olvassuk el ezt! Leonhard Euler akkor, amikor választ adott a Königsbergi polgárok kérdésére, megteremtette a gráfelmélet alapjait. A probléma forrása lett néhány fontos gráfelméleti fogalom kialakulásának is:

–                –                séta, körséta

–                –                vonal, körvonal

–                –                út, kör

·                ·                ·                ·                Euler vonal, Euler kör

·                ·                ·                ·                Hamilton út, Hamilton kör

Ha az emelt szintű érettségi vizsga követelményeit szem előtt tartjuk, akkor a most megismert fogalmakat továbbiak megalkotására használjuk fel.

Egy gráfot összefüggő gráfnak nevezünk, ha bármely két pontja között van út.

A korábban vizsgált gráfjaink között a Königsbergi hidak problémáját szemléltető gráf és a teljes gráfok voltak összefüggők.

Az olyan egyszerű, összefüggő és körmentes gráfokat, amelyekben nincs kör, fagráfnak (röviden: fa) hívjuk.

Keressünk különböző számú pontokkal rendelkező fákat!

Fák

A tapasztalataink alapján megfogalmazhatjuk azt a sejtést, hogy egy n pontú fának n-1 éle van. Ez az állítás bizonyítható.

Befejezésül egy feladat:

Bizonyítsuk be, hogy egy legalább 2 pontú fagráfban legalább kettővel nagyobb az elsőfokú pontok száma, mint a legalább harmadfokúaké!

Tarcsay Tamás

Csatlakozz hozzánk!

Ajánljuk

European Schoolnet Academy Ingyenes online tanfolyamok tanároknak
School Education Gateway Ingyenes tanfolyamok és sok más tanárok számára
All you need is code Minden a kódolás tanulásához
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek