A Hamilton-körök problémája csak síkba rajzolható gráfokra is NP-teljes?
Figyelt kérdés
2013. ápr. 28. 09:45
1/3 anonim 
válasza:
válasza:Azt hiszem ez nyitott kérdés. Bizonyos síkba rajzolható gráfokra belátták, hogy az.
2/3 anonim 
válasza:
válasza:They remain NP-complete even for undirected planar graphs of maximum degree three,[8] for directed planar graphs with indegree and outdegree at most two,[9] for bridgeless undirected planar 3-regular bipartite graphs, and for 3-connected 3-regular bipartite graphs
3/3 A kérdező kommentje:
Nem a legjobb az angolom :) Ez azt jelenti, hogy még akkor is az, ha a legnagyobb fokszám 3?
2013. ápr. 30. 06:33
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!