Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе



Скачать 15.92 Kb.
Дата08.10.2012
Размер15.92 Kb.
ТипДокументы

  1. Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе.

  2. Подграф. Частичный граф. Частичный подграф. Полные, пустые и двудольные графы.

  3. Способы задания графов (орграфов). Изоморфизм и гомеоморфизм графов.

  4. Операции над графами.

  5. Степень вершины. Степень графа. Свойство распределения степеней вершин графа.

  6. Цепь: составная, сложная и простая цепи. Длина цепи. Расстояние между вершинами в графе. Диаметр графа.

  7. Связность графа. Вершинная и реберная связность графа. Компонента связности графа. Нахождение компонент связности.

  8. Связность в ориентированных графах. Компонента сильной связности. Нахождение компонент сильной связности. Конденсат орграфа.

  9. Циклы в графе. Эйлеров и гамильтонов циклы. Эйлеров граф. Гамильтонов граф. Критерий эйлеровости графа.

  10. Пространство циклов графа. Цикломатическая матрица. Цикломатический базис. Цикломатическое число. Алгоритм порождения циклов.

  11. Разделяющее множество. Разрез графа. Коциклический ранг графа. Поиск разрезов в графе.

  12. Внутренняя устойчивость графа. Пустой подграф. Число внутренней устойчивости. Алгоритм порождения пустых подграфов.

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

  14. Внешняя устойчивость графа. Положительная и отрицательная внешняя устойчивость.

  15. Раскраска графа. Хроматическое число. Алгоритм нахождения хроматического числа и раскраски графа.

  16. Оценки хроматического числа. Приближенная оценка (раскраска) по Ершову. Значение (оценка) хроматического числа для операций над графами.

  17. Рёберные графы. Критерий рёберности. Нахождения образа рёберного графа.

  18. Род поверхности и род графа. Укладка графа на поверхности. Планарные графы. Критерий планарности.

  19. Группа подстановок. Свойства группы. Вычисление произведения подстановок.

  20. Автоморфизм и группа автоморфизмов графа.

  21. Операции на группах автоморфизмов. Сложение, произведение, композиция и степень группы. Количественные характеристики групп.

  22. Группы автоморфизмов на композиционных графах.


Похожие:

Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconБилеты по Дискретной математике «Теория Графов»
Понятие графа (орграфа). Смежность и инцидентность в графе. Классы (типы) графов
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconАлгоритм Зыкова
Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный...
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconВопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры
Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconДискретная математика (2 часть из 2) Специальность: 230115 Программирование в компьютерных системах
Понятие неориентированного графа. Способы задания графа. Матрицы смежности. Путь в графе. Цикл в графе. Связный граф. Компоненты...
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconВершинная и реберная связность графов. Расстояния в графе. Изоморфизм графов. Разрезы в граф
Докажите неравенство, где вершинная связность графа G, реберная связность, минимальная степень вершины графа
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconПеречислите способы задания графов. Что такое матрица инциденций графа?
Оцените число ребер графа через число вершин и число компонент связности, если в графе р=11, k=3
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconПути в графах. Минимальный остов связного графа Нахождение минимального пути в графе
Путь в орграфе d из вершины V в вершину w, где V w, называется минимальным, если он имеет минимальную длину среди всех путей орграфа...
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconТема: Связность графов. Множества сочленения и разделяющие множества
В теории графов, понятие связности графа является ключевым при решении многих прикладных задач
Понятие графа (орграфа). Носитель и сигнатура. Классы (типы) графов. Смежность и инцидентность в графе iconАлгоритмы решения задач на графах на основе метода муравьиной колонии
Предложен и реализован метод решения задачи нахождения максимального паросочетания в графе и родственных ей задач раскраски графа...
Разместите кнопку на своём сайте:
ru.convdocs.org


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