DOI:
Автор:
Подоляка А.Н., Національний аерокосмічний університет ім. М. Є. Жуковського «Харківський авіаційний інститут», Харків, Україна
Подоляка О.А., Харківський національний автомобільно-дорожний університет, м. Харків, Україна
Скакаліна О.В., ПНТУ ім. Ю.Кондратюка, м. Полтава, Україна
Мова статті: російська
Анотація:
У роботі розглядається клас поліноміально вирішуваних задач, які зводяться до задачі покриття дводольних графа зірками, а також деякі схожі складновирішувані задачі, зокрема, комівояжера, тривимірного сполучення і задачі про покриття множин.
Ключові слова:
реберне покриття графа, зірки, цикли, паросполучення
Використана література:
1. Гери М. Р. Вычислительные машины и труднорешаемые задачи / М. Р. Гери, Д. С. Джонсон. – М.: Мир, 1982. – 416 с.
2. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: МЦНМО, 2000. – 956 с.
3. Ловас Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер. – М.: Мир, 1998. – 653 с.
4. Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц. – М.: Мир, 1985. – 510 с.
5. Петровский А. Б. Пространства множеств и мультимножеств / А. Б. Петровский. – М.: Едиториал УРСС, 2003. – 248 с.
6. Хопкрофт Д. Введение в теорию автоматов, языков и вычислений / Д. Хопкрофт, Р. Мотвани, Д. Ульман. – 2-е изд. – М.: Вильямс, 2002. – 528 с.
7. Эвнин А. Ю. Вокруг теоремы Холла: учебное пособие / А. Ю. Эвнин. – Челябинск: Изд-во ЮУрГУ, 2004. – 71 с.