A gráf fogalma

Gráfnak nevezzük pontoknak és éleknek a halmazát, ahol az élek pontokat kötnek össze, illetve az élekre pontok illeszkednek úgy, hogy minden élre legalább egy, legfeljebb két pont illeszkedik.

A gráfelmélet néhány alapfogalma

Teljes gráfok A gráfokpontjait egyszerűen pontoknak nevezzük, de használatos a csúcspont (csúcs), szögpont elnevezés is.

Ha egy élre két pont illeszkedik, akkor azt mondjuk, hogy az az él két pontot köt össze. Azt is mondjuk, hogy a P, Q pontok az e él végpontjai.

Megtörténhet, hogy ugyanazt a P, Q pontot két vagy több él köti össze, akkor ezeket párhuzamos (vagy többszörös) éleknek nevezzük.

Ha egy élre egy pont illeszkedik, azaz egy él végpontja azonos, akkor azt az élt hurokélnek nevezzük.

Ha egy gráfban nincsenek párhuzamos élek és nincs hurokél, akkor azt egyszerű gráfnak nevezzük.

Ha egy gráfnak mindegyik pontjából pontosan egy-egy él vezet a gráf összes többi pontjához, akkor azt teljes gráfnak nevezzük.

Példák gráfokra