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

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

Устойчивости графа

Определение чисел внутренней и внешней

Лабораторная работа N3

Варианты заданий к выполнению работы

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

Порядок выполнения работы

Задания к выполнению работы

Задание 1. Выполнить разложение орграфа на компоненты сильной связности методом Мальгранжа-Томеску.

Задание 2. Произвести раскраску графа, используя функцию смежности Гранди.

Граф задается матрицей смежности. Вариант задания определяется следующим образом: по номеру ijиз таблиц 1-9 берется таблица с номером i, по j из таблицы 10 выбирается строка и осуществляется замена меток {a, b, c, d, e, f, g, h} столбцов матрицы смежности с номером i на цифры из множества {1, 2, 3, 4, 5, 6, 7, 8} в соответствии с табл. 10, затем производится перестановка столбцов матрицы смежности в порядке возрастания номеров. В результате получается матрица смежности требуемого графа.

При раскраске графа его необходимо задать графически.

1) Изучить теоретическую часть.

2) Выполнить задания по п.6 в соответствии с заданным вариантом.

3) Составить отчет.

4) Ответить на контрольные вопросы.

1) Что называется графом?

2) Как представляются графы?

3) Что такое матрица смежности?

4) Какие графы подразделяются по связности?

5) Что такое транзитивное замыкание вершин?

6) В чем заключается алгоритм Мальгранжа - Томеску?

7) В чем заключается алгоритм заполнения столбца?

8) Как разложить граф на компоненты сильной связности?

9) В чем состоит задача раскраски графа?

10) В чем заключается алгоритм раскраски графа с помощью функции Гранди?

Таблица 1
	A	b	c	d	e	f	g	h

Таблица 2
	a	b	c	d	e	f	g	h

Таблица 3
	a	b	c	d	e	f	g	h

Таблица 4
	a	b	c	d	e	f	g	h

Таблица 5
	a	b	c	d	e	f	g	h

Таблица 6
	a	b	c	d	e	f	g	h

Таблица 7
	a	b	c	d	e	f	g	h

Таблица 8
	a	b	c	d	e	f	g	h

Таблица 8
	a	b	c	d	e	f	g	h
Таблица 8
	a	b	c	d	e	f	g	h

Таблица 9
	a	b	c	d	e	f	g	h

Таблица 8
	a	b	c	d	e	f	g	h

Таблица 10
N варианта	a	b	c	d	e	f	g	h

Цель работы:

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

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

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

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

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

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

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

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

Рис.1

На рис.1 изображен граф G, у которого наибольшими внутренне устойчивыми являются множества вершин {1,2,3,7},{1,2,3,8},{2,3,5,7}, {4,7},{2,3,5,8}; следовательно, aO(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 - наименьшие покрытия, а ХЗ - минимальное. Множество вершин графа, являющееся одновременно и внутренне и внешне устойчивым, называется ядром графа.

Дата добавления: 2017-01-13