Három ház–három kút-probléma
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 öt csú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]- három ház–három kút-probléma, Matematikai kislexikon, Budapest, Műszaki Könyvkiadó, 1972