Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степен - rita.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) 1 15.92kb.
«Волшебный компьютер» (35 часов) 1 127.28kb.
Вопросы к экзамену по теории игр 1 7.43kb.
1. Многозначность понятия «информация», классификация информации... 1 16.91kb.
Вопросы к экзамену (зачету) по охране труда 2013, курдюкова е а. 1 30.58kb.
Определите основные факторы, влияющие на изменение стоимости облигации 1 46.48kb.
Лекция предварительные замечания к курсу микроэкономики сфера применения... 1 75kb.
Вопросы к промежуточной аттестации по биологии за курс 9 класса 1 12.87kb.
1. информационное право: наука, учебная дисциплина. Отрасль праву... 1 76.23kb.
Вопросы к экзамену по курсу «Технология и организация производства» 1 28.08kb.
Вопросы к зачету по дисциплине «административное право» 1 20.33kb.
Правила внутреннего распорядка студентов и слушателей филиала Московского... 1 61.55kb.
Публичный отчет о деятельности моу кассельская сош 2 737.71kb.
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов - страница №1/1

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


  1. Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры.

  2. Операции над графами. Подграфы. Дополнение графа. Привести примеры.

  3. Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры.

  4. Цепи, маршруты (пути), циклы (контуры) в графе (орграфе). Количество всех путей (маршрутов) длины к в ориентированном псевдографе (псевдографе). Примеры.

  5. Связность графа. Компоненты связности. Матрица связности. Пример.

  6. Алгоритм выделения компонент связности. Пример.

  7. Полные, двудольные, однородные графы. Пример.

  8. Реберные графы. Нахождение матриц смежности, степеней вершин, количества ребер реберного графа через данные исходного графа. Примеры.

  9. Поиск путей (маршрутов) с минимальным числом дуг (ребер) в орграфе (графе). Алгоритм фронта волны. Привести пример.

  10. Расстояние в графах. Матрица расстояний. Диаметр, радиус, центр графа. Привести примеры.

  11. Нагруженные графы. Расстояние, эксцентриситет, радиус в нагруженном графе. Алгоритм нахождения кратчайшего остова в награжденном графе.

  12. Алгоритм Флойда нахождения кратчайшего маршрута в нагруженном графе.

  13. Алгоритм Форда-Беллмана нахождения кратчайшего маршрута в нагруженном графе.

  14. Алгоритм Дейкстеры нахождения минимального пути в нагруженном графе. Пример.

  15. Эйлеровы цепи и циклы в графах. Эйлеровы графы. Необходимое и достаточное условие существования эйлерова цикла. Примеры.

  16. Алгоритм выделения эйлерова цикла в графе. Пример.

  17. Гамильтоновы цепи и циклы в графах. Гамильтоновы графы. Достаточные условия существования гамильтонова цикла.

  18. Деревья. Корневые деревья. Свойства деревьев. Остов графа. Построение остова графа. Пример.

  19. Цикломатическое число графа. Цикловой базис. Выделение базиса в графе. Пример.

  20. Раскраска вершин и ребер графа. Хроматическое число графа. Независимые множества вершин и паросочетания. Точный алгоритм раскрашивания.

  21. Изоморфизм графов. Планарные графы. Раскрашиваемость планарного графа пятью красками. Гипотеза четырех красок.