Вопросы для повторения.
Граф. Неориентированный граф. Вершины и рёбра графа. Концевые вершины. Петля. Параллельные дуги. Ориентированный граф (орграф). Смежные рёбра. Инцидентные вершины и рёбра. Порядок графа. Изолированные и висячие вершины.
Простой граф. Полный граф. Мультиграф. Псевдограф. Двудольный граф. Полный двудольный граф.
Изоморфные графы. Помеченный граф. Формула Пойа.
Дополнительный граф (дополнение). Самодополнительный граф. Подграф.
Объединение (наложение) графов. Произведение графов. Слияние (отождествление) вершин. Стягиваемые графы. Расщепление вершин.
Маршрут. Цепь. Простая цепь. Гамильтонова цепь. Длина маршрута.
Циклический маршрут. Цикл. Простой цикл. Гамильтонов цикл. Обхват графа.
Связный граф. Путь. Сильно связный орграф. Теорема о связности графа. Теорема о разложении графа на связные (сильно связные) компоненты. Теорема о числе рёбер связного графа.
Граф со взвешенными дугами (сеть). Узлы сети. Вес дуги. Вес пути.
Независимость и покрытия. Связь между числом независимости и числом вершинного покрытия графа.
Числа вершинной и рёберной связности. Понятие n- связного графа.
Теорема Менгера. Теорема Холла.
Латинская матрица.
Матрица смежности вершин. Связь между матрицами смежности изоморфных графов. Ранг графа.
Матрица смежности дуг.
Матрица инциденций. Вектора инциденций. Связь между матрицами инциденций изоморфных графов.
Матрица Кирхгофа и её свойства.
Матрица связности. Матрицы достижимости и контрдостижимости, связь между ними и использование их для нахождения сильных компонент графа.
Расстояние между вершинами и его свойства. Эксцентриситет вершины. Диаметр графа. Радиус графа. Периферийная вершина. Диаметральная цепь. Теорема о диаметре связного графа. Центральная вершина. Центр графа.
Упорядочивание вершин связного орграфа без контуров. Алгоритм Фалкерсона. Упорядочивание дуг.
Матричный способ упорядочивания вершин. Полустепени захода и выхода.
Теорема о количестве дуг маршрутов и следствия из неё. Модифицированная матрица смежности.
Операции Шимбелла. Метод Шимбелла определения экстремальных путей на графах.
Уровни орграфа. Порядковая функция орграфа. Алгоритм нахождения уровней орграфа без контуров.
Функция Гранди. Алгоритм определения функции Гранди для орграфа без контуров.
Задачи для самостоятельного решения.
Показать, что для произвольного графа G=(S,U) справедливо равенство
Для графа, изображённого на рис. 26, составить матрицы смежности вершин, смежности дуг и инциденций.
Рис. 26
По матрице смежности вершин построить наглядное изображение графа:
.
По матрице смежности вершин построить наглядное изображение графа:
.
На рис. 27 приведены графы G1 и G2. Найти
и
.
Рис. 27
Найти матрицы сильных компонент и маршрутов длины три дуги, исходящих из вершины x1, для графа, изображённого на рис. 28.
Рис. 28
Найти матрицы сильных компонент и маршрутов длины три ребра, исходящих из вершины x1, для графа, изображённого на рис. 29.
Рис. 29
Найти эксцентриситеты вершин, радиус и диаметр графа, приведённого на рис. 30.
Рис. 30
Упорядочить вершины и дуги орграфа, изображённого на рис. 31, графическим и матричным способом (дуги - только графическим способом).
Рис. 31
Доказать, что три графа, изображённых на рис. 32, изоморфны.
Рис. 32
Доказать, что три графа, изображённых на рис. 33, неизоморфны.
Рис. 33
Построить граф, центр которого состоит ровно из одной вершины.
Построить граф, центр которого состоит ровно из трёх вершин и не совпадает с множеством всех вершин.
Построить граф, центр которого совпадает с множеством всех вершин.
Показать, что в любом графе без петель и кратных рёбер, содержащем не менее двух вершин, найдутся две вершины с одинаковыми степенями.
Разбить орграф без контуров, заданный матрицей смежности
,
на уровни. Найти функцию Гранди.