Három ház–három kút-probléma

A Wikipédiából, a szabad enciklopédiából
a gráf
nem oldható meg

A három ház–három kút-probléma (vagy víz–gáz–villany-probléma, három közmű problémája) a gráfelméleti Kuratowski-tételben szereplő egyik gráfhoz – a három ház–három kút-gráfhoz – kapcsolódó probléma.

A probléma így fogalmazható meg: Tervezhető-e három házhoz és három kúthoz olyan síkbeli úthálózat, hogy minden háztól minden kútig vezessen egy-egy út és ezek az utak ne keresztezzék egymást? A válasz: Nem lehet.

A három ház–három kút-gráf egy teljes páros gráf, jelölése K3,3. Ez a gráf – az ötcsúcspontú teljes gráf (K5) mellett – meghatározó jelentőségű a gráfok síkbarajzolhatóságának problémakörében.

Források[szerkesztés | forrásszöveg szerkesztése]

  • három ház–három kút-probléma, Matematikai kislexikon, Budapest, Műszaki Könyvkiadó, 1972