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



Скачать 14.82 Kb.
Дата04.07.2013
Размер14.82 Kb.
ТипВопросы к экзамену
Вопросы к экзамену


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Похожие:

Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconАлгоритм Зыкова
Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный...
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconБилеты по Дискретной математике «Теория Графов»
Понятие графа (орграфа). Смежность и инцидентность в графе. Классы (типы) графов
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconVi. Элементы теории графов. Основные понятия теории графов. Определение Графом
Определение Графом называется совокупность 2-х множеств Х и У. Х это множество точек, называемых вершинами графа, а у это множество...
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconОсновные понятия теории графов Теорема 1
Теорема Пусть в графе g p вершин и q ребер. Пусть deg VI степень вершины VI. Тогда
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconПонятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе

Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconОсновные понятия теории графов
Т. е граф – это пара G=(V,E), где V множество вершин, а e семейство пар ребер ei=(vi1, vi2), vij принадлежит V. Вершины графа можно...
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconВершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф
Докажите неравенство, где вершинная связность графа G, реберная связность, минимальная степень вершины графа
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconЛекция 11: Графы и деревья
...
Вопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры iconОсновные понятия теории графов граф и его виды
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org