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

Матричные представления графа

Читайте также:
  1. II. Оснащение транспортных средств тахографами
  2. А) ПОНЯТИЕ ЖИЗНИ У ГУССЕРЛЯ И ГРАФА ЙОРКА
  3. Архетипы, соотносимые с представлениями о времени и пространстве
  4. Биологическое значение боли. Современные представления о механизмах болевой чувствительности.
  5. Во время представления комедии куклы узнают Буратино
  6. ВРАЧИ НЕ ИМЕЮТ ПРЕДСТАВЛЕНИЯ НЕ ТОЛЬКО О ЗНАЧИМОСТИ ПИТАНИЯ
  7. Врачи не имеют представления не только о значимости питания

 

Одной из форм математического представления графа является его представление в виде матриц смежности инциденций.

Вершины х и y являются смежными, если они различны и если существует дуга, идущая из х в y.

Дугу u называют инцидентной вершине х, если она заходит в эту вершину или исходит из нее.

Обозначим через х1, х2, …, хn вершины графа, а через u1, u2, …, um его дуги.

Матрицей смежности R=[ri,j] графа G=(Х, Г) называется квадратная матрица порядка n (n – число вершин графа), элементы которой ri,j (i=1, 2, …n; j=1,2, …n) определяются следующим образом:

(2.6)

Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат. Элемент матрицы R2 определяется по формуле:

(2.7)

Слагаемое тогда и только тогда, когда и , в противном случае слагаемое . Так как из равенства следует существование пути длины два (пути, проходящего через две дуги) из вершины хi в вершину xj, проходящего через вершину xk, то равно числу путей длины два, идущих из xi в xj через xk.

Если является элементом матрицы , то ¹0 равно числу путей длины p, идущих из xi в xj.

Пример. На рис. 2.4 задан граф G. построить матрицу смежности и выяснить, сколько путей длины три существует в графе G.

Рис. 2.4

 

Решение.

 

 

Элемент , следовательно в данном графе существует единственный путь длиной три – это путь из вершины х1 в вершину х4: х1 u1 x2 u2 x3 u3 x4.

Все элементы матрицы равны нулю. Следовательно, в графе отсутствуют пути длиной четыре.

Матрицей инциденций называется прямоугольная матрица размерности n´m (n-число вершин, m – число дуг), элементы которой определяются следующим образом:

(2.8)

Если граф G не содержит петель, то каждый столбец матрицы S содержит единственный элемент, равный 1 (дуга имеет начало) и единственный элемент, равный –1 (дуга имеет конец), а остальные элементы равны нулю.

Пример. Построить матрицу смежности и матрицу инциденций для графа, приведенного на рис. 2.5.

 
 

 

 


Матрица инциденций будет иметь вид:

xi /uj u1 u2 u3 u4 u5 u6 u7 u8 u9
x1 -1                
x2     -1   -1        
x3           -1 -1    
x4   -1   -1          
x5               -1  

 

Или в более компактной форме матрица смежности R и инциденций S будут иметь вид:

; .

 


Дата добавления: 2015-10-13; просмотров: 82 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Определение графа| Достижимость

mybiblioteka.su - 2015-2024 год. (0.006 сек.)