Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Пермского университета, сер. Математика. Механика. Информатика, вып. 3 (4), 2006., сс. 86-87. (прореферировано в рж математика, ран, № 07. 08. 13В. 231) Шкарапута А. П., к ф. м н

Название: Пермского университета, сер. Математика. Механика. Информатика, вып. 3 (4), 2006., сс. 86-87. (прореферировано в рж математика, ран, № 07. 08. 13В. 231) Шкарапута А. П., к ф. м н
Раздел: Остальные рефераты
Тип: реферат Добавлен 03:02:28 12 сентября 2011 Похожие работы
Просмотров: 9 Комментариев: 11 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

ПРЕДУВЕДОМЛЕНИЕ РЕДАКЦИИ

Для обеспечения свободного доступа к статье воспроизводится публикация автора в малотиражном журнале, оригинальный печатный текст:

Чечулин В. Л., Об одном варианте доказательства теоремы о 4-раскрашиваемости плоских графов // Вестник Пермского университета, сер. Математика. Механика. Информатика, вып. 3 (4), 2006., сс. 86–87. (прореферировано в РЖ Математика, РАН, реферат № 07.08.‑13В.231)

Шкарапута А. П., к. ф.-м. н.
УДК 519.17

ОБ ОДНОМ ВАРИАНТЕ ДОКАЗАТЕЛЬСТВА
4-РАСКРА­ШИ­ВА­­­ЕМОС­ТИ ПЛОСКИХ ГРАФОВ

Чечулин В. Л. 1 chechulinvl@rambler.ru

1 Россия, 618419, Пермская обл., г. Березники, ул. Пятилетки 50-22

Описан вариант доказательства известной теоремы о 4-раскрашиваемости плоских графов.

© Чечулин В. Л., 2005-2009.

Как известно, каждый связный 4-раскра­ши­ва­емый граф стягиваем к К4 [1, с. 264, теорема 60.1], выберем в произвольном 5-рас­кра­ши­ва­е­мом графе (G, c(G) ≥ 5) произвольную 5-рас­кра­ши­ва­емую область (G5 ), часть которой (вся 4-рас­кра­ши­ваемая, G4 ) стягиваема в К4 , тогда, поскольку эта стянутая область (G5 *, содержащая G4 , стянутую в К4 ) 5-раскрашиваема, то, очевид­но, в ней можно выделить подграф К5 [1] , од­нако граф К5 — не плоский, значит, 5-рас­­кра­шиваемый граф (G) тоже не плоский; ввиду произвольности выбранного 5-рас­кра­ши­ваемого графа получаем утверждение:

Всякий минимально 5-раскраши­ва­емый граф — не плоский
(c(G) ³ 5, Þ G — не плоский);

из которого следует решение проблемы 4-х красок:

Всякий плоский граф 4-раскра­ши­ваем
(G — плоский, Þ c(G) £ 4).[2]

Библиографический список

1. Лекции по теории графов / Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. , М.: «Наука», гл. ред. физ.-мат. лит., 1990.— 384 с.

2. Харари Ф. , Лекции по теории графов, , М.: «Мир», 1973.— 304 с., пер. с англ. Козырев В. В. , ред. Гаврилов Г. П..

3. Самохин А. В. , Проблема 4-х красок: неоконченная история доказательства // Соросовский образовательный журнал, №7, 2000 г., сс. 91-96.

ABOUT А ONE PROOF OF A PLANAR'S GRAPHS 4-CHROMATI­CAL­LY

Chechulin V. L., chechulinvl@rambler.ru

Russia, Perm region, Berezniki, 618419, Pyatyletka st., 50-22.

The proof of the "4-colors" theorem in a graph theory about а planar's graphs 4-chromatically was described..

© Chechulin V. L., 2005-2009.


[1] Получаемый (в G5 *) из выделенного всего 4-рас­кра­шиваемого подграфа (G4 ), стянутого в K4 , присоединением одной 5-ой (5-раскрашиваемой вершины), по 5-ть раскрашиваемости подграфа (G5 ), в нём найдётся такая вершина, соединённая рёбрами со всеми вершинами K4 . Предположения о стягиваемости 5-рас­кра­шиваемой области (G5 ) в К5 — не требуется (гипотезы Хадвиггера не требуется, см. [1, с. 264], [2, с. 161-162] ).

5-раскрашиваемая область (G5 ) выбирается так, что в ней есть некоторая вершина раскрашенная 5‑м цветом, соединённая рёбрами с вершинами связной 4-раскрашиваемой области (G4 ), которая и стягиваема в К4 . (Если такого выбора сделать нельзя, то изначальный граф (G) — менее чем 5‑рас­­крашиваем, и проблема уже решена.)

[2] Исторически попытки доказательства теоремы 4- красок (Мёбиус, 1840, Кемпе, Kempe A. B. , On geographical problem of four colors, Amer. J. Math., 2 (1879), 193–204; Хивуд, Heawood P. J. , Map color theorems, Quart. J. Math., 24 (1890), 332–338 (ссылки по [2])) заключались в прямом способе доказательства: попытке установить достаточное условие,— сколько цветов достаточно для раскрашивания плоской карты (получалось не менее 5-ти), позже Xeeш Х., 1969, и другие поступая так же свели исследование проблемы к исследованию сложных, т. н. неустранимых, конфигураций, 1492‑х, в 1976 г. посредством ЭВМ коллективу математиков при руководстве Аппеля К. и Хейкена В. удалось раскрасить все эти кон­фигурации 4‑мя цветами, на что потребовалось ок. 2000 часов компьютерного времени (Appel K. , Haken W. , Every Planar Map Is Four Colorable., Contemporary Mathematics. Providense (R. I.): Amer. Math. Soc., 1989., Vol 98. 308 p. Cсылки по [1], [3], там же указывалось на сложность проверки такого "доказательства", см. тж. краткий историч. обзор в [3]); логический же ход доказательства необходимости 4-х красок для раскраски плос­кого графа: 5‑ть рас­крашиваемый граф необходимо не плоский (см. текст),— прежде не использовался.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Olya16:48:59 01 сентября 2019
.
.16:48:59 01 сентября 2019
.
.16:48:58 01 сентября 2019
.
.16:48:57 01 сентября 2019
.
.16:48:56 01 сентября 2019

Смотреть все комментарии (11)
Работы, похожие на Реферат: Пермского университета, сер. Математика. Механика. Информатика, вып. 3 (4), 2006., сс. 86-87. (прореферировано в рж математика, ран, № 07. 08. 13В. 231) Шкарапута А. П., к ф. м н

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(258743)
Комментарии (3486)
Copyright © 2005-2020 BestReferat.ru support@bestreferat.ru реклама на сайте

Рейтинг@Mail.ru