Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция № 16


Тема: раскраска графов и карт

Основные вопросы, рассматриваемые на лекции:

1. Раскраска графа. Хроматическое число графа. Теорема Кенига.

2. Раскраска карты. Проблема 4-х красок.

3. О решении проблемы 4-х красок.

Краткое содержание лекционного материала

1. Раскраска графа. Раскраска карты. -раскраска графа – это приписывание цветов его вершинам, такое, что две любые смежные вершины окрасятся в разные цвета. Граф называется -раскрашиваемым, если его можно окрасить не более чем в цветов. Хроматическим числом графа называется наименьшее число цветов, для которого граф имеет -раскраску. Граф называется -хроматическим, если . Граф являеется -раскрашиваемым, если .

Если граф 1-раскрашиваем, то он вполне несвязен, т.е. не содержит ребер. Значит, тогда и только тогда, когда граф вполне не связан.

тогда и только тогда, когда граф не содержит нечетных простых циклов (терема Кенига). Треугольник и являются примерами 3- и 4- хроматического графа. не является примером 5- хроматического графа, так как мы рассматриваем только плоские графы. Можно доказать следующую теорему: каждый плоский граф 5-раскрашиваем.

Гипотеза: каждый ли граф 4-раскрашиваем?

2. Раскраска карт. Раскраской плоской карты называется такое приписывание цветов его областям, что никакие две смежные области не получают одинакового цвета. Карта называется -раскрашиваемым, если существует его раскраска, использующая не более чем в цветов. Можно доказать, что каждая плоская карта 5-раскрашиваема.

В 1852 году Френсис Гутри (Guthrie), составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану (DeMorgan), а тот - математической общественности. Точная формулировка гипотезы опубликована А. Кэли (Cayley, 1878).

Проблема 4-х красок: достаточно ли 4-х красок для раскраски любой плоской карты.

Заметим, что нетрудно доказать: гипотеза «каждый граф 4-раскрашиваем» равносильна гипотезе 4 красок «каждая плоская карта 4-раскрашиваема».

3. О решении проблемы 4-х красок. В 1976 г К. Аппель и В. Хакен доказали, что четырьмя красками можно раскрасить любую карту. Их доказательство очень объемное, опирается на алгоритмы, реализуемые на компьютерах, в нем все вычисления человеку невозможно проверить.

<== предыдущая лекция | следующая лекция ==>
Лекция № 15 | Лекция № 17

Дата добавления: 2014-01-03; Просмотров: 174; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.003 сек.