Königsbergi hidak

königsbergi hidak
A XIX. század elején hét híd volt Königsbergben (akkor Kelet-Poroszország, ma Kalinyingrád, Oroszország). Ezek a Pregel (vagy Pregolya) folyó különböző ágait keresztezték, ahogy azt az ábra vázlatosan mutatja.

századból származik, s a "Königsbergi hidak" problémájaként ismert. A várost átszelő Pregel folyó hét hídjával kapcsolatban merült fel, hogy bejárhatók-e egyetlen séta keretében, úgy, hogy mindegyiken pontosan egyszer haladunk át.

minden élen pontosan egyszer megyünk végig? (lásd: Königsbergi hidak, Euler-kör)
minden csúcsot pontosan egyszer érintünk? (lásd: Hamilton-út) ...

Lásd még: Gráfelmélet, Fokszám, Összefüggő, Gráf, Részgráf