Metod 'kriticheskogo' klassa grafow

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.