Лабораторная работа n3 Определение чисел внутренней и внешней устойчивости графа

Цель работы:

Изучение методов определения внутренне и внешне устойчивых множеств вершин графа, определение чисел устойчивости, цикломатического числа; построение матрицы фундаментальных циклов.

1 Теоретическая часть

1.1. Устойчивые множества вершин графа

Множество вершин графа называется внутренне устойчивым (независимым), если никакие две вершины из этого множества не смежны.

Внутренне устойчивое множество вершин называется максимальным, если оно не является собственным подмножеством некоторого другого внутренне устойчивого множества.

Наибольшее по мощности устойчивое множество называется наибольшим.

Наибольшее внутренне устойчивое множество является максимальным, обратное неверно.

Понятие внутренней устойчивости на содержательном уровне сводится к поиску решения задачи, например, о восьми ферзях: требуется так расставить на шахматной доске наибольшее число ферзей, чтобы они не били друг друга. Таких ферзей не может быть более восьми, т.к. никакие два из них не должны находиться на одной вертикали, горизонтали или диагонали.

Очевидно, что требуемой расстановке будет соответствовать максимальное внутренне устойчивое множество вершин графа, которым соответствуют клетки шахматной доски, клетки одной вертикали, горизонтали или диагонали будут соответствовать ребрам графа.

Число вершин в наибольшем внутренне устойчивом множестве графа G называется числом внутренней устойчивости и обозначается a0(G)

Рис.1

На рис.1 изображен граф G, у которого наибольшими внутренне устойчивыми являются множества вершин {1,2,3,7},{1,2,3,8},{2,3,5,7}, {4,7},{2,3,5,8}; следовательно, O(G)=4. Множество {4,7} является максимальным внутренне устойчивым, но не наибольшим.

Подмножество V’ вершин графа G называется внешне устойчивым, если каждая вершина, не принадлежащая этому множеству (V\V’), смежна с некоторой вершиной из V’.

Внешне устойчивое множество называется минимальным, если никакое его собственное подмножество не является внешне устойчивым.

Внешне устойчивое множество называется наименьшим, если его мощность наименьшая.

Понятие внешней устойчивости на содержательном уровне может быть проиллюстрировано задачей о пяти ферзях: требуется расставить на шахматной доске минимальное число ферзей так, чтобы каждая клетка доски была под боем.

Число вершин в минимальном внешне устойчивом множестве наименьшей мощности называется числом внешней устойчивости и обозначается b_o (G)

Отыскание в графе наименьшего внешне устойчивого множества является содержанием многих прикладных задач такого типа: если вершины графа представляют собой технологические модули гибкого автоматизированного процесса, за которым должно осуществляться непрерывное наблюдение, а две вершины графа соединены ребром, если соответствующие им модули можно наблюдать, находясь около одного из них, то требуется так расставить телекамеры, чтобы оператор мог наблюдать за всеми модулями, но при этом число телекамер было бы минимальным.

С понятием устойчивости связано понятие покрытия. Вершина и ребро графа покрывают друг друга, если они инцидентны. Покрытие графа G называется минимальным, если оно не содержит покрытия с меньшим числом вершин, и наименьшим, если число вершин в нем наименьшее среди всех покрытий графа G.

В примере на рис.1 множества Х1={4,5,6,8}, Х2={4,5,6,7}, ХЗ={1,2,3,5,6,8} являются покрытием, причем, Х1 и Х2 - наименьшие покрытия, а ХЗ - минимальное. Множество вершин графа, являющееся одновременно и внутренне и внешне устойчивым, называется ядром графа.