Ruský jazyk

Metod «kriticheskogo» klassa grafow

Vydavateľstvo: LAP LAMBERT Academic Publishing
Rok vydania: 2010
Formát: Paperback
Rozmer: 220 x 150 mm
Jazyk: Ruský jazyk
ISBN: 9783843301428

Na objednávku, dodanie 2-4 týždne

45.36 €

bežná cena: 50.40 €

O knihe

V knige rassmatriwaetsq problema opredeleniq granicy mezhdu polinomial'noj razreshimost'ü i NP-polnotoj dlq klassicheskih grafowyh zadach w reshetke zamknutyh otnositel'no udaleniq wershin klassow obyknowennyh grafow (reshetke nasledstwennyh klassow). Izuchenie dannoj granicy wedetsq na osnowe metoda «kriticheskogo» klassa grafow - poiska nasledstwennyh klassow, igraüschih osobuü rol' pri reshenii upomqnutoj zadachi demarkacii. Issleduütsq dwa tipa takih razdelitelej - granichnye i minimal'nye slozhnye klassy grafow, odin iz kotoryh (minimal'nye slozhnye klassy) byl wweden w rassmotrenie awtorom. V monografii predstawleny rezul'taty awtora po strukture granichnyh klassow dlq rqda zadach na grafah. Naprimer, pokazywaetsq, chto dlq obeih zadach o 3-raskraske (wershinnogo i rebernogo wariantow) mnozhestwo granichnyh klassow kontinual'no. V ätoj knige wperwye pred#qwleny konkretnye primery minimal'nyh slozhnyh klassow (ranee ne bylo izwestno, suschestwuüt li oni woobsche). S drugoj storony, wydelqetsq tip zadach, dlq kotoryh takih ne suschestwuet. Dannaq kniga prednaznachena dlq studentow, aspirantow i nauchnyh rabotnikow, zanimaüschihsq diskretnoj matematikoj.