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

1. Матрица инцидентности [строками обозначаются вершины, а столбцами ребра (табл. 2.1)].

Таблица 2.1 – Матрица инцидентности.

Элемент матрицы b_ij = 1 в случае, если i-я вершина инцидентна j-у ребру, и b_ij = 0, если данная i-я вершина не инцидентна j-у ребру.

Пример матрицы инцидентности приведен ниже (табл. 2.2), граф данной матрицы показан на рисунке 2.13.

2. Матрица смежности [как строки, так и столбцы – это узлы логистической системы (табл. 2.3)].

Таблица 2.3 – Матрица смежности.

Элемент матрицы b_ij = 1, если между i-м и j-м узлами системы есть ребра, в противном случае b_ij = 0.

Пример матрицы смежности приведен в таблице 2.4, граф матрицы аналогичен графу предыдущего примера (рис. 2.13).

Таблица 2.4 – Пример матрицы смежности.

Матрица смежности в квадрате:

Степень матрицы указывает длину пути (2), значение в полученной матрице – на количество возможных путей (0, 1, 2 или 3).

Из i-го узла в j-й узел существует k путь, если  (один путь). Существует m k путей, если .

Литература:

1. Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
2. Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.