Gráfelmélet

Ha adott egy V ponthalmaz és egy E élhalmaz, amely V-beli pontpárokat tartalmaz, akkor a V és E által létrejött struktúrát gráfnak nevezzük. Jelölése G(V,E). A gráfokat szemléletesen síkbeli ponthalmazokként ábrázoljuk, ahol bizonyos pontokat vonallal vagy görbével összekötünk.

Beszélhetünk irányított és irányítatlan gráfokról aszerint, hogy az éleiknek adunk-e irányítást, vagy nem.

Ha egy él kezdő- és végpontja is ugyanaz a pont, akkor az élet hurokélnek nevezzük. Ha két él ugyanaz a két pontot köti össze, akkor többszörös élekről beszélünk.

Egyszerű gráfoknak nevezzük azokat a gráfokat, amelyekben nincs hurokél és többszörös él.

Két él szomszédos, ha közös pontból indulnak ki. Két pont szomszédos, ha őket él köti össze.

Egy gráf összefüggő, ha bármely pontjából bármely másikba el lehet jutni szomszédos gráfbeli élek egy sorozata mentén.

Egy csúcs fokszáma egyenlő a csúcsba futó élek számával.

Izolált csúcsnak hívjuk azokat a csúcsokat, amelyekbe nem fut él, tehát a nulla fokszámú csúcsokat.

Tétel: Bármely véges gráfban a fokszámok összege az élek számának kétszeresével egyenlő.

Bizonyítás: A fokszámok összegének képzésénél minden élet kétszer számolunk, a két végpontjánál.