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


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

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

 1-matrichnoe-predstavlenie-grafov

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

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

2-matrichnoe-predstavlenie-grafov

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

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

 3-matrichnoe-predstavlenie-grafov

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

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

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

4-matrichnoe-predstavlenie-grafov

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

5-matrichnoe-predstavlenie-grafov

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

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

Литература:

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


Категории: Логистика  

Об этой статье

teoriia-grafov-matrichnoe-predstavlenie-grafov-avatar
2017-11-02 12:03:39
591
user
Логистика; Лекции; Теория графов;
В статье рассмотрено матричное представление графов