Вопросы к экзамену

Вид материала

Вопросы к экзамену

Подобный материал:

• В г. Воскресенске > к э. н., доцент К. А. Артамонова 2009 г. Вопросы к экзамену, 14.63kb.
• 8. Вопросы для подготовки к экзамену, 83.39kb.
• Вопросы к экзамену по дисциплине «Экономический анализ», 35.26kb.
• Вопросы к экзамену по курсу «Дифференциальные уравнения», 22.85kb.
• Кафедра финансов и кредита Вопросы к междисциплинарному Государственному экзамену, 85.13kb.
• Вопросы к экзамену по дисциплине «Психология управления», 11.1kb.
• Д. Н. Барышников ст пр., к полит, н. Вопросы к экзамену, 313.16kb.
• Вопросы к экзамену по курсу «Основы менеджмента», 31.86kb.
• Маркетинг предприятий отрасли примерный перечень вопросов к экзамену и тем курсовых, 108.14kb.
• Контрольные вопросы по дисциплине Деньги, кредит, банки в целом (вопросы к экзамену), 25.31kb.

Вопросы к экзамену

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