Плоская карта
Cтраница 2
В действительности нашу таблицу можно интерпретировать как плоскую карту, или план, представляющий некую расположенную в пространстве двумерную поверхность. Чтобы найти эту поверхность, мы поступаем следующим образом. [16]
Теорема 2.34. Пяти цветов достаточно для раскрашивания областей плоской карты. [17]
Та же самая процедура получения однородной карты степени 3 из плоской карты применима также для карты на поверхности р-го рода. Далее мы будем рассматривать только связные карты, так как нетрудно видеть, что раскраска несвязной карты является частным случаем раскраски связной. [18]
В 1890 было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. [19]
Теорема 12.9. Гипотеза четырех красок справедлива тогда и только тогда, когда каждая кубическая плоская карта, не имеющая мостов, - раскрашиваема. [20]
В теореме 12.9 уже доказана эквивалентность гипотезы четырех красок утверждению о том, что любая кубическая плоская карта без мостов 4-раскрашиваема. [21]
Дайте краткое индуктивное доказательство того, что шесть цветов достаточно для раскраски ( правильной) любой плоской карты. Используйте тот факт, что если каждая вершина имеет степень, по меньшей мере 3, то, по крайней мере, одна грань имеет самое большое пять сторон. [22]
Он высказал важное утверждение ( 1878 - 1880Ь) о том, что 4-раскрашивание областей кубической плоской карты эквивалентно 3-раскрашиванию ребер этой карты, а затем занялся задачей о разложении кубических планарных графов. [23]
Ясно, что если 4-раскрашиваема всякая плоская карта, не содержащая мостов, то и всякая кубическая плоская карта, не содержащая мостов, также 4-раскрашиваема. Чтобы проверить обратное, предположим, что G - плоская карта без мостов и что все кубические плоские карты без мостов 4-раскрашиваемы. Так как G не содержит мостов, то в ней нет висячих вершин. Если в G существует вершина v степени 2, инцидентная ребрам у и г, то произведем подразбиение ребер у и г, обозначая дополнительные вершины через и и w соответственно. [24]
Плоская карта с корневым ребром получается из плоской карты с помощью ориентации произвольного ребра с последующим выделением одной из двух граней, инцидентных этому ребру; эта грань объявляется внешней гранью карты. [25]
 |
Пленарный граф и его укладка. [26] |
Плоской картой называется связный плоский граф вместе со всеми его гранями. [27]
Мы здесь представим теоретико-графовое обсуждение этой бесславной проблемы. Раскраской плоской карты G называется такое приписывание цветов областям в G, что никакие две смежные области не получают одинакового цвета. Карта G называется л-рас-крашиваемой, если существует ее раскраска, использующая п или менее цветов. [28]
Так, в работе [207] у плоских карт с треугольными областями одно из ребер ( корень) снабжается направлением и указанием, какая из двух примыкающих к нему областей считается правой, а какая левой; при изоморфизме карт их корни, с учетом этих предписаний, должны соответствовать друг другу. В работе [208] у плоской карты с вершинами степени 3 роль корня играет одна из вершин вместе с двумя инцидентными ей ребрами или даже гамильтонов цикл, содержащий эти элементы. В работе [209] рассматривается область R плоскости, ограниченная простыми замкнутыми непересекающимися кривыми 3i3s 3 на каждой из кривых з / дано ( lnl 0 точек. Выводится рекуррентная формула для числа способов разбиения R на односвязные ломтики ( slices) посредством дуг, которые не имеют друг с другом общих концов и которые соединяют различные пары точек на кривых Si 32 ЗУ ПРИ выводе используется довольно сложное комбинаторное тождество, доказанное в той же работе и записываемое в терминах дифференциального исчисления. Дает некоторый класс плоских карт, для которых задача подсчета, таким образом, тоже оказывается решенной. Статья [210] содержит обзор всех этих результатов, а в работе [211] делается попытка подвести фундамент под теорию подсчета плоских карт и, в частности, пересчитываются все плоские корневые карты. К сожалению, все это еще не означает окончательного решения задачи о подсчете обычных ( не корневых) плоских карт и графов; лишь при допущении ( пока что не обоснованном) большой редкости симметричных карт можно получать асимптотические формулы для количества неизоморфных карт путем деления соответствующих формул для количества неизоморфных корневых карт на учетверенное число ребер. [29]
Плоская карта с корневым ребром получается из плоской карты с помощью ориентации произвольного ребра с последующим выделением одной из двух граней, инцидентных этому ребру; эта грань объявляется внешней гранью карты. [30]
Страницы: 1 2 3