Gráfelmélet - elnevezések, összefüggések
Lépésenként kattintgatva
Önműködően lejátszva
Egyszerre megmutatva
Csak az eredmény
Mit kell tudnom?
A gráfelmélet alapfogalma a gráf, olyan struktúra, ami csúcsokból és élekből áll, minden él két csúcs között fut.
A csúcsok fokszáma, foka: a rá illeszkedő élek száma
A csúcs be-foka a csúcsba futó, a ki-foka a belőle induló irányított élek száma.
Reguláris gráf: minden csúcsnak azonos a fokszáma.
Többszörös (párhuzamos) élek: ugyanazt a két csúcsot kötik össze.
Hurokél: azonos a két végpontja
Izolált csúcs: amelyhez nem csatlakozik él.
Üres gráf: nincsenek élei, a csúcsai izoláltak.
Teljes gráf: bármly két csúcsa között van él.
Síkbeli gráf: megrajzolható a képe úgy, hogy az élek nem metszik egymást.
Euler tétel: Síkbeli gráfban a csúcsok + tartományok száma = élek száma + 2
séta: egy csúcs-él-csúcs-él-....-csúcs sorozatot sétának nevezünk (a csúcsok és az élek is ismétlődhetnek tetszés szerint)
vonal: összefüggő élsorozat, amely egy élen nem halad át többször
út: vonal, amely egy csúcsot nem érint többször
kör, körvonal: vonal, amelynek a végpontja a kezdőponttal azonos
Összefüggő gráf: van út bármelyik két csúcsa között
Euler vonal egy olyan vonalat, mely a gráf minden élét pontosan egyszer tartalmazza.
Hamiltonian út egy olyan út, mely a gráf minden csúcsát érinti.
Hamilton kör egy olyan Hamilton út ami zárt.
Fa (fa-gráf): kör nélküli összefüggő gráf.
A fa csúcsainak száma=élek száma+1
Erdő: minden komponense fa.
Az erdő csúcsainak száma=élek száma+komponensek száma.
