Основные теоремы теории графов

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

Определение 2.01. Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа.

Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек (см. рис. 2.1).

(РИСУНОК 2.1)

В дальнейшем вершины графа мы будем обозначать латинскими буквами A, B, C, D. Иногда граф в целом будем обозначать одной заглавной буквой.

Определение 2.02. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными.

Определение 2.03. Граф, состоящий только из изолированных вершин, называется нуль - графом.

Обозначение: O' – граф с вершинами, не имеющий ребер (рис. 2.2).

(РИСУНОК 2.2)

Определение 2.04. Граф, в котором каждая пара вершин соединена ребром, называется полным.

Обозначение: U' – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n –угольник, в котором проведены все диагонали (рис. 2.3).

(РИСУНОК 2.3)

Определение 2.05. Степеньювершины называется число ребер, которым принадлежит вершина.

Определение 2.06. Граф, степени всех k вершин которого одинаковы, называется однороднымграфомстепениk.

На рисунке 2.4 и 2.5 изображены однородные графы второй и третьей степени.

(РИСУНОК 2.4 и 2.5)

Определение 2.07. Дополнениемданногографа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.

На рисунке 2.6 изображен исходный граф G, а на рисунке 2.7 – дополнение данного графа – граф G'.

(РИСУНОК 2.6 и 2.7)

Определение 2.08. Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским. (рис. 2.8)

(РИСУНОК 2.8)

Определение 2.09. Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.

Понятия плоского графа и грани графа применяется при решении задач на "правильное" раскрашивание различных карт.

Определение 2.10. Путем от A до X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

Определение 2.11. Циклом называется путь, в котором совпадают начальная и конечная точка.

Определение 2.12. Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.

Определение 2.13. Длиной пути,проложенного на цикле,называется число ребер этого пути.

Определение 2.14. Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

Определение 2.15. Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.

(РИСУНОК 2.9 и 2.10)

На рисунке 2.9 изображен связный граф; на рисунке 2.10 – несвязный (т. к. существует минимум одна пара несвязных вершин – A и D).

Определение 2.16. Деревом называется связный граф, не содержащий циклов.

Трехмерной моделью графа-дерева служит, например, настоящее дерево с его замысловато разветвленной кроной; река и ее притоки также образуют дерево, но уже плоское – на поверхности земли

Определение 2.17. Несвязный граф, состоящий исключительно из деревьев, называется лесом.

Определение 2.13. Дерево, все n вершин которого имеют номера от 1 до n, называют деревом с перенумерованными вершинами.

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