Három ház–három kút-probléma
Megjelenés
(Három ház–három kút-gráf szócikkből átirányítva)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f3/Biclique_K_3_3.svg/100px-Biclique_K_3_3.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b9/H%C3%A1rom_h%C3%A1z-h%C3%A1rom_k%C3%BAt-probl%C3%A9ma.svg/100px-H%C3%A1rom_h%C3%A1z-h%C3%A1rom_k%C3%BAt-probl%C3%A9ma.svg.png)
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