A gráfelméletről VI.
Tarcsay Tamás
2007/11/23 12:31
882 megtekintés
A cikk lejárt! Valószínű, hogy már nem aktuális információkat tartalmaz!
Az emelt szintű érettségi vizsga anyagában szereplő, gráfelméleti témákat tárgyaló sorozatunk utolsó részéhez érkeztünk. Néhány feladat megoldását mutatjuk még be.

Az előző részben kitűzött feladat így szólt:

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é!

Legyen a fagráf pontjainak száma n, az elsőfokú pontok száma e, a legalább harmadfokú pontok száma h! Ekkor a másodfokú pontok száma ne –   h.

A fagráf éleinek száma n – 1. Tekintettel arra, hogy bármely gráf pontjai fokszámainak összege az élei számának kétszerese, a vizsgált fa fokszámainak összege 2(n – 1).

A fentiek alapján igaz a következő egyenlőtlenség:A fentiek alapján igaz a következő egyenlőtlenség:

Az állítást bebizonyítottuk.

Tekintsük a következő problémát!

A 0-tól hatig pontozott dominó 28 kövét körbe lehet-e rakni úgy, hogy egymás mellett azonos számok szerepeljenek?

A feladat szemléltetésére használhatjuk a következő gráfot:

A gráf élei az egyes dominókat (a hurok élek a duplákat) ábrázolják. A probléma úgy is fogalmazható, hogy van-e ebben a gráfban Euler kör.

Mivel a gráf összefüggő, és minden pont fokszáma páros létezik benne Euler kör (zárt Euler vonal).

Búcsúzóul még egy feladat az olvasó számára:

Az 1, 2, 3, 4, 5, 6, 7, 8, 9 számokat el lehet-e helyezni egy körön úgy, hogy bármely két egymás melletti szám összege ne legyen osztható se hárommal, se öttel, se héttel?

Irodalom:Irodalom:

  1. Barabás Boglárka: Gráfelméleti feladatgyűjtemény (Szakdolgozat, készült a SZTE Bolyai Intézetében)

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