03. Матричный способ задания графа

Рассмотрим граф , Имеющий P вершин и Q ребер.

Определение. Матрицей смежности вершин графа называется квадратная матрица порядка P, элементы которой определяются по правилу:

Индексы независимо друг от друга.

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

Определение. Матрицей инцидентности графа называется матрица размерности P на Q, элементы которой определяются по правилу:

Например, матрицей инцидентности графа на рис. 8 (см. пункт 4.1) является матрица размерности четыре на пять .

Теорема 4. Ранги матриц смежности изоморфных графов равны.

3адачи и упражнения

7. Составьте матрицы смежности графов задачи 1.

8. Составьте матрицы инцидентности графов задачи 1.

9. Найдите ранги матриц смежности и матриц инцидентности графов задач 4.6.

10. Постройте диаграммы графов, заданных следующими матрицами смежности:

1) ; 2) .

11. Постройте диаграммы графов, заданных следующими матрицами инцидентности:

1) ; 2) .

< Предыдущая		Следующая >