Студопедия — Приложение 3. Расчет плотности графа.
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






 

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

В качестве примера рассмотрим граф, изображенный на рис. П1.

 

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

 

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

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

 

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

 

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

 

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

 

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

 

 
 

 


а) б)

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

 

Построим ещё одно дерево для вершины v6, чтобы проверить, все ли полныеподграфы мы нашли. Все действия аналогичны. Рис. П2.

 

 

 

Рис. П2. Получили ещё два полных подграфа {2,5,6} и {4,6,7}, который уже был получен..

 

Таким образом, получили 4 полных подграфа с наибольшей степенью 3. Следовательно плотность графа равна трем.

 

Литература

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

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

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

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

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

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







Дата добавления: 2015-08-29; просмотров: 806. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Искусство подбора персонала. Как оценить человека за час Искусство подбора персонала. Как оценить человека за час...

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

Тема 5. Анализ количественного и качественного состава персонала Персонал является одним из важнейших факторов в организации. Его состояние и эффективное использование прямо влияет на конечные результаты хозяйственной деятельности организации.

Вопрос 1. Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации Коллективные средства защиты: вентиляция, освещение, защита от шума и вибрации К коллективным средствам защиты относятся: вентиляция, отопление, освещение, защита от шума и вибрации...

Задержки и неисправности пистолета Макарова 1.Что может произойти при стрельбе из пистолета, если загрязнятся пазы на рамке...

Вопрос. Отличие деятельности человека от поведения животных главные отличия деятельности человека от активности животных сводятся к следующему: 1...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия