Студопедия Главная Случайная страница Обратная связь

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

Расчет степеней вершин δi графа G.




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

Расчет выполняется методом визуального анализа графа G с целью определения количества ребер (дуг) инцидентных вершине xi. Результаты расчета сведены в таблицу .2.

 

Таблица 2 - Результаты расчета

степеней вершин графа G

xi δi

2. Расчет числа компонент связности æ(G)

 

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

 
 

 

 


где ||1|| - единичная матрица (рисунок 3),

||H(xi)|| - матрица смежности графа G,

||Hp(xi)|| - матрица смежности графа G, возведенная в p-ую степень.

 

 
 

 

 


 

 

Рисунок 3 - Единичная матрица для графа G

 

Для возведения в степень матрицы смежности используют правило умножения булевых матриц.

На рисунке 4 правило умножения булевых матриц прокомментировано графически.

 

 

 
 

 


Первая строка на первый столбец

 

 

Первая строка на второй столбец

 

Обозначения: - дизъюнкция (см. таблицу истинности по учебному пособию [4] );

- конъюнкция (см. таблицу истинности по учебному пособию [4])

 

Рисунок 4 - Пример умножения булевых матриц 4х4







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

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