Gráfelmélet - elnevezések, összefüggések

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.

393_1.svg

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.

393_2.svg

Síkbeli gráf: megrajzolható a képe úgy, hogy az élek nem metszik egymást.

393_3.svg

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

393_5.svg

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.

393_4.svg

Kulcsszavak: