![]() КАТЕГОРИИ: Архитектура-(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-раскрашиваем, то он вполне несвязен, т.е. не содержит ребер. Значит,
Гипотеза: каждый ли граф 4-раскрашиваем? 2. Раскраска карт. Раскраской плоской карты называется такое приписывание цветов его областям, что никакие две смежные области не получают одинакового цвета. Карта называется В 1852 году Френсис Гутри (Guthrie), составляя карту графств Англии, обратил внимание, что для такой цели вполне хватает четырех красок. Его брат, Фредерик, сообщил об этом наблюдении известному математику О. Де Моргану (DeMorgan), а тот - математической общественности. Точная формулировка гипотезы опубликована А. Кэли (Cayley, 1878). Проблема 4-х красок: достаточно ли 4-х красок для раскраски любой плоской карты. Заметим, что нетрудно доказать: гипотеза «каждый граф 4-раскрашиваем» равносильна гипотезе 4 красок «каждая плоская карта 4-раскрашиваема». 3. О решении проблемы 4-х красок. В 1976 г К. Аппель и В. Хакен доказали, что четырьмя красками можно раскрасить любую карту. Их доказательство очень объемное, опирается на алгоритмы, реализуемые на компьютерах, в нем все вычисления человеку невозможно проверить.
Дата добавления: 2014-01-03; Просмотров: 331; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |