Please enable JavaScript.
Coggle requires JavaScript to display documents.
Теория графов, Кёнигово представление гиперграфа image, Планарность,…
Теория графов
6 неделя
Хроматическое число графа x(G) - минимальное количество цветов для вершинной раскраски графов
Число внешней устойчивости графа - минимальное количество вершин, образами которых являются все остальные вершины этого графа
-
Минимальная опора - опора в графе, которую нельзя уменьшить по мощности без нарушения свойства внешней устойчивости
-
Число парасочетания (число независимости ребер) - максимальное количество несмежных между собой ребер графа
Парасочетание - любое подмножество ребер графа, не смежных между собой
Максимальное парасочетание - парасочетание, которое нельзя расширить за счет других ребер графа без нарушения свойства независимости ребер в данном парасочетании
-
Число реберного покрытия графа - минимальное количество ребер для покрытия всех вершин графа. Графы с изолированными вершинами не имеют реберного покрытия
Реберное покрытие графа - любое множество ребер графа, которое покрывает все вершины этого графа
Минимальное реберное покрытие графа - такое реберное покрытие графа, которое нельзя уменьшить по количеству ребер без нарушения свойства вершинного покрытия ребрами данного графа
Наименьшее реберное покрытие графа - минимальное реберное покрытие графа с наименьшим количеством ребер
Совершенное паросочетание – это наибольшее паросочетание графа с минимальным
суммарным весом его ребер.
7 неделя
Двудольные графы(графы Кёнига К) - графы, у которых множество вершин состоит из двух долей
- Граф Кёнига можно раскрасить в два цвета, т.к. вершины в долях не смежны между
собой. Поэтому граф Кёнига называют еще и бихроматическим графом.
- Число внутренней устойчивости графа Кёнига max(|X1|, |X2|)
Теорема Кёнига (критерий двудольности графа)
Для двудольности графа необходимо и достаточно, чтобы этот граф не содержал простых циклов нечётной длины.
Задача линейного назначения,
понятие совершенного паросочетания графа
Гиперграф
Количество вершин n и количество гиперрёбер m определяют порядок гиперграфа
(аналог размерности бинарного графа)
-
Количество вершин, инцидентных гиперребру r из R, определяет степень этого
гиперребра – ρ(r), причем ρ(r) ≥ 1.
Смежность в гиперграфах. Два гиперграфа r᾽ и r᾽᾽ называются смежными, если
выполняется условие r᾽ ∩ r᾽᾽ ≠ Ø.
Однородность гиперграфов. Если в гиперграфе H(X, R) выполняется условие для любого r принадлежащему R:
ρ(r) = h, то такой гиперграф называется h-однородным или h-униформным.
Бинарный граф является частным случаем гиперграфа, причем однородным с h = 2.
-
-
-
-
-
-
Кёнигово представление гиперграфа
-
-
-
Цикломатическое число графа указывает то наименьшее число рёбер, которое нужно удалить из данного графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа), т. е. добиться отсутствия у графа циклов. Цикломатическое число всегда неотрицательно
Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).
Число внутренней устойчивости (= число независимости, = число неплотности) графа – это максимальное количество вершин в графе, не смежных между собой.
Число внешней устойчивости графа - минимальное количество вершин, образами которых являются все остальные вершины этого графа
Число парасочетания (число независимости ребер) - максимальное количество несмежных между собой ребер графа
Число реберного покрытия графа - минимальное количество ребер для покрытия всех вершин графа. Графы с изолированными вершинами не имеют реберного покрытия
Кликовое число (=число зависимости, = число плотности) графа – это максимальное
количество вершин в графе, смежных между собой.
-
-
-
-
Поиск минимального остовного дерева в связном взвешенном графе с помощью алгоритма Прима (4 неделя курса)
Поиск совершенного паросочетания во взвешенном полном двудольном графе с помощью венгерского алгоритма (7 неделя курса)
Установление изоморфизма двух псевдографов с помощью алгоритма на основе локальных характеристик отношения вершин (8 неделя)
-