Теорема 2. Для любого планарного графа существует правильная 6–раскраска

Def.Правильная раскраска графа G, при которой использовано k различных цветов, называется k-раскраской, а граф G, для которого существует k-раскраска, называется k-раскрашиваемым.

Def. Наименьшее значение k, для которого существует правильная k -раскраска графа G, называется хроматическим числом графа G и обозначается χ (G)

К поиску правильной окраски графа и его хроматического числа сводится решение многих классических задач.

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

По данной карте построим граф следующим образом. Поставим в соответствие странам карты вершины графа. Если какие-то две страны имеют общий участок границы, то соответствующие им вершины соединим ребром, в противном случае – нет.

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

Степень вершин. Степень графа.

Def. Степенью вершины называется число ребер графа, которым инцидентна эта вершина.

Степ А=3, степ. В=1, степ D=0 и т.д.

Def. Вершину называют четной, если из нее выходит четное число ребер и нечетной в противном случае. (По предыдущему примеру перечислите четные и нечетные вершины)

Теорема 3. В графе сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа. (По пред. примеру 1+3+2+2+3+1+0=2∙6)

Теорема 4. Число нечетных вершин любого графа четно.

По пред. примеру число нечетных вершин – A, B, F,C – 4 – четно.

Решение задач с использованием графов.

Задача 1.

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

Задача 2.

Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания? Да. Изобразить соответствующий граф.

Возможна ли такая компания из 5ти человек, где каждый знаком с тремя и только с тремя другими? Нет. Изобразить соответствующий граф.

Задача 3. Участники пионерского слета, познакомившись, обменялись конвертами с адресами. Докажите, что всего было передано четное число конвертов.

Пусть участники слета A₁, A₂, A₃, …, A_n – вершины графа, а ребра соединяют те вершины, которые обменялись конвертами. Таким образом, степень каждой вершины А_i показывает число конвертов, которые передал участник A_i своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа и по теореме 3 является четным числом.

Задача 4. По матрице весов М построить граф. Заполнить таблицу добавления ребер в МОД по алгоритму Краскала.

Построить граф.

Список ребер	Сумма весов
(2;3)
(2;3), (2;4)	100+150=250
(2;3), (2;4), (2;6)	100+150+180=430
(2;3), (2;4), (2;6), (1;4)	100+150+180+200=630
(2;3), (2;4), (2;6), (1;4), (1;5)	100+150+180+210=840
(2;3), (2;4), (2;6), (1;4), (1;5)б (5;7)	100+150+180+210+210=840

Корневое дерево

Корневое дерево есть специальный способ представления (изображения) дерева. Выбирается некоторая вершина, которая именуется «корнем дерева». При изображении все вершины располагают по ярусам, следующим образом. На нулевом ярусе располагается корень дерева (см. рис.). на 1 ярусе располагают все вершины дерева, смежные с корнем; затем на 2 ярусе — все вершины, смежные с вершинами 1-го яруса; на 3-ем — вершины, смежные с с вершинами 2-го яруса и так далее.

Каждому корневому дереву ставится в соответствие его бинарный код, который строится в процессе полного обхода дерева. Обход начинается с корня и заканчивается корнем. Обход осуществляется слева направо, т.е. сначала проходится левая ветвь, затем следующая и так далее, в конце — самая правая. При обходе необходимо подниматься по ветви (см. следующий рис.) до тех пор, пока это возможно. Затем по ветви опускаются до тех пор, пока не появится возможность продолжить подъем по еще не пройденной ветви. При подъеме с одного яруса на следующий в код дерева записывается 1, при опускании с яруса на ярус — 0. Так дерево на рисунке имеет код (11101101000011011011000100).

Легко видеть, что код дерева обладает следующими свойствами:

· длина кода дерева порядка равна ;

· число нулей равно числу единиц;

· если обрубить код на каком-либо месте, то число единиц на участке от начала кода до данного места не меньше числа нулей на этом участке (разность между этим количеством совпадает с ярусом, на котором прерван обход).

Обратно, по всякому бинарному набору, обладающему этими свойствами, можно построить корневое дерево, код которого совпадает с данным набором.

Дата добавления: 2014-01-20