Студопедия — Расчет неплотности ε(G) графа G
Студопедия Главная Случайная страница Обратная связь

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

Расчет неплотности ε(G) графа G






Рассмотрим плотность графа G, т.е. наибольшее число вершин пустого подграфа графа G между всеми вершинами которого нет отношений смежности.

 

Построим обратный граф ┐ G для графа G. Для этого получим матрицу || H || и обратную ей матрицу || ┐ H || (рисунок 15).

 

       
   
H            
             
             
             
             
             
             

 

 
H            
             
             
             
             
             
             

 

 

 


Рисунок 15 - Матрицы смежности (слева-направо) графа G и графа ┐ G

 

Строим матрицу достижимости графа ┐ G и выполняем операцию перестановки строк и столбцов. Результаты показаны на рисунке 16.

 

 

Qp            
             
             
             
             
             
             

 

 
 
Qp            
             
             
             
             
             
             

 

 


 

Рисунок 16 - Матрицы достижимости ┐ Qp графа ┐ G

Примечание: матрица на рисунке справа имеет блочную структуру.

 

На рисунке 17 показан обратный граф ┐ G.

 
 

 

Рисунок 17 - Обратный граф ┐ G

 

Анализ матрицы ┐ Qp с блочной структурой на рисунке 16 показывает, что поскольку число блоков – три, то имеем три пустых подграфа графа G с тремя вершинами в каждом (рисунок 17):

|Х`1|=3, |Х`2|=3, |Х`3|=3.

 
 

Рисунок 18 - Три пустых подграфа графа G

Таким образом имеем:

.

На этом расчеты числовых характеристик графа G закончены.

 

 

Приложение 1. Построение матрицы достижимости.
Построим матрицу смежности и зададим единичную матрицу
Возводим в соответствующую степень

 

 
 
Анализ матриц показывает, что никаких изменений нет. Матрица достижимости:






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



Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Законы Генри, Дальтона, Сеченова. Применение этих законов при лечении кессонной болезни, лечении в барокамере и исследовании электролитного состава крови Закон Генри: Количество газа, растворенного при данной температуре в определенном объеме жидкости, при равновесии прямо пропорциональны давлению газа...

Ганглиоблокаторы. Классификация. Механизм действия. Фармакодинамика. Применение.Побочные эфффекты Никотинчувствительные холинорецепторы (н-холинорецепторы) в основном локализованы на постсинаптических мембранах в синапсах скелетной мускулатуры...

Шов первичный, первично отсроченный, вторичный (показания) В зависимости от времени и условий наложения выделяют швы: 1) первичные...

САНИТАРНО-МИКРОБИОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ ВОДЫ, ВОЗДУХА И ПОЧВЫ Цель занятия.Ознакомить студентов с основными методами и показателями...

Меры безопасности при обращении с оружием и боеприпасами 64. Получение (сдача) оружия и боеприпасов для проведения стрельб осуществляется в установленном порядке[1]. 65. Безопасность при проведении стрельб обеспечивается...

Весы настольные циферблатные Весы настольные циферблатные РН-10Ц13 (рис.3.1) выпускаются с наибольшими пределами взвешивания 2...

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