Числа, характеризующие граф.

Цикломатическим числом графа называется число u=N-n+p, где N- число ребер графа, n – число его вершин, P – число компонент связности. Для связного графа u=N-n+1.

Теорема. Цикломатическое число графа равно наибольшему количеству независимых циклов.

Понятие независимых циклу состоит в следующем. Поставим в соответствие циклу μ графа G некоторый вектор. Для этого придадим каждому ребру графа произвольную ориентацию. Если цикл μ проходит через ребро u_k в направлении его ориентации r_k раз и в противоположном направлении S_k раз, то полагаем c^k=r_k-S_k. Вектор с¹, c², …, c^K, …, c^N) m-мерного пространства называют вектором-циклом, соответствующим циклу μ. Циклы μ ₁, μ ₂, … называют независимыми, если соответствующие им векторы , , … линейно независимы.

Следствием названной теоремы являются следующие утверждения:

1. Связаный граф G не имеет циклов тогда и только тогда, когда u=0. Такой граф есть дерево (различные определения графа-дерева будут рассмотрены в специальном разделе ниже).

2. Связный граф G имеет единственный цикл тогда и только тогда, когда u=1.

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

Пример.

Цикломатическое число графа, изображенного на рис.3.1.10 равно 3.

Рис. 10.

Число внутренней устойчивости графа. Пусть задан некоторый граф G(x, гx). Рассмотрим такое подмножество его вершин S Х, в котором две любые точки являются несмежными. Такое подмножество S называется внутренне устойчивым. Другими словами S Х является внутренне устойчивым, если гSÇ S=0.

Обозначим |S| - мощность множества S. Пусть F – множество всех внутренне устойчивых множеств. Числом внутренней устойчивости графа G называется

a(G)= |S|.

Отыскание a(G) нужно начинать с максимального числа вершин и, постепенно увеличивая его, проверять, образуют ли выбранные вершины внутренне устойчивое множество.

Рис. 11.

Для графов, изображенных на рис. 3.1.11, имеем следующие a(G1)=1, любая пара вершин G1 является смежной. Граф G2 имеет два внутренне устойчивых множества S1={x₁, x₃}, S2={x₄, x₂}, |S1|=|S2|=2. Следовательно, a(G2)=2. Граф G3 содержит внутренне устойчивые множества S1={x₁, x₅}, S2={x₁, x₃}, S3={x₁, x₄}, S4={x₂, x₅}, S5={x₂, x₄}.

Но если к любому из этих множеств добавить какую-либо вершину, не содержащуюся в нем, подмножество перестанет быть внутренне устойчивым a(G3)=2.

Число внешней устойчивости графа. Пусть задан некоторый граф G(x, гx). Подмножество его вершин TÍ Х есть внешне устойчивое множество, если для каждой точки xÎ (X/T) выполнено условие

гxÇ T¹ 0.

Обозначим |T| - мощность множества T. Пусть Ф – множество всех внутренне устойчивых множеств. Числом внешней устойчивости графа G называется

b(G)= |T|.

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

Пример.

Определим число внешней устойчивости для графов, изображенных на рис.3.1.11. Любая пара вершин графа G1 образует внешне устойчивое множество, т.е. b(G1)=2. Граф G2 содержит два внешне устойчивых множества T1={x₁, x₃}, T2={x₂, x₄} с минимальным числом элементов, т.е. b(G1)=2. Для графа G2 внешне устойчивое множество минимальной мощности есть T={x₂, x₄}, т.е. b(G3)=2.

К определению числа внешней устойчивости графа сводится задача о часовых. На посту расставлены часовые, охраняющие n объектов, причем один и тот же часовой может наблюдать за несколькими объектами. Нужно выяснить, каково минимальное число часовых, необходимых для наблюдения за всеми объектами. Граф, изображенный на рис.3.1.12, соответствует следующей задаче: 9 вершин графа – охраняемые объекты (n=9), ребра характеризуют возможность просматривания объектов часовыми. Так, например, часовой у объекта X₁ может одновременно наблюдать за объектами X₂, X₃, X₄, X₆, X₉, часовой у объекта X₂ – за объектами X₁, X₃, X₇, X₈ и т.д. Для данного графа число внешней устойчивости X₄, X₈. Достаточно двух часовых, расположенных в точках X₄ и X₈, для охраны всех объектов.

Рис. 12.

Ядро графа. Если множество вершин графа G(x, гx) содержит подмножество LÍ Х как внутренне, так и внешне устойчиво, то такое подмножество L называется ядром графа.

Обозначим |L| мощность множества L. Эта величина удовлетворяет неравенству a(G)³ |L|³ b(G).

Пример.

Граф G1 (рис.3.1.11) не имеет ядра; граф G2 имеет два ядра {x1, x3}, {x2, x4}; граф G3 имеет одно ядро {x2, x4}.

Хроматическое число графа. Предположим, что каждая вершина графа G окрашена в какой-либо цвет так, что никакие две смежные вершины не окрашены одинаково. Если при этом потребовалось К красок, то граф называется хроматическим порядка К. Минимальное число К, при котором граф остается хроматическим, называется хроматическим числом и обозначается γ. Для графа G, изображенного на рис.3.1.13, хроматическое число γ (G)=3.

Рис. 13.

Теорема. Для каждого графа F выполняется неравенство n£ a(G)g(G), где n=|Х| мощность множества X, a(G) – число внутренней устойчивости, g(G) – хроматическое число графа.

Доказательство. Все множество вершин графа можно разбить на g внутренне устойчивых множеств, состоящих из точек одинакового цвета. Пусть внутренне устойчивые множества содержат m₁, …, m_g вершин. m_i£ a(G), т.к. a(G) по определению есть максимальное число вершин внутренне устойчивых множеств. Но n=m₁+m₂+…+m_g, следовательно, n£ a(G)g(G).

Задача о раскраске геометрической карты связана с определением хроматического числа графа. Любую географическую карту можно изобразить в виде графа G(x, гx), где вершинами являются страны, а ребрами связаны страны, граничащие между собой. Такой граф является плоским. Гипотеза о четырех красках состоит в утверждении того, что граф, соответствующий любой географической карте, имеет хроматическое число не больше 4. Долгое время это предположение оставалось недоказанным, несмотря на широкий интерес математиков к этой проблеме. Благодаря созданию современных ЭВМ решение этой проблемы стало возможным, что и было проделано американскими математиками К.Аппелем и В.Хакеном. Задача была решена путем сведения ее к некоторым частным вопросам чисто арифметического характера, требующим большого числа вычислений, которые были бы не под силу человек, не вооруженному современной вычислительной техникой.