Приложение 2. Расчет плотности графа.

Алгоритм нахождения плотности графа:

Рассмотрим граф, изображенный на рис. П1.

1. Сопоставляем корню дерева заданный граф.

2. Фиксируем в графе вершину с максимальной степенью, сопоставив её концу исходящей из корня дуги.

Степень вершины v6 максимальна.

3. Строим множество исходящих из корня дуг. Их число – мощность носителя неокрестности вершины с максимальной степенью.

4. Считаем концы построенного яруса корнями новых деревьев. Устанавливаем, помечена ли вершина V символом пустое множество. Если нет, строим следующий ярус. Если да – конец алгоритма.

5. Пути между концами дуг, исходящих из корня синтезированного дерева, и висячими вершинами определяют полные подграфы заданного графа.

Рассмотрим применение этого алгоритма для приведенного графа.

3

1

111

1

3

7

11

6

5

10

9

7

2

6

8

3

7

10

а) б)

Рис. П1. Исходный граф (а) и построенное дерево (б). Получившиеся подграфы {11,9,8}, {11,9,10}, {1,2,3}

Задание 2. Теоретические вопросы

Литература

1. Колесников А.В. Дискретная математика. Задания и методические указания к курсовой работе для студентов специальности 080801.65 «Прикладная информатика в экономике» (очно-заочная форма обучения). Калининград, 2006, 45 стр.

2. Кузнецов О.М., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988, 480 с.

3. Пономарев. В.Ф. Основы дискретной математики: Учебное пособие. – Калининград: КГТУ, 1997, 165 с.

4. Пономарев В.Ф. Дискретная математика для информатиков-экономистов. Учебное пособие. – Калининград: КГТУ и КИМБ, 2002, 239с.

5. Непейвода Н. Н. Прикладная логика: Учеб. Пособие.- 2-е изд., испр. и доп.- Новосибирск, изд-во Новосиб. Ун-та, 2000.-521с.

6. Горбатов В.А. Фундаментальные основы дискретной математики. М, Наука, ФМ, 200, 540 стр.