Ядро графа

Доминирующее множество вершин S графа G=(V, A) – подмножество вершин такое, что для любой вершины w Î V–S существует такая вершина vÎ S, что (v, w) Î A.

Независимое множество вершин графа G -подмножество вершин графа G, в котором никакие две вершины не смежны между собой.

Ядро графа – множество вершин, которое одновременно является доминирующим и независимым иножеством.

Например:

Задание к лабораторной работе

1. Используя алгоритм генерации варианта GV, построить ориентированный граф G: GV (9, {3, 4}). Ориентацию дуг установить произвольно.

2. Построить матрицу смежности и матрицу инцидентности заданного орграфа.

3. Построить основание и обратный граф. Определить является ли граф симметричным.

4. Построить ормаршрут, выделить в нем цепь, путь, полумаршрут, полуцепь, полупуть, замкнутый маршрут, цикл и контур.

5. Построить матрицу достижимости, контрдостижимости, взаимной достижимости.

6. Определить тип связности орграфа, выделить сильные компоненты.

7. Построить конденсацию. Определить базы и антибазы.

8. Выделить ядро орграфа.

9. Найти в графе контур и цепь Эйлера и Гамильтона.

Контрольные вопросы

1. Определение орграфа. Дуги орграфа.

2. Основание и обратный орграф.

3. Полустепень исхода и полустепень захода вершин орграфа.

4. Достижимость, контрдостижимость и взаимная достижимость.

5. Сильная, односторонняя и слабая связность.

6. Конденсация орграфа.

7. База, антибаза и ядро орграфа.

8. Гамильтонов контур и орграф.

9. Эйлеров цикл и орграф.