Вопросы к зачету по курсу проф. Н. Н. Петрова

"ЗАДАЧИ ТЕОРИИ ГРАФОВ"

  1. Комбинаторное и топологическое определения графа.
  2. Смежность и инцидентность.
  3. Деревья.
  4. Хроматическое число графа.
  5. Кликовое число графа.
  6. Постановка задачи вершинного поиска.
  7. Теорема о субмодулярности граничного оператора.
  8. Теорема о существовании k-клубка.
  9. Теорема о существовании увеличивающегося k-клубка.
  10. Теорема о существовании монотонной выигрывающей программы.
  11. Теорема о дополнении графа интервалов.
  12. Теорема Гилмора-Хоффмана о характеризации графа интервалов (3 утверждения).
  13. Теорема о вершинно-поисковм числе графа интервалов.
  14. Теорема о вершинно-поиском числе произвольного графа.
  15. Теорема о матрице сетей-ключей.
  16. Теорема о характеризации хордального графа в терминах РЕ-упорядочения.
  17. Теорема о характеризации хордального графа терминах минимальных разделителей.
  18. Совершенство хордального графа.
  19. Совершенство дополнения хордального графа.
  20. Теорема о характеризации графа с единичным полицейским числом.

 

 

ЛИТЕРАТУРА

  1. Айзекс Р. Дифференциальные игры.-М.: Мир,1967.- 480с.
  2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. Наука. М.,1990. 384с..
  3. Fomin F. V. (Ed.) Graph-Theoretic Concepts in Computer Science. Springer-Verlag, Berlin, Heidelberg, 2006. 358p.
  4. West D.B. Introduction to Graph Theory. Prentice Hall, 1996.-512p.
  5. Alpern S., Gal S. The theory of search games and rendezvous. Kluver,2003.-320p.
  6. Головач П.А. Экстремальные задачи поиска на графах. Дис…канд. физ-мат. наук.-СПб., 1990.-158с.
  7. Фомин Ф.В. Задачи преследования и поиска на графах. Дис…канд. физ.-мат. наук.- СПб.,1996.-106с.