Теория графов: основные определения, виды, свойства

Содержание

Введение в теорию графов
Основные определения теории графов
Виды графов

Введение в теорию графов

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

Графы позволяют визуализировать и анализировать сложные взаимосвязи между объектами, что делает их незаменимыми в решении задач оптимизации, поиска кратчайших путей и анализа сетей. Мы начнем с изучения базовых понятий, таких как вершины, ребра, степень вершины и смежность, а затем перейдем к более сложным темам, включая типы графов (простые, полные, ориентированные и неориентированные) и их ключевые свойства.

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

Основные определения теории графов

Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936 г, хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.).

Л. Эйлер в 1736 году опубликовал решение задачи о Кенигсбергских мостах.

Граф $G = (V,E)$ состоит из двух множеств: конечного множества элементов $V$ , называемых вершинами, и конечного множества элементов $E$ , называемых ребрами.

На рисунке 1.1.1 задан граф $G = (V,E)$ , где множество вершин $V = \{ V_{1},\ V_{2},\ V_{3},\ V_{4},V_{5},V_{6},V_{7},V_{8},V_{9},V_{10}\}$ ; множество ребер $E = \left\{ e_{1},\ e_{2},\ e_{3},e_{4},\ e_{5},e_{6},\ e_{7},e_{8},\ e_{9},\ e_{10},e_{11},\ e_{12},e_{13},\ e_{14} \right\}$ .

Рисунок 1.1.1 – Граф G=(V,E) - Теория графов ischanow.com — Рисунок 1.1.1 – Граф G=(V,E)

Вершины $v_{i}$ и $v_{j}$ , определяющие ребро $e_{k}$ , называются концевыми вершинами ребра $e_{k}$ .

Ребра с одинаковыми концевыми вершинами называются параллельными ( $e_{12}$ , $e_{13}$ ).

Петля — замкнутое ребро ( $e_{10}$ ).

Ребро, принадлежащее вершине, называется инцидентным (ребро $e_{2}$ инцидентно вершинам $V_{2}$ и $V_{3}$ ).

Изолированная вершина не инцидентна ни одному ребру ( $V_{10}$ ).

Две вершины смежны, если они являются концевыми вершинами некоторого ребра ( $V_{3}$ , $V_{9}$ ).

Если два ребра имеют общую концевую вершину, они называются смежными ( $e_{1}$ , $e_{2}$ ).

Подграф — любая часть графа, сама являющаяся графом.

Рисунок 1.1.2 – Подграф K графа G - Теория графов ischanow.com — Рисунок 1.1.2 – Подграф K графа G

Виды графов

Граф $G = (V, E)$ называется простым, если он не содержит петель и параллельных ребер.

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

Граф $G = (V,E)$ называется полным, если он простой и каждая пара вершин смежна.

Рисунок 1.2.2 – Полный граф - Теория графов ischanow.com — Рисунок 1.2.2 – Полный граф

Дополнением графа $G'$ называется граф $\overline{G}'$ , имеющий те же вершины, что и граф $G'$ , и содержащий только те ребра, которые нужно добавить к графу $G'$ , чтобы он стал полным.