Математическая культура. Мациевский С.В. - 43 стр.

                     п. 4. Раскрашенный граф
    1. Хроматическое число. Граф k-раскрашиваемый, если каждую вер-
шину можно раскрасить в один из k цветов так, что все смежные вершины
— разных цветов. Если граф k-раскрашивамый, но не (k–1)-раскрашивае-
мый, то он — k-хроматический, а число k —хроматическое число графа.
Хроматическое число обозначим греческой буквой χ. Цвета вершин графов
будем также обозначать греческими буквами.
    Примеры.                                    β
    1. Имеем: χ(Kn) = n. В частности, χ(K3) = 3. α  γ           α
    2. Граф без ребер называется пустым. Для него всегда χ = 1. α    α
    Упр. 9. Выпишите в виде таблицы все 11 графов порядка 4 и соответст-
вующие им хроматические числа.
    2. Двудольные графы. Граф двудольный, если все его вершины мож-
но окрасить в два цвета так, чтобы любое ребро имело разноцветные кон-
цы. Если при этом каждая вершина одного цвета соединена ребром с ка-
ждой вершиной другого цвета, то граф полный двудольный и обозначает-
ся Km,n, где n — число вершин одного цвета, m — другого.
    Граф Km,n имеет ровно m + n вершин и mn ребер.
    Примеры.
    1. Граф K3,3 не планарен.                               α
    2. Граф K1,n называется звездным. Пример: граф K1,3. α β α
    Упр. 10. Нарисуйте на плоскости граф K3,3.
    Теорема. Любой граф, имеющий подграфом K5 или K3,3, непланарен. И
наоборот: любой непланарный граф содержит подграф K5 или K3,3.
    Замечание. В пространстве этой проблемы нет. Любой граф можно
вложить в трехмерное пространство так, чтобы его ребра не пересекались.
    3. Гипотеза четырех красок. Впервые сформулировал эту гипотезу сту-
дент-дипломник Лондонского университета в 1852 году: любую карту на
плоскости можно раскрасить только четырьмя красками так, что никакие
две смежные страны не имеют один цвет. История этой гипотезы — самая
длительная и волнующая в теории графов.
    Переведем задачу на язык графов. Карте сопоставим граф следующим
образом. Пусть вершинами графа будут столицы всех стран, а ребрами —
дороги, соединяющие столицы соседних стран (разумеется, территории стран
подразумеваются связными, т.е. состоящими из одного куска, а соседние
страны имеют общую протяженную границу). Тогда формулировка гипотезы
изменится на следующую: любой планарный граф 4-раскрашиваем.
    Несложно доказать, что пяти красок достаточно. Но четырех
    В 1975 году с помощью компьютера был закончен просмотр 8 571 слу-
чая, к которым была сведена эта проблема. В настоящее время считается,
что гипотеза четырех красок решена положительно.
    Упр. 11. Нарисуйте карту Европы и раскрасьте все страны четырьмя
красками так, чтобы никакие две смежные страны не имели один цвет.

                                   42