Теория графов. Матричное представление графов
- Матрица инцидентности [строками обозначаются вершины, а столбцами ребра (табл. 2.1)].
Таблица 2.1 – Матрица инцидентности.
Элемент матрицы bij = 1 в случае, если i-я вершина инцидентна j-у ребру, и bij = 0, если данная i-я вершина не инцидентна j-у ребру.
Пример матрицы инцидентности приведен ниже (табл. 2.2), граф данной матрицы показан на рисунке 2.13.
2. Матрица смежности [как строки, так и столбцы – это узлы логистической системы (табл. 2.3)].
Таблица 2.3 – Матрица смежности.
Элемент матрицы bij = 1, если между i-м и j-м узлами системы есть ребра, в противном случае bij = 0.
Пример матрицы смежности приведен в таблице 2.4, граф матрицы аналогичен графу предыдущего примера (рис. 2.13).
Таблица 2.4 – Пример матрицы смежности.
Матрица смежности в квадрате:
Степень матрицы указывает длину пути (2), значение в полученной матрице – на количество возможных путей (0, 1, 2 или 3).
Из i-го узла в j-й узел существует k путь, если (один путь). Существует m k путей, если
.
Литература:
- Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
- Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.
Популярные рубрики
Популярные теги