Metod Kriticheskogo Klassa Grafov

V knige rassmatrivaetsya problema opredeleniya granitsy mezhdu polinomial'noy razreshimost'yu i NP-polnotoy dlya klassicheskikh grafovykh zadach v reshetke zamknutykh otnositel'no udaleniya vershin klassov obyknovennykh grafov (reshetke nasledstvennykh klassov). Izuchenie dannoy granitsy vedetsya na osnove metoda kriticheskogo klassa grafov - poiska nasledstvennykh klassov, igrayushchikh osobuyu rol' pri reshenii upomyanutoy zadachi demarkatsii. Issleduyutsya dva tipa takikh razdeliteley - granichnye i minimal'nye slozhnye klassy grafov, odin iz kotorykh (minimal'nye slozhnye klassy) byl vveden v rassmotrenie avtorom. V monografii predstavleny rezul'taty avtora po strukture granichnykh klassov dlya ryada zadach na grafakh. Naprimer, pokazyvaetsya, chto dlya obeikh zadach o 3-raskraske (vershinnogo i rebernogo variantov) mnozhestvo granichnykh klassov kontinual'no. V etoy knige vpervye pred"yavleny konkretnye primery minimal'nykh slozhnykh klassov (ranee ne bylo izvestno, sushchestvuyut li oni voobshche). S drugoy storony, vydelyaetsya tip zadach, dlya kotorykh takikh ne sushchestvuet. Dannaya kniga prednaznachena dlya studentov, aspirantov i nauchnykh rabotnikov, zanimayushchikhsya diskretnoy matematikoy.