Rambler's Top100


Дискретная математика. Часть 3 (Курс лекций). Авторы: Емцева Е.Д., Солодухин К.С., редактор: в авторской редакции

§9. Матрицы, ассоциированные с графами.
Определение 1

Матрицей смежности помеченного графа порядка n называется квадратная бинарная матрица A порядка n, определяемая следующим образом:

, где    

 

Замечание

 

Если граф неориентированный, то матрица его смежности симметрическая.

 

Пример

 

                                                      1                             2

                       5                            4                  3

 

Замечание

 

В случае если в графе есть кратные ребра и петли, то элемент  матрицы A будет равен числу дуг, соединяющих вершины i и j. При  этом неориентированная петля считается за два ребра.

 

 

Пример

 

Неориентированный граф.

 

2

 

1

 

2

 

5

 

3

 

4

 

1

 

5

 

4

 

3

 
                                                                

 

 

 

 


Ориентированный граф.

 

 

4

 

5

 

1

 

2

 

3

 
                                                            

 

 

 

Замечание

 

Задание графа с помощью его матрицы смежности однозначно, если граф помеченный. Более того, любая квадратная бинарная матрица является матрицей смежности некоторого ориентированного графа. А произвольная бинарная симметрическая матрица – неориентированного графа.

Определение 2

Ранг матрицы смежности графа G называется рангом графа G. Обозначают .

Poker razz odds calculator