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

Az olyan ábrát, amely pontokból és azok közül néhányat (lehet, hogy egyet sem, de az is lehet, hogy mindet) összekötő vonalakból áll, ahol lényegtelen a vonalak alakja, gráfnak nevezzük. Az adott pontok a gráf csúcsai, a pontokat összekötő vonalak a gráf élei.

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: olyan vonal, amely kezdő- és végpontja azonos, ezen felül bármely más csúcsot legfeljebb egyszer érint
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 vonal, mely a gráf minden élét pontosan egyszer tartalmazza.
Hamilton út egy olyan út, amely a gráf minden csúcsán pontosan egyszer halad át.
Hamilton kör egy olyan kör, mely a gráf minden csúcsát érinti.

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.