Материал: baldin_kv_red_matematika_dlia_gumanitariev

Искомая матрица имеет размер (4 9) и выглядит следующим образом

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

Пусть задан псевдограф (имеет петли) содержащий n вершин и m ребер.

Матрицей смежности этого графа As называется матрица размера n n, т. е.

As = (aij),

Любой элемент этой матрицы aij в случае ориентированного графа определяется следующим образом [10].

если вершины (ViVj) [ ek и ребро исходит из вершины Vi;

впротивоположном случае.

Вслучае, если граф G неориентированный, то любой элемент его матрицы смежности определяется так:

если вершины Vi и Vj принадлежит ребру ek; в противоположном случае.

41

Искомая матрица смежности имеет размер 4 4 и выглядит так:

В том случае, если граф кроме петель имеет параллельные ребра матрица As находится по следующим правилам [7].

Если задан ориентированный граф, то каждый элемент его матрицы смежности находится так:

числа ребер, выходящих из вершины Vi и входящих в вершину Vj;

впротивоположном случае.

Вслучае неориентированного графа имеем:

числа ребер между смежными вершинами Vi и

Vj;

в противоположном случае.

Найдем матрицу смежности для графа, изображенного на рис 1. 2.

Рис. 1.32

42

Данному графу соответствует матрица смежности размера 4 4, имеющая вид:

Раскраски

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

Пусть G = (V, Е) — граф, k [ N. Произвольная функция вида f: VG {1, 2, , …, k} называется вершинной k-раскраской, или просто k-раскраской. Раскраска называется правильной, если для любых смежных вершин Vi и Vj выполняется неравенство f(Vi) f(Vj). Граф, для которого существует правильная k-раскраска называется k-раскрашиваемым. В определении раскраски вместо множества {1, 2, , …, k} можно взять произвольное k-элементное множество. Правильную k-раскраску графа можно трактовать как окрашивание каждой его вершины в один из k цветов, при этом смежные вершины должны быть окрашены в разные цвета. При k-раскраске может быть использовано и менее k цветов. Правильную k-раскраску графа G можно рассматривать как разбиение

V1 < V2 < … < Vt = VG, t # k

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

4

Правильная k-раскраска G при k = Х(G) называется минималь-

ной [10, 27].

Нарис.1. приведенаоднаизправильных4-раскрасок,при- чем меньшим числом цветов этот граф раскрасить нельзя [10].

V6

Рис. 1.33

Плоскиеипланарныеграфы

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

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

Примеры плоских графов показаны на рис. 1. 4.

Любой граф, изоморфный плоскому графу, называется планарным [10]. На рис. 1. 5, а приведен плоский граф, а на рис. 1. 5, б — планарный граф, изоморфный графу на рис. 1. 5, а.

44

Рис. 1.34

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

Позднее понятие карты сформулировали так: карта — это связный плоский мультиграф без мостов (ребро графа называется мостом, если его удаление увеличивает число компонент графа, мостами являются ребра e и t в графах на рис. 1. 5, а, б).

В1879 г. английский математик А. Кэли сформулировал гипотезу четырех красок так: всякая карта 4-раскрашиваема.

Часто пользуются другой формулировкой: всякий планарный граф 4-раскрашиваем.

В1890 г. Р. Хивуд показал, что если 4 заменить на 5, то гипотеза легко доказывается, т. е. верна теорема: всякий планарный граф 5-раскрашиваем.

45