Способы задания графов: геометрическая интерпретация, матрицы смежности, инцидентности и список ребер

Введение

Теория графов предоставляет мощные инструменты для моделирования и анализа сложных систем, но для эффективной работы с графами необходимо уметь их правильно задавать. В этой статье мы рассмотрим основные способы задания графов, включая матрицы смежности и матрицы инцидентности, а также другие методы, такие как списки ребер и геометрическое представление.

Матрицы смежности и инцидентности являются одними из наиболее популярных способов задания графов, так как они позволяют компактно и удобно хранить информацию о вершинах и ребрах. Мы подробно разберем, как строить эти матрицы, какие данные они содержат и как их использовать для решения практических задач. Кроме того, мы рассмотрим примеры задания графов с помощью списков ребер и геометрического представления, которые могут быть полезны в различных ситуациях.

Если вы уже знакомы с основами теории графов и хотите узнать, как эффективно задавать и работать с графами, эта статья станет для вас незаменимым руководством.

Содержание

Способы задания графов
Явное задание графа как алгебраической системы (список ребер)
Геометрический
Матрица смежности
Матрица инцидентности

Способы задания графов

Явное задание графа как алгебраической системы (список ребер)

Чтобы задать граф, достаточно для каждого ребра указать двухэлементное множество вершин — его мы и будем отождествлять с ребром.

$G = \left\{ \left\{ V_{1},\ V_{2} \right\},\ \left\{ V_{1},\ V_{3} \right\},\ \left\{ V_{3},\ V_{5} \right\},\ \left\{ V_{2},\ V_{4} \right\},\ \left\{ V_{4},\ V_{5} \right\} \right\}.$

Геометрический

Рисунок 1.3.1 – Неориентированный граф - Теория графов ischanow.com — Рисунок 1.3.1 – Неориентированный граф

Матрица смежности

Элементы $A_{ij}$ матрицы смежности $A$ для неориентированного графа равны количеству ребер между рассматриваемыми вершинами; для ориентированного графа — числу ребер с началом в $i$ -ой вершине и концом в $j$ -ой.

Матрица инцидентности

Матрица инцидентности $B$ — это таблица, строки которой соответствуют вершинам графа, а столбцы — ребрам.

Элементы матрицы определяются следующим образом:

1) для неориентированного графа

2) для ориентированного графа

Задача 1.3.1. Для неориентированного графа $G$ , представленного на рисунке 1.3.2, записать матрицы смежности, инцидентности и список ребер.

Рисунок 1.3.2 – Неориентированный граф - Теория графов ischanow.com — Рисунок 1.3.2 – Неориентированный граф

Решение.

Матрица смежности

Матрица инцидентности

Список ребер

Задача 1.3.2. Для ориентированного графа $G$ , представленного на рисунке 1.3.3, записать матрицы смежности, инцидентности и список ребер.

Рисунок 1.3.3 – Ориентированный граф - Теория графов ischanow.com — Рисунок 1.3.3 – Ориентированный граф

Матрица смежности

Матрица инцидентности

Список ребер

Задача 1.3.3. Для неориентированного графа $G$ , представленного на рисунке 1.3.4, записать матрицы смежности, инцидентности и список ребер.

Рисунок 1.3.4 – Неориентированный граф- Теория графов ischanow.com — Рисунок 1.3.4 – Неориентированный граф

Задача 1.3.4. Для ориентированного графа $G$ , представленного на рисунке 1.3.5, записать матрицы смежности, инцидентности и список ребер.

Рисунок 1.3.5 – Ориентированный граф - Теория графов ischanow.com — Рисунок 1.3.5 – Ориентированный граф

Задача 1.3.5. Постройте граф отношения $x + y \leq 9$ на множестве $K = \left\{ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7 \right\}$ . Постройте матрицы инцидентности, смежности и список ребер.

Решение. Построим граф с множеством вершин $V = \left\{ V_{i},\ \ i = 1,\ ...,\ 7 \right\}$ , две вершины $V_{i}$ и $V_{j}$ соединяются ребром тогда и только тогда, когда выполняется условие $V_{i} + V_{j} \leq 9$ .

Рисунок 1.3.6 – Неориентированный граф - Теория графов ischanow.com — Рисунок 1.3.6 – Неориентированный граф

Матрица смежности

Матрица инцидентности

Список ребер

Задача 1.3.6. Постройте граф отношения $x - y > 3$ на множестве $F = \left\{ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9 \right\}$ . Постройте матрицы инцидентности, смежности и список ребер.

Решение.

Рисунок 1.3.7 – Ориентированный граф - Теория графов ischanow.com — Рисунок 1.3.7 – Ориентированный граф

Матрица смежности

Матрица инцидентности

Список ребер

Задача 1.3.7. Постройте граф отношения $x + y = 9$ на множестве $K = \left\{ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7 \right\}$ . Постройте матрицы инцидентности, смежности и список ребер.

Решение.

Рисунок 1.3.8 – Неориентированный граф - Теория графов ischanow.com — Рисунок 1.3.8 – Неориентированный граф

Матрица смежности

Матрица инцидентности

Список ребер

Задача 1.3.8. Постройте граф отношения $x + y < 2$ на множестве $G = \left\{ 1,\ 2,\ 3 \right\}$ . Постройте матрицы инцидентности, смежности и список ребер.

Решение.

Рисунок 1.3.9 – Неориентированный граф - Теория графов ischanow.com — Рисунок 1.3.9 – Неориентированный граф

Матрица смежности

Матрицу инцидентности и список ребер мы построить не сможем, так как вершины не соединены ребрами.

Задача 1.3.9. Постройте граф отношения $x + y < 7$ на множестве $K = \left\{ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7 \right\}$ . Постройте матрицы инцидентности, смежности и список ребер.

Задача 1.3.10. Постройте граф отношения $x + y > 3$ на множестве $K = \left\{ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7 \right\}$ . Постройте матрицы инцидентности, смежности и список ребер.

Задача 1.3.11. Постройте граф отношения $x - y \leq 3$ на множестве $K = \left\{ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7 \right\}$ . Постройте матрицы инцидентности, смежности и список ребер.