A Hamilton-kör és az NP-teljesség problémájával foglalkozom, ezzel kapcsolatban lenne egy kérdésem. (? )
Figyelt kérdés
Tegyük fel, hogy valamilyen speciális tulajdonság alapján csoportokra tudom osztani a gráfokat. Ha belátom, hogy mindegyik csoportra tudok adni polinomhosszú algoritmust, ellenben ez a polinom csoportonként változó, akkor azzal lehet valamit kezdeni?2014. júl. 2. 11:28
1/5 anonim 
válasza:
válasza:Ha polinom időben tudod csoportokba osztani a gráfokat, akkor nyert ügyed van. Legalábbis, ha véges sok csoportod van.
2/5 A kérdező kommentje:
És ha megszámlálhatóan végtelen (pl. csúcsszám szerint)?
2014. júl. 2. 13:32
3/5 anonim válasza:
válasza:Csúcsszám szerint hiába csoportosítod a gráfokat, ugyanis ettől még nem tudsz polinomiális algoritmust adni.
(Szerintem egyébként korábban is sikerült már másnak is megszámolnia a csúcsokat...)
4/5 A kérdező kommentje:
Köszönöm az akonstruktív hozzászólásodat; nem azt mondtam, hogy csúcsszám szerint akarom csoportosítani, hanem példát adtam a megszámlálhatóan véges csoportosításra. Ennyi erővel azt is mondhattam volna, hogy síkbarajzolható gráfok esetén a tartományszám alapján akarom szétbontani a gráfokat (elvégre az is véges).
2014. júl. 2. 14:13
5/5 A kérdező kommentje:
*megszámlálhatóan végtelen, elnézést.
2014. júl. 2. 14:15
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!