Gráf fogalma

Königsberg városa és a környező terület régen Poroszországhoz tartozott. Jelenleg Kalinyingrád néven Oroszországhoz tartozik, bár nem szomszédos vele. Délről Lengyelország, nyugatról a Balti-tenger, északról és keletről Litvánia határolja.

A város a Pregel nevű folyó két partján terül el, amely azt 4 részre osztja. Az egyes részeket 7 db híd köti össze a jobb oldali mellékelt ábra szerint. A königsbergiek olyan útvonalat szerettek volna tervezni, hogy valaki a lakásából indul el és minden hídon csak egyszer sétál végig, majd visszatér a lakásába.

Euler az 1736-ban szembesült a „königsbergi séta” problémájával, és bebizonyította, hogy ilyen útvonal nem lehetséges. Ő evvel az egyszerűsített modellel dolgozott. Ez egyben a gráfelmélet kezdete is, bár csak a XIX. század végén kezdődött meg ennek az új matematika szakterületnek a fejlődése.
https://hu.wikipedia.org/wiki/K%C3%B6nigsbergi_hidak_probl%C3%A9m%C3%A1ja

Ha véges sok pont közül egyeseket vonallal összekötünk, akkor a kapott ábrát gráfnak nevezzük.

Definíció:

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.

Elnevezések, jelölések.

A gráfok pontjait egyszerűen pontoknak, vagy csúcspontoknak, vagy csúcsoknak nevezzük. A gráf pontjait nagy betűkkel, az éleit kis betűkkel jelöljük.

Ha két csúcs (pont) között több él húzódik, akkor párhuzamos, vagy másképp többszörös élről beszélünk.
Ha egy él mindkét végpontja ugyanaz a pont, akkor hurokélről beszélünk.

A gráf egy pontjába összefutó élek számát a pont fokszámának nevezzük.
A königsbergi gráfban az A csúcs fokszáma = 5, a B, C és D csúcsé pedig = 3.

Egyszerű gráfról beszélünk, ha egy gráfban nincs sem párhuzamos él, sem hurokél.

Teljes gráfnak nevezzük azokat a gráfokat, amelyeknek minden pontjából a gráf összes többi pontjához vezet egy-egy él.

A gráf összefüggő, ha bármely pontjából bármely más pontjába élek mentén el lehet jutni.