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
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
