Элементы теории графов и история теоремы о четырех красках на школьном математическом кружке
А.
Л. АрзамасцевБиблиографическое описание статьи для цитирования:
Арзамасцев
А.
Л.,
Гомонов
С.
А. Элементы теории графов и история теоремы о четырех красках на школьном математическом кружке // Научно-методический электронный журнал «Концепт». –
2014. – № 8 (август). – С.
16–20. – URL:
http://e-koncept.ru/2014/14202.htm.
Аннотация. Статья носит методический и научно-популярный характер и посвящена проблемам отбора и представления материала для занятия школьного математического кружка, на котором изучаются элементы теории графов и теорема о четырех красках.
Ключевые слова:
графы, история проблемы четырех красок, планарный граф, хроматический граф, 4-раскраска графа
Текст статьи
Арзамасцев Алексей Леонидович, студент физикоматематического факультета ФГБОУ ВПО «Смоленский государственный университет», г. Смоленскalexd8089@gmail.com
Гомонов Сергей Анатольевич,кандидат физикоматематических наук, доцент кафедры прикладной математики ФГБОУ ВПО «Смоленский государственный университет», г. Смоленскrectorat@smolgu.ru
Элементы теории графов и история теоремы о четырех красках
назанятиях вшкольном математическом кружке
Аннотация. Статья носит методический и научнопопулярный характер и посвящена проблемам отбора и представления материала для занятия школьного математического кружка, на котором изучаются элементы теории графови теорема о четырех красках.Ключевые слова: графы, история проблемы четырех красок, планарный граф, хроматический граф, 4раскраска графа.Раздел: (01)педагогика; история педагогики и образования; теория и методика обучения и воспитания (по предметным областям).
1.Материал, предлагаемый учителем на занятии школьного математического кружка, само хронологическое выстраивание этого материала на занятии (или занятиях), принципы отбора и подачи материала, выбор вспомогательных технических средств, определение аудиоили визуального ряда –все это зависит от целей, поставленных перед собой педагогом, от «состава» учащихся (возраст, подготовленность, заинтересованность) и, конечно, от математической и методической подготовленности самого учителя. Правда, многое зависит еще и от того, сколько сил осталось у ведущего кружок человека после проведения «основных» школьных уроков и оформления многочисленных документов.Универсальных рецептов успешного проведения занятий кружка, факультатива или элективного курса, пожалуй, не существует, однако есть ряд факторов, наличие которых помогает сделать занятия кружка интереснее и познавательнее. Обратим внимание на некоторые из них, причем сразу отметим, что именно они и были по возможности учтены при написании второй и третьей частей данной статьи.A)Занятие кружка можно начать с экскурса в историю возникновения раздела математической науки, научного направления, появления интересной, но долго не поддававшейся решению задачи; при этомобязателен и рассказ о людях, имевших непосредственное отношение к соответствующим научным изысканиям.B)Для изложения математической проблемы, скорее всего, понадобится целый ряд совершенно новых для учеников понятий, а значит, если стараться предлагать максимально аккуратные в математическом отношении формулировки определений и теорем, то занятия кружка получатся скучными и малоинтересными. Новые понятия имеет смысл вводить постепенно и лишь с необходимой степенью общности, опираясь на ранее изученный учениками материал (если таковой был) и на возможность прибегнуть к максимальной визуализации (через иллюстрирование) соответствующих понятий (в теории графов во многих случаях это неплохо получается). Некоторую помощь ученикам в освоении материала может оказать и краткий словарик терминов, подобный тому, что завершает текст данной статьи (его тоже при необходимости можно снабдить визуальным рядом).C)Одной из самых заманчивых иллюстраций к изучаемому материалу может явиться получение (с использованием основных понятий и теорем, в данном случае, например, знаменитой теоремы Эйлера для плоских графов) прямо на глазах учеников, а еще лучшес их посильным участием, некоторого частного результата, пусть не столь фундаментального, как сама теорема о четырех красках, новсе же позволяющего показать в «деле» и некоторые понятия, и отдельные теоремы «большой» математики (возможно, даже и не все случаи будут рассмотрены, и не все детали будут учтены, более того, эта недосказанность, вероятно, позволит предложить членам кружка творческое домашнее задание, причем дать его можно в «стендовом» варианте, ради обширных указаний и комментариев).D)Определенную пользу может принести и не слишком обширный, но обязательно содержащий названия книг и статей научнопопулярного характера список рекомендованной литературы, тем более что обширный список по теории графов весьма «опасен» еще и тем, что до сих пор не «устоялась» терминология этого раздела математики.2.Принято считать, что основоположником теории графов является великий российский и немецкий ученый швейцарского происхождения Леонард Эйлер (Le’onardEuler, 1707–1783). Именно решенная Эйлером задача о Кёнигсбергских мостах считается началом математической теории графов (см. [1,2], атакжесочинениесамогоЛ. Эйлера: L. Euler. Solutio problematis ad geometriam situs pertinentis. CommentariiAcademiaePetropolitanae, v. 8 (1736), 128–140). Однако за данной статьей не последовало практически никаких исследований той же тематики, и этот «заговор» молчания математиков продолжался около века, пока не был прерван появлением теоремы о четырех красках [3, 4], столь же знаменитой, что и великая теорема Ферма. Вот это замечательное утверждение: всякую расположенную на сфере или плоскости карту государств–«областей» можно раскрасить, используя не болеечем четыре краски так, чтобы любые две «области», имеющие общий участок границы (одна общая точкаграница общим участком не считается и никакое государство не состоит из разрозненных частей!), будут раскрашены в разные цвета, то есть картабудет «правильно» раскрашена. Предположение об истинности данного утверждения было высказано в 1852 г.математиком Френсисом Гутри. Через своего брата Фредерика он обратился к известному математику Огастесу де Моргану с просьбой высказаться об истинности сформулированного предложения. Де Морган сам не смог дать заключения по поводу утверждения Ф. Гутри, но познакомил с этой любопытной задачей сэра Уильяма Гамильтона и некоторых других своих коллег, так что в 1878 г.эта задача была представлена на всеобщеерассмотрение Артуром Кэли в Лондонском математическом обществе.Уже через год лондонский адвокат Альфред Кемпе опубликовал доказательство истинности утверждения Ф. Гутри, но в его остроумных рассуждениях была обнаружена (через 11 лет,в 1890 г.,математиком Перси Хивудом) ошибка. Сам Перси Хивуд, как и многие другие математики, справиться с задачей Ф. Гутри не смог, хотя переход от раскраски карт к раскраскевершин графов состоялся уже тогда. Однако к середине XXв.было доказано, что любая карта на сфере,изображающая не более 38 стран,может быть «правильно» раскрашена так, что потребуется не более четырех красок. Доказательство же общего утверждения Ф. Гутри было всетаки получено в результате работы с 1970 по 1976 г.целого научного коллектива под руководством математиков Кеннета Аппеля и Вольфгана Хакена из Иллинойского университета в УрбанаШампейн[5; 6] с помощью ЭВМ: примерно за 2000 часов работы ЭВМ нашла правильные 4раскраски всех 1482 неустранимых конфигураций [7; 8]. Метод перебора, намеченный еще А. Кемпе и модифицированный немецким математиком Генрихом Хеешем, был реализованблагодаря появлению «быстросчитающих» машин. В 1997 г.Робертсон, Сандерс, Сеймур и Томас привели обновленное доказательство, в котором сочетались классические представления и новые компьютерные алгоритмы. Однако «классического» доказательства теоремы о четырех красках до сих пор не найдено.3.Перечислим теперь некоторые простейшие преобразования плоских графов, позволяющие упростить процесс нахождения их 4раскрасок, а такжеполучим результат, хотя и более скромный, чем утверждение о существовании правильной 4раскраски любой карты, изображающий не более 38 стран, но и отличающийся большой простатой примененных для его получения соображений.Напомним, что правильной nраскраской плоского неориентированного, не псевдои не мультиграфа G= (V, R) [9, 10] называетсявсякое отображениемножества вершин Vво множество {1,2,...,n}, если для всякого ребра изR
, где, разумеется, и .Впрочем, наличие кратных ребер и петель у графа не является существенным препятствием для введения понятия nраскраски этого графа. Напомним также, что хроматическим числом (G) графа Gназывают минимальное число цветов, в которые можно раскрасить вершины графа Gтак, чтобы концы любого его ребра имели разные цвета, так что теорема Ф. Гутри может быть сформулирована совсем просто: для любого планарного графа Gсправедливо неравенство(G).Итак, если не ставить своей целью доказать утверждение Ф. Гутрив общем виде, то можно достаточно элементарными средствами получить, пусть и скромные, но все же результаты 4раскрашиваемости некоторых плоских графов, в частности, подобные результаты можно получить, если, стараясь найти 4раскраску плоского графа:1)удастся научиться (в результате некоторых преобразований графа) «избавиться» от тех его вершин, чья реберная инцидентность не превышает некоторого фиксированного числа, а значит, появится возможность перейти или к тривиальному графу, или к графу, инцидентность каждой из вершин которого ограничена снизу одним и тем же не очень малым натуральным числом, что,в свою очередь, может позволить оценить снизу и число вершин графа, а значит, граф, по числу вершин не удовлетворяющий этой оценке, будет заведомо 4раскрашиваемый;2)найти более «жесткую» зависимость между числом вершин, ребер и граней плоского графа по сравнению с той, что предлагается знаменитой теоремой Эйлера, «достраивая» данный граф тем или иным способом до имеющегося, например,только треугольные грани.Вотвозможные преобразования конечного плоского неориентированного графа G(не содержащего ни петель, ни кратных ребер), позволяющие считать у Gналичие некоторых дополнительных свойств, упрощающих поиск его 4раскраски:а)Gможно считать связным, в частности, можем считать, что у Gнет изолированных вершин (в противном случае можно перейти к окрашиванию каждой компоненты связности в отдельности);
б)можно считать, что число ребер, инцидентных любой вершине vграфа G, т.е. степень графа в любой его вершине p(v)не меньше четырех (в противном случае такие вершины графа можно удалить вместе с инцидентными им ребрами, затем раскрасить четырьмя красками то, что осталось от исходного графа, а затем вернуть ранее удаленные вершины и ребра и «докрасить» то, что еще окажется неокрашенным);в)можно считать, что нет у рассматриваемого графа и вершин степени 4, так как если v–таковая, т.е. соответствующая часть графа, например, имеет вид(рис.1).
Рис. 1
то, удаляя v, а затем отождествляя и , получим следующую цепочку преобразований графа (точнее, только рассматриваемой части) (рис. 2).
Рис. 2
причем наличие 4раскраски у преобразованного графа немедленно обеспечит наличие таковой и у исходного графа (независимо от того, две или три краски использованы для окрашивания трех вершин и , при этом если и были бы соединены ребром, а тогда и –заведомо нет, то указанное выше отождествление следовало бы применить к и );г)не нарушая общности рассуждения, можем считать, что все грани рассматриваемого графа«треугольные», так как при наличии грани с большим числом сторон мы всегда можем «добавить» соответствующее число ребер, например, так (рис. 3).
Рис.3Если после всех вышеуказанных преобразований мы получим некоторый нетривиальный граф G, то, используя далее следующие обозначения:V–число вершин графа G,R–число ребер графа G,D–число граней графа G(все они треугольные); мы получим, что,то есть,а значит, используя теорему Эйлера [11]:,получаем.Итак, доказана следующая лемма.Лемма.Всякий плоский конечный неориентированный граф без петель и кратных ребер после преобразований (а)–(г) превратится или в тривиальный граф, илив граф, число вершин (V), граней (D) и ребер (R) которого связаносоотношениями:
Теперь, предполагая, что степень каждой из вершин не меньше 5, имеем
а значит, ,что позволяет получить простое следствие, причем существенно для его обоснования то, что многократные применения преобразований (а), (б) и (в) (без применения (г)) хоть и могут на некоторых промежуточных этапах, а именнопосле преобразования (в), привестик росту степени некоторых вершин графа, но всегда, как оказалось, в этой ситуации будет затем возможно применение преобразований (а) и (б), что и приведет к понижению степеней вершин до исходных значений (или даже сделает их ниже).Следствие. Любой плоский граф с числом вершин, меньшим 12, допускает правильную 4раскраску.
Краткий словарь терминовГраф(неориентированный) –множество точек в пространстве (их называют вершинами графа), некоторые пары из нихсоединены между собой линиями произвольной формы (эти линии называют ребрами графа).Граф планарный (плоский)–граф, который можно изобразить на плоскости без пересечения ребер в неконцевых своих точках.Граф тривиальный –граф, состоящий из одной вершины.Псевдограф–граф, содержащий хотя бы одну петлю.Мультиграф–граф, у которого имеются хотя бы две несовпадающие вершины, соединенные более чем одним ребром.Графназывают связным, если для его любых двух различных вершин существует соединяющая их цепь –такая последовательность его ребер, что любые два «соседних» ребра из этой последовательности имеют общую «среднюю» для них концевую точку, то есть имеет вид .Степень вершины графа –(реберная) инцидентность вершины графа –количество ребер графа, имеющих эту вершину концевой точкой.Правильная раскраска графа –раскраска его вершин, при которой никакие две из них, соединенные ребром, не будут окрашены в один цвет.Хроматическое число графа–минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета, то есть правильно его раскрасить.Грань –часть плоскости, ограниченная рёбрами в плоском графеи не содержащая внутри себя вершин и рёбер графа. Внешняя по отношению к графу часть плоскости тоже образует грань.
Ссылки на источники1.Шапорев С. Д. Дискретная математика: курс лекций и практических занятий. –СПб.: БХВПетербург, 2009. –336 с.2.Оре О. Теория графов. –М.:Наука, 1968. –352 с.3.Шапорев С. Д.Указ. соч.4.Оре О.Указ. соч.5.AppelК., HakenW. Everyplanarmapisfourcolorable, 1976. –567 p. 6.Клауди Альсина. Мир математики: в 40 т. Т. 11: Карты метро и нейронные сети. Теорияграфов. –М.: ДеАгостини, 2014. –144 с.7.Шапорев С. Д.Указ. соч.8.AppelК., HakenW.Op. cit.9.Шапорев С. Д.Указ. соч.10.ОреО.Указ. соч.11.Тамже.
Alexey Arzamastsev,Student of the Department of Physics and Mathematics, Smolensk State University, Smolenskalexd8089@gmail.comSergey Gomonov,Candidate of physicomathematical Sciences, Associate Professor at the chair of applied mathematics, Smolensk State University, Smolenskrectorat@smolgu.ruElements of graph theoryand the history of the theorem of four paints at school mathematical clubAbstract.The authors discuss the problems of selection and presentation of sources in school mathematical club, where elements of graph theory and the theorem of four paints are studied.Key words: graphs, theorem of four paints, planar graph, chromatic graph, coloring of graph.References1.Shaporev, S.D. (2009) Diskretnaja matematika: kurs lekcij i prakticheskih zanjatij,BHVPeterburg,St. Peterburg, 336 p.(in Russiаn).2.Ore,O. (1968) Teorija grafov,Nauka,Moscow, 352 p.(in Russiаn).3.Shaporev, S.D. (2009)Op. cit.4.Ore,O. (1968) Op. cit.5.Appel, K. &Haken,W. (1976) Every planar map is four colorable, 567 p. (in Russiаn).6.Klaudi,Al'sina(2014)Mir matematiki: v 40 t. T. 11: Karty metro i nejronnye seti. Teorija grafov, De Agostini, Moscow, 144 p.(in Russiаn).7.Shaporev, S.D. (2009)Op. cit.8.Appel, K. &Haken,W. (1976)Op. cit.9.Shaporev, S.D. (2009) Op. cit.10.Ore,O. (1968) Op. cit.11.Ibid.
Рекомендовано к публикации:ГоревымП.М., кандидатом педагогических наук, главным редактором журнала «Концепт»
Гомонов Сергей Анатольевич,кандидат физикоматематических наук, доцент кафедры прикладной математики ФГБОУ ВПО «Смоленский государственный университет», г. Смоленскrectorat@smolgu.ru
Элементы теории графов и история теоремы о четырех красках
назанятиях вшкольном математическом кружке
Аннотация. Статья носит методический и научнопопулярный характер и посвящена проблемам отбора и представления материала для занятия школьного математического кружка, на котором изучаются элементы теории графови теорема о четырех красках.Ключевые слова: графы, история проблемы четырех красок, планарный граф, хроматический граф, 4раскраска графа.Раздел: (01)педагогика; история педагогики и образования; теория и методика обучения и воспитания (по предметным областям).
1.Материал, предлагаемый учителем на занятии школьного математического кружка, само хронологическое выстраивание этого материала на занятии (или занятиях), принципы отбора и подачи материала, выбор вспомогательных технических средств, определение аудиоили визуального ряда –все это зависит от целей, поставленных перед собой педагогом, от «состава» учащихся (возраст, подготовленность, заинтересованность) и, конечно, от математической и методической подготовленности самого учителя. Правда, многое зависит еще и от того, сколько сил осталось у ведущего кружок человека после проведения «основных» школьных уроков и оформления многочисленных документов.Универсальных рецептов успешного проведения занятий кружка, факультатива или элективного курса, пожалуй, не существует, однако есть ряд факторов, наличие которых помогает сделать занятия кружка интереснее и познавательнее. Обратим внимание на некоторые из них, причем сразу отметим, что именно они и были по возможности учтены при написании второй и третьей частей данной статьи.A)Занятие кружка можно начать с экскурса в историю возникновения раздела математической науки, научного направления, появления интересной, но долго не поддававшейся решению задачи; при этомобязателен и рассказ о людях, имевших непосредственное отношение к соответствующим научным изысканиям.B)Для изложения математической проблемы, скорее всего, понадобится целый ряд совершенно новых для учеников понятий, а значит, если стараться предлагать максимально аккуратные в математическом отношении формулировки определений и теорем, то занятия кружка получатся скучными и малоинтересными. Новые понятия имеет смысл вводить постепенно и лишь с необходимой степенью общности, опираясь на ранее изученный учениками материал (если таковой был) и на возможность прибегнуть к максимальной визуализации (через иллюстрирование) соответствующих понятий (в теории графов во многих случаях это неплохо получается). Некоторую помощь ученикам в освоении материала может оказать и краткий словарик терминов, подобный тому, что завершает текст данной статьи (его тоже при необходимости можно снабдить визуальным рядом).C)Одной из самых заманчивых иллюстраций к изучаемому материалу может явиться получение (с использованием основных понятий и теорем, в данном случае, например, знаменитой теоремы Эйлера для плоских графов) прямо на глазах учеников, а еще лучшес их посильным участием, некоторого частного результата, пусть не столь фундаментального, как сама теорема о четырех красках, новсе же позволяющего показать в «деле» и некоторые понятия, и отдельные теоремы «большой» математики (возможно, даже и не все случаи будут рассмотрены, и не все детали будут учтены, более того, эта недосказанность, вероятно, позволит предложить членам кружка творческое домашнее задание, причем дать его можно в «стендовом» варианте, ради обширных указаний и комментариев).D)Определенную пользу может принести и не слишком обширный, но обязательно содержащий названия книг и статей научнопопулярного характера список рекомендованной литературы, тем более что обширный список по теории графов весьма «опасен» еще и тем, что до сих пор не «устоялась» терминология этого раздела математики.2.Принято считать, что основоположником теории графов является великий российский и немецкий ученый швейцарского происхождения Леонард Эйлер (Le’onardEuler, 1707–1783). Именно решенная Эйлером задача о Кёнигсбергских мостах считается началом математической теории графов (см. [1,2], атакжесочинениесамогоЛ. Эйлера: L. Euler. Solutio problematis ad geometriam situs pertinentis. CommentariiAcademiaePetropolitanae, v. 8 (1736), 128–140). Однако за данной статьей не последовало практически никаких исследований той же тематики, и этот «заговор» молчания математиков продолжался около века, пока не был прерван появлением теоремы о четырех красках [3, 4], столь же знаменитой, что и великая теорема Ферма. Вот это замечательное утверждение: всякую расположенную на сфере или плоскости карту государств–«областей» можно раскрасить, используя не болеечем четыре краски так, чтобы любые две «области», имеющие общий участок границы (одна общая точкаграница общим участком не считается и никакое государство не состоит из разрозненных частей!), будут раскрашены в разные цвета, то есть картабудет «правильно» раскрашена. Предположение об истинности данного утверждения было высказано в 1852 г.математиком Френсисом Гутри. Через своего брата Фредерика он обратился к известному математику Огастесу де Моргану с просьбой высказаться об истинности сформулированного предложения. Де Морган сам не смог дать заключения по поводу утверждения Ф. Гутри, но познакомил с этой любопытной задачей сэра Уильяма Гамильтона и некоторых других своих коллег, так что в 1878 г.эта задача была представлена на всеобщеерассмотрение Артуром Кэли в Лондонском математическом обществе.Уже через год лондонский адвокат Альфред Кемпе опубликовал доказательство истинности утверждения Ф. Гутри, но в его остроумных рассуждениях была обнаружена (через 11 лет,в 1890 г.,математиком Перси Хивудом) ошибка. Сам Перси Хивуд, как и многие другие математики, справиться с задачей Ф. Гутри не смог, хотя переход от раскраски карт к раскраскевершин графов состоялся уже тогда. Однако к середине XXв.было доказано, что любая карта на сфере,изображающая не более 38 стран,может быть «правильно» раскрашена так, что потребуется не более четырех красок. Доказательство же общего утверждения Ф. Гутри было всетаки получено в результате работы с 1970 по 1976 г.целого научного коллектива под руководством математиков Кеннета Аппеля и Вольфгана Хакена из Иллинойского университета в УрбанаШампейн[5; 6] с помощью ЭВМ: примерно за 2000 часов работы ЭВМ нашла правильные 4раскраски всех 1482 неустранимых конфигураций [7; 8]. Метод перебора, намеченный еще А. Кемпе и модифицированный немецким математиком Генрихом Хеешем, был реализованблагодаря появлению «быстросчитающих» машин. В 1997 г.Робертсон, Сандерс, Сеймур и Томас привели обновленное доказательство, в котором сочетались классические представления и новые компьютерные алгоритмы. Однако «классического» доказательства теоремы о четырех красках до сих пор не найдено.3.Перечислим теперь некоторые простейшие преобразования плоских графов, позволяющие упростить процесс нахождения их 4раскрасок, а такжеполучим результат, хотя и более скромный, чем утверждение о существовании правильной 4раскраски любой карты, изображающий не более 38 стран, но и отличающийся большой простатой примененных для его получения соображений.Напомним, что правильной nраскраской плоского неориентированного, не псевдои не мультиграфа G= (V, R) [9, 10] называетсявсякое отображениемножества вершин Vво множество {1,2,...,n}, если для всякого ребра изR
, где, разумеется, и .Впрочем, наличие кратных ребер и петель у графа не является существенным препятствием для введения понятия nраскраски этого графа. Напомним также, что хроматическим числом (G) графа Gназывают минимальное число цветов, в которые можно раскрасить вершины графа Gтак, чтобы концы любого его ребра имели разные цвета, так что теорема Ф. Гутри может быть сформулирована совсем просто: для любого планарного графа Gсправедливо неравенство(G).Итак, если не ставить своей целью доказать утверждение Ф. Гутрив общем виде, то можно достаточно элементарными средствами получить, пусть и скромные, но все же результаты 4раскрашиваемости некоторых плоских графов, в частности, подобные результаты можно получить, если, стараясь найти 4раскраску плоского графа:1)удастся научиться (в результате некоторых преобразований графа) «избавиться» от тех его вершин, чья реберная инцидентность не превышает некоторого фиксированного числа, а значит, появится возможность перейти или к тривиальному графу, или к графу, инцидентность каждой из вершин которого ограничена снизу одним и тем же не очень малым натуральным числом, что,в свою очередь, может позволить оценить снизу и число вершин графа, а значит, граф, по числу вершин не удовлетворяющий этой оценке, будет заведомо 4раскрашиваемый;2)найти более «жесткую» зависимость между числом вершин, ребер и граней плоского графа по сравнению с той, что предлагается знаменитой теоремой Эйлера, «достраивая» данный граф тем или иным способом до имеющегося, например,только треугольные грани.Вотвозможные преобразования конечного плоского неориентированного графа G(не содержащего ни петель, ни кратных ребер), позволяющие считать у Gналичие некоторых дополнительных свойств, упрощающих поиск его 4раскраски:а)Gможно считать связным, в частности, можем считать, что у Gнет изолированных вершин (в противном случае можно перейти к окрашиванию каждой компоненты связности в отдельности);
б)можно считать, что число ребер, инцидентных любой вершине vграфа G, т.е. степень графа в любой его вершине p(v)не меньше четырех (в противном случае такие вершины графа можно удалить вместе с инцидентными им ребрами, затем раскрасить четырьмя красками то, что осталось от исходного графа, а затем вернуть ранее удаленные вершины и ребра и «докрасить» то, что еще окажется неокрашенным);в)можно считать, что нет у рассматриваемого графа и вершин степени 4, так как если v–таковая, т.е. соответствующая часть графа, например, имеет вид(рис.1).
Рис. 1
то, удаляя v, а затем отождествляя и , получим следующую цепочку преобразований графа (точнее, только рассматриваемой части) (рис. 2).
Рис. 2
причем наличие 4раскраски у преобразованного графа немедленно обеспечит наличие таковой и у исходного графа (независимо от того, две или три краски использованы для окрашивания трех вершин и , при этом если и были бы соединены ребром, а тогда и –заведомо нет, то указанное выше отождествление следовало бы применить к и );г)не нарушая общности рассуждения, можем считать, что все грани рассматриваемого графа«треугольные», так как при наличии грани с большим числом сторон мы всегда можем «добавить» соответствующее число ребер, например, так (рис. 3).
Рис.3Если после всех вышеуказанных преобразований мы получим некоторый нетривиальный граф G, то, используя далее следующие обозначения:V–число вершин графа G,R–число ребер графа G,D–число граней графа G(все они треугольные); мы получим, что,то есть,а значит, используя теорему Эйлера [11]:,получаем.Итак, доказана следующая лемма.Лемма.Всякий плоский конечный неориентированный граф без петель и кратных ребер после преобразований (а)–(г) превратится или в тривиальный граф, илив граф, число вершин (V), граней (D) и ребер (R) которого связаносоотношениями:
Теперь, предполагая, что степень каждой из вершин не меньше 5, имеем
а значит, ,что позволяет получить простое следствие, причем существенно для его обоснования то, что многократные применения преобразований (а), (б) и (в) (без применения (г)) хоть и могут на некоторых промежуточных этапах, а именнопосле преобразования (в), привестик росту степени некоторых вершин графа, но всегда, как оказалось, в этой ситуации будет затем возможно применение преобразований (а) и (б), что и приведет к понижению степеней вершин до исходных значений (или даже сделает их ниже).Следствие. Любой плоский граф с числом вершин, меньшим 12, допускает правильную 4раскраску.
Краткий словарь терминовГраф(неориентированный) –множество точек в пространстве (их называют вершинами графа), некоторые пары из нихсоединены между собой линиями произвольной формы (эти линии называют ребрами графа).Граф планарный (плоский)–граф, который можно изобразить на плоскости без пересечения ребер в неконцевых своих точках.Граф тривиальный –граф, состоящий из одной вершины.Псевдограф–граф, содержащий хотя бы одну петлю.Мультиграф–граф, у которого имеются хотя бы две несовпадающие вершины, соединенные более чем одним ребром.Графназывают связным, если для его любых двух различных вершин существует соединяющая их цепь –такая последовательность его ребер, что любые два «соседних» ребра из этой последовательности имеют общую «среднюю» для них концевую точку, то есть имеет вид .Степень вершины графа –(реберная) инцидентность вершины графа –количество ребер графа, имеющих эту вершину концевой точкой.Правильная раскраска графа –раскраска его вершин, при которой никакие две из них, соединенные ребром, не будут окрашены в один цвет.Хроматическое число графа–минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета, то есть правильно его раскрасить.Грань –часть плоскости, ограниченная рёбрами в плоском графеи не содержащая внутри себя вершин и рёбер графа. Внешняя по отношению к графу часть плоскости тоже образует грань.
Ссылки на источники1.Шапорев С. Д. Дискретная математика: курс лекций и практических занятий. –СПб.: БХВПетербург, 2009. –336 с.2.Оре О. Теория графов. –М.:Наука, 1968. –352 с.3.Шапорев С. Д.Указ. соч.4.Оре О.Указ. соч.5.AppelК., HakenW. Everyplanarmapisfourcolorable, 1976. –567 p. 6.Клауди Альсина. Мир математики: в 40 т. Т. 11: Карты метро и нейронные сети. Теорияграфов. –М.: ДеАгостини, 2014. –144 с.7.Шапорев С. Д.Указ. соч.8.AppelК., HakenW.Op. cit.9.Шапорев С. Д.Указ. соч.10.ОреО.Указ. соч.11.Тамже.
Alexey Arzamastsev,Student of the Department of Physics and Mathematics, Smolensk State University, Smolenskalexd8089@gmail.comSergey Gomonov,Candidate of physicomathematical Sciences, Associate Professor at the chair of applied mathematics, Smolensk State University, Smolenskrectorat@smolgu.ruElements of graph theoryand the history of the theorem of four paints at school mathematical clubAbstract.The authors discuss the problems of selection and presentation of sources in school mathematical club, where elements of graph theory and the theorem of four paints are studied.Key words: graphs, theorem of four paints, planar graph, chromatic graph, coloring of graph.References1.Shaporev, S.D. (2009) Diskretnaja matematika: kurs lekcij i prakticheskih zanjatij,BHVPeterburg,St. Peterburg, 336 p.(in Russiаn).2.Ore,O. (1968) Teorija grafov,Nauka,Moscow, 352 p.(in Russiаn).3.Shaporev, S.D. (2009)Op. cit.4.Ore,O. (1968) Op. cit.5.Appel, K. &Haken,W. (1976) Every planar map is four colorable, 567 p. (in Russiаn).6.Klaudi,Al'sina(2014)Mir matematiki: v 40 t. T. 11: Karty metro i nejronnye seti. Teorija grafov, De Agostini, Moscow, 144 p.(in Russiаn).7.Shaporev, S.D. (2009)Op. cit.8.Appel, K. &Haken,W. (1976)Op. cit.9.Shaporev, S.D. (2009) Op. cit.10.Ore,O. (1968) Op. cit.11.Ibid.
Рекомендовано к публикации:ГоревымП.М., кандидатом педагогических наук, главным редактором журнала «Концепт»
