Понеділок, 18.02.2019, 08:47
Гость

Мішатронік

Автор - Кренцін Михайло

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Java чи С++
Всього відповідей: 1
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0




Матриця суміжності 

Розглянемо наступний граф:

При представленні графа матрицею суміжності інформація про граф зберігається в квадратній матриці (двомірному списку), де елемент a[i,j] дорівнює 1, якщо вершини i та j з’єднані ребром та дорівнює 0, якщо вершини i та j не з’єднані.

Для даного прикладу матриця суміжності матиме вигляд: 

 

 

1

2

3

4

5

1

0

1

1

1

0

2

1

0

0

1

1

3

1

0

0

1

0

4

1

1

1

0

1

5

0

1

0

1

0

 
 
Якщо граф неорієнтований, то матриця суміжності завжди симетрична відносно головної діагоналі. 
 
Розглянемо орієнтований граф: 

Матриця суміжності матиме вигляд

 

1

2

3

4

5

1

0

1

0

0

0

2

0

0

0

1

1

3

1

0

0

1

0

4

1

0

1

0

0

5

0

0

0

0

0

 

 

Для зваженого графа кожному ребру відповідає деяке число (наприклад,  довжина дороги або вартість проїзду) – вага ребра.
 
В цьому випадку замість одиниць в матриці суміжності зберігають ваги ребер, а при відсутності ребра зберігають спеціальне значення, наприклад, в багатьох задачах зручно при відсутності ребра зберігати дуже велике число – «нескінченість». 
 
Джерела:disted.edu.vn.ua

 

Форма входа
Пошук
Календар
«  Лютий 2019  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728
Друзі сайту
Погода у Вінниці


Єдина Країна! Единая Страна!