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