Проблема трех коммунальных услуг

Два представления графа полезности, также известного как граф Томсена или

K_{3,3}

Классическая математическая головоломка, известная как задача трех коммунальных услуг или иногда воды, газа и электричества, требует провести непересекающиеся соединения между тремя домами и тремя коммунальными предприятиями на плоскости . Ставя эту проблему в начале 20 века, Генри Дюдени писал, что это уже старая проблема. Это неразрешимая головоломка : невозможно соединить все девять линий, не пересекая их. Могут быть решены версии проблемы на неплоских поверхностях, таких как тор или лента Мёбиуса , или которые позволяют соединениям проходить через другие дома или инженерные коммуникации.

Эту загадку можно формализовать как задачу топологической теории графов , задав вопрос, является ли полный двудольный граф $K_{3,3}$ , где вершины представляют дома и коммунальные услуги, а ребра представляют их соединения, имеет граф, вложенный в плоскость. Невозможность головоломки соответствует тому факту, что $K_{3,3}$ не является плоским графом . Известны многочисленные доказательства этой невозможности, которые составляют часть доказательства теоремы Куратовского, характеризующей плоские графы двумя запрещенными подграфами, один из которых $K_{3,3}$ . Вопрос о минимизации числа пересечений в рисунках полных двудольных графов известен как задача Турана о кирпичном заводе , и для $K_{3,3}$ минимальное количество пересечений - одно.

$K_{3,3}$ часто называют графом полезности . — это граф с шестью вершинами и девятью ребрами, который применительно к задаче ^[1]Его также называют графиком Томсена в честь химика XIX века Юлиуса Томсена . Это хорошо покрытый граф , наименьший без треугольников кубический граф и наименьший непланарный минимально жесткий граф .

История [ править ]

Обзор истории проблемы трех полезностей дан Куллманом (1979) . Он утверждает, что большинство опубликованных упоминаний о проблеме характеризуют ее как «очень древнюю». ^[2]В самой ранней публикации, найденной Куллманом, Генри Дюдени ( 1917 ) называет это «водой, газом и электричеством». Однако Дьюдени утверждает, что проблема «стара, как мир... намного старше, чем электрическое освещение или даже газ ». ^[3] Дюдени ранее публиковал ту же головоломку в журнале The Strand Magazine в 1913 году. ^[4] Конкурирующее право на приоритет принадлежит Сэму Лойду , который, по словам его сына в посмертной биографии, опубликовал эту задачу в 1900 году. ^[5]

Другая ранняя версия проблемы предполагает подключение трех домов к трем колодцам. ^[6]Это формулируется аналогично другой (и разрешимой) головоломке, в которой также участвуют три дома и три фонтана, причем все три фонтана и один дом касаются прямоугольной стены; головоломка снова включает в себя создание непересекающихся связей, но только между тремя обозначенными парами домов и колодцами или фонтанами, как в современных с числовыми связями . головоломках ^[7]Загадка Лойда «Ссорливые соседи» также предполагает соединение трех домов с тремя воротами тремя непересекающимися дорожками (а не девятью, как в задаче об коммунальных услугах); один дом и трое ворот находятся на стене прямоугольного двора, внутри которого находятся два других дома. ^[8]

Как и в задаче трех полезностей, граф $K_{3,3}$ появляется в публикациях конца 19-го и начала 20-го веков, как в ранних исследованиях структурной жесткости, так и в публикациях конца 19-го и начала 20-го веков. ^[9]^[10] и в теории химических графов , где Юлиус Томсен предложил ее в 1886 году для неопределенной на тот момент структуры бензола . ^[11] В честь работы Томсена $K_{3,3}$ иногда называют графом Томсена. ^[12]

Заявление [ править ]

Задачу трех полезностей можно сформулировать следующим образом:

Предположим, что каждый из трех домов необходимо подключить к компаниям по водоснабжению, газу и электричеству, используя отдельную линию от каждого дома к каждой компании. Есть ли способ сделать все девять соединений так, чтобы ни одна из линий не пересекала друг друга?

Проблема представляет собой абстрактную математическую головоломку, которая накладывает ограничения, которых не было бы в практической инженерной ситуации. Его математическая формализация является частью области топологической теории графов которая изучает встраивание графов , на поверхности . Важная часть головоломки, хотя она часто не указывается явно в неформальных формулировках головоломки, заключается в том, что дома, компании и линии должны быть размещены на двумерной поверхности с топологией плоскости , и что линиям не разрешается проходить через другие здания; иногда это достигается путем показа рисунков домов и компаний и просьбы нарисовать связи в виде линий на одном и том же рисунке. ^[13]^[14]

Говоря более формальными терминами теории графов , проблема заключается в том, является ли полный двудольный граф $K_{3,3}$ представляет собой планарный граф . Этот граф имеет шесть вершин в двух подмножествах по три: по одной вершине для каждого дома и по одной для каждого коммунального предприятия. Он имеет девять ребер: по одному ребру для каждой пары дома с полезностью или, говоря более абстрактно, по одному ребру для каждой пары вершин в одном подмножестве и вершины в другом подмножестве. Планарные графы — это графы, которые можно нарисовать без пересечений на плоскости, и если бы такой рисунок можно было найти, он решил бы загадку трех полезностей. ^[13]^[14]

Решения головоломок [ править ]

Неразрешимость [ править ]

Как это обычно представляется (на плоской двухмерной плоскости), решение головоломки полезности — «нет»: невозможно выполнить все девять соединений без пересечения ни одной линии друг с другом. Другими словами, график $K_{3,3}$ не является плоским. Казимеж Куратовский заявил в 1930 году, что $K_{3,3}$ является неплоским, ^[15]откуда следует, что задача не имеет решения. Куллман (1979) , однако, утверждает, что «достаточно интересно, что Куратовский не опубликовал подробного доказательства того, что [ $K_{3,3}$ ] неплоский». ^[2]

Одно из доказательств невозможности найти плоское вложение $K_{3,3}$ использует анализ случая, включающий теорему о кривой Жордана . ^[16] В этом решении рассматриваются различные возможности расположения вершин относительно 4-циклов графа и показано, что все они несовместимы с плоским вложением. ^[17]

В качестве альтернативы можно показать, что любой без мостов с двудольный планарный граф $V$ вершины и $E$ края имеет $E\leq 2V-4$ объединив формулу Эйлера $V-E+F=2$ (где $F$ — количество граней плоского вложения) с учетом того, что количество граней не превышает половины количества ребер (вершины вокруг каждой грани должны чередоваться между домами и инженерными коммуникациями, поэтому каждая грань имеет не менее четырех ребер, и каждая ребро принадлежит ровно двум граням). На графике полезности $E=9$ и $2V-4=8$ поэтому в графике полезности неверно, что $E\leq 2V-4$ . Поскольку граф полезности не удовлетворяет этому неравенству, он не может быть плоским. ^[18]

Изменение правил [ править ]

Решение на ленте Мёбиуса

Решение на торе

Тор позволяет разместить до 4 инженерных сетей и 4 домов.

$K_{3,3}$ является тороидальным графом , что означает, что его можно вложить без пересечений на тор , поверхность рода один. ^[19] Эти вложения решают версии головоломки, в которой дома и компании нарисованы на кофейной кружке или другой подобной поверхности, а не на плоской плоскости. ^[20] На торе даже достаточно дополнительной свободы, чтобы решить версию головоломки с четырьмя домами и четырьмя инженерными коммуникациями. ^[21]^[5] Аналогично, если головоломка о трех полезностях представлена на листе прозрачного материала, ее можно решить, скрутив и склеив лист, чтобы получилась лента Мёбиуса . ^[22]

Другой способ изменить правила головоломки, который сделал бы ее разрешимой, предложенный Генри Дьюдени , — позволить линиям инженерных коммуникаций проходить через другие дома или коммуникации, кроме тех, которые они соединяют. ^[3]

Свойства графа полезности [ править ]

Помимо головоломки полезности, тот же график $K_{3,3}$ возникает в нескольких других математических контекстах, включая теорию жесткости , классификацию клеток и хорошо покрытых графов , изучение чисел пересечений графов и теорию миноров графов .

Жесткость [ править ]

График полезности $K_{3,3}$ является графом Ламана , что означает, что почти для всех размещений его вершин на плоскости нет способа непрерывно перемещать его вершины, сохраняя при этом все длины ребер, кроме как за счет жесткого движения всей плоскости, и что ни один из его охватов подграфы обладают одинаковым свойством жесткости . Это наименьший пример непланарного графа Ламана. ^[23] Несмотря на то, что граф является минимально жестким, он имеет нежесткие вложения со специальным расположением вершин. ^[9]^[24]Для вложений общего положения полиномиальное уравнение , описывающее все возможные размещения с одинаковой длиной ребра, имеет степень 16, что означает, что в общем случае может быть не более 16 размещений с одинаковой длиной. Можно найти системы длин ребер, для которых до восьми решений этого уравнения описывают реализуемые размещения. ^[24]

графов Другие свойства теории

$K_{3,3}$ — граф без треугольников , в котором каждая вершина имеет ровно три соседа ( кубический граф ). Среди всех подобных графов он самый маленький. Следовательно, это (3,4)-клетка , наименьший граф, имеющий по три соседа на вершину и в котором самый короткий цикл имеет длину четыре. ^[25]

Как и все другие полные двудольные графы , это хорошо покрытый граф , что означает, что каждое максимальное независимое множество имеет одинаковый размер. В этом графе единственные два максимальных независимых множества являются двумя сторонами бираздела и имеют одинаковые размеры. $K_{3,3}$ является одним из семи 3-регулярных 3-связных хорошо покрытых графов. ^[26]

Обобщения [ править ]

Две важные характеристики плоских графов: теорема Куратовского о том, что плоские графы - это именно те графы, которые не содержат ни того, ни другого. $K_{3,3}$ ни полный график $K_{5}$ как подразделение, и теорема Вагнера о том, что планарные графы — это именно те графы, которые не содержат ни $K_{3,3}$ ни $K_{5}$ будучи второстепенным , используйте и обобщайте непланарность $K_{3,3}$ . ^[27]

» Пала Турана « Задача кирпичного завода в более общем плане требует формулу минимального числа пересечений на рисунке полного двудольного графа. $K_{a,b}$ по количеству вершин $a$ и $b$ по обе стороны двураздела. График полезности $K_{3,3}$ может быть нарисован только с одним пересечением, но не с пересечением нуля, поэтому номер его пересечения равен единице. ^[5]^[28]

Ссылки [ править ]

^ Грис, Дэвид ; Шнайдер, Фред Б. (1993), «Глава 19: Теория графов», Логический подход к дискретной математике , Нью-Йорк: Springer, стр. 423–460, doi : 10.1007/978-1-4757-3837-7 , ISBN 978-1-4419-2835-1 , S2CID 206657798 . См. стр. 437: " $K_{3,3}$ известен как граф полезности ».
^ Перейти обратно: ^а ^б Куллман, Дэвид (1979), «Проблема коммунальных услуг», Mathematics Magazine , 52 (5): 299–302, doi : 10.1080/0025570X.1979.11976807 , JSTOR 2689782
^ Перейти обратно: ^а ^б Дьюдени, Генри (1917), «Задача 251 – Вода, газ и электричество» , Забавы по математике , т. 2, № 1, с. 100, Томас Нельсон, с. 73, Бибкод : 1917Natur.100..302. , doi : 10.1038/100302a0 , S2CID 10245524 . Решение, приведенное на стр. 200–201, предполагает проведение линии через один из других домов.
^ Дадени, Генри (1913), «Загадки с некоторыми простыми головоломками для начинающих» , The Strand Magazine , vol. 46, с. 110
^ Перейти обратно: ^а ^б ^с Бейнеке, Лоуэлл ; Уилсон, Робин (2010), «Ранняя история проблемы кирпичного завода», The Mathematical Intelligencer , 32 (2): 41–48, doi : 10.1007/s00283-009-9120-4 , MR 2657999 , S2CID 122588849
^ «Головоломка» , Успешное фермерство , вып. 13, с. 50, 1914 ; «Загадка колодца и дома» , «Спутник юности» , т. 90, нет. 2, с. 392, 1916 .
^ «32. Загадка с фонтаном» , «Собственная книга волшебника, или Все искусство фокусирования» , Нью-Йорк: Дик и Фицджеральд, 1857, стр. 276
^ Лойд, Сэм (1959), «82: Ссорливые соседи» , в Гарднере, Мартине (редактор), « Математические головоломки Сэма Лойда» , Dover Books, стр. 79, ISBN 9780486204987
^ Перейти обратно: ^а ^б Диксон, AC (1899), «О некоторых деформируемых каркасах» , Вестник математики , 29 : 1–21, JFM 30.0622.02
^ Хеннеберг, Л. (1908), «Графическая статика твердых тел» , Энциклопедия математических наук , том. 4, стр. 345–434 . См., в частности , стр. 403 .
^ Томсен, Юлиус (июль 1886 г.), «Конституция бензола» (PDF) , Отчеты Немецкого химического общества , 19 (2): 2944–2950, номер документа : 10.1002/cber.188601902285
^ Боллобас, Бела (1998), Современная теория графов , Тексты для аспирантов по математике, том. 184, Спрингер-Верлаг, Нью-Йорк, с. 23, номер домена : 10.1007/978-1-4612-0619-4 , ISBN 0-387-98488-7 , МР 1633290
^ Перейти обратно: ^а ^б Харари, Франк (1960), «Некоторые исторические и интуитивные аспекты теории графов», SIAM Review , 2 (2): 123–131, Bibcode : 1960SIAMR...2..123H , doi : 10.1137/1002023 , MR 0111698
^ Перейти обратно: ^а ^б Бона, Миклош (2011), Прогулка по комбинаторике: введение в перечисление и теорию графов , World Scientific, стр. 275–277, ISBN 9789814335232 . Бона представляет головоломку (в виде трех домов, соединенных с тремя колодцами) на стр. 275, и пишет на с. 277, что это «эквивалентно проблеме рисования $K_{3,3}$ на плоской поверхности без пересечений».
^ Куратовский, Казимеж (1930), «К проблеме левых кривых в топологии» (PDF) , Fundamenta Mathematicae (на французском языке), 15 : 271–283, doi : 10.4064/fm-15-1-271-283
^ Эйрес, WL (1938), «Некоторые элементарные аспекты топологии», The American Mathematical Monthly , 45 (2): 88–92, doi : 10.1080/00029890.1938.11990773 , JSTOR 2304276 , MR 1524194
^ Трюдо, Ричард Дж. (1993), Введение в теорию графов , Dover Books on Mathematics, Нью-Йорк: Dover Publications, стр. 68–70, ISBN 978-0-486-67870-2
^ Каппрафф, Джей (2001), Связи: геометрический мост между искусством и наукой , Серия K&E, посвященная узлам и всему остальному, том. 25, World Scientific, с. 128, ISBN 9789810245863
^ Харари, Ф. (1964), «Последние результаты в топологической теории графов», Acta Mathematica , 15 (3–4): 405–411, doi : 10.1007/BF01897149 , hdl : 2027.42/41775 , MR 0166775 , S2CID 123170864 ; см. стр. 409.
^ Паркер, Мэтт (2015), Что делать и делать в четвертом измерении: путешествие математика через нарциссические числа, оптимальные алгоритмы свиданий, по крайней мере два вида бесконечности и многое другое , Нью-Йорк: Фаррар, Штраус и Жиру, стр. 180 –181, 191–192, ISBN 978-0-374-53563-6 , МР 3753642
^ О'Бейрн, TH (21 декабря 1961 г.), «Рождественские головоломки и парадоксы, 51: Для мальчиков, мужчин и героев» , New Scientist , vol. 12, нет. 266, стр. 751–753.
^ Ларсен, Могенс Эсром (1994), «Неправильное понимание моих запутанных лабиринтов может сделать меня несчастным», Гай, Ричард К .; Вудро, Роберт Э. (ред.), Материалы конференции памяти Юджина Стренса по развлекательной математике и ее истории, состоявшейся в Университете Калгари, Калгари, Альберта, август 1986 г. , MAA Spectrum, Вашингтон, округ Колумбия: Математическая ассоциация Америки, стр. 289–293, ISBN. 0-88385-516-Х , МР 1303141 . См. рисунок 7, с. 292 .
^ Стрейну, Илеана (2005), «Псевдотриангуляции, жесткость и планирование движения», Discrete & Computational Geometry , 34 (4): 587–635, doi : 10.1007/s00454-005-1184-0 , MR 2173930 , S2CID 25281202 . См. стр. 600: «Не все минимально жесткие графы в общем случае имеют вложения в виде псевдотриангуляций, потому что не все являются плоскими графами. Самый маленький пример - это $K_{3,3}$ ".
^ Перейти обратно: ^а ^б Уолтер, Д.; Хасти, М.Л. (2007), «О девятизвенной связи, ее возможных конфигурациях и условиях парадоксальной подвижности» (PDF) , в Мерле, Жан-Пьер; Дахан, Марк (ред.), 12-й Всемирный конгресс по механизмам и машиноведению (IFToMM 2007) , Международная федерация содействия развитию механизмов и машиноведения
^ Тутте, WT (1947), «Семейство кубических графов», Труды Кембриджского философского общества , 43 (4): 459–474, Бибкод : 1947PCPS...43..459T , doi : 10.1017/s0305004100023720 , MR 0021678 , S2CID 123505185
^ Кэмпбелл, СР; Эллингем, Миннесота ; Ройл, Гордон Ф. (1993), «Характеристика хорошо покрытых кубических графов», Журнал комбинаторной математики и комбинаторных вычислений , 13 : 193–212, MR 1220613
^ Литтл, Чарльз Х.К. (1976), «Теорема о плоских графах», в Кассе, Луи Р.А.; Уоллис, Уолтер Д. (ред.), Комбинаторная математика IV: Материалы четвертой австралийской конференции, состоявшейся в Университете Аделаиды 27–29 августа 1975 г. , Конспекты лекций по математике, том. 560, Springer, стр. 136–141, doi : 10.1007/BFb0097375 , MR 0427121.
^ Пах, Янош ; Шарир, Миха (2009), «5.1 Пересечения — проблема кирпичного завода», Комбинаторная геометрия и ее алгоритмические приложения: Лекции в Алькале , Математические обзоры и монографии, том. 152, Американское математическое общество , стр. 126–127.

Внешние ссылки [ править ]

Головоломка с 3 утилитами в Cut-the-knot
Загадка утилит , объясненная и «решенная» на Archimedes-lab.org
Вайсштейн, Эрик В. , «График полезности» , MathWorld

[gs93-1] Грис, Дэвид ; Шнайдер, Фред Б. (1993), «Глава 19: Теория графов», Логический подход к дискретной математике , Нью-Йорк: Springer, стр. 423–460, doi : 10.1007/978-1-4757-3837-7 , ISBN 978-1-4419-2835-1 , S2CID 206657798 . См. стр. 437: " $K_{3,3}$ известен как граф полезности ».

[kullman1979-2] Перейти обратно: ^а ^б Куллман, Дэвид (1979), «Проблема коммунальных услуг», Mathematics Magazine , 52 (5): 299–302, doi : 10.1080/0025570X.1979.11976807 , JSTOR 2689782

[dud17-3] Перейти обратно: ^а ^б Дьюдени, Генри (1917), «Задача 251 – Вода, газ и электричество» , Забавы по математике , т. 2, № 1, с. 100, Томас Нельсон, с. 73, Бибкод : 1917Natur.100..302. , doi : 10.1038/100302a0 , S2CID 10245524 . Решение, приведенное на стр. 200–201, предполагает проведение линии через один из других домов.

[dud13-4] Дадени, Генри (1913), «Загадки с некоторыми простыми головоломками для начинающих» , The Strand Magazine , vol. 46, с. 110

[early-5] Перейти обратно: ^а ^б ^с Бейнеке, Лоуэлл ; Уилсон, Робин (2010), «Ранняя история проблемы кирпичного завода», The Mathematical Intelligencer , 32 (2): 41–48, doi : 10.1007/s00283-009-9120-4 , MR 2657999 , S2CID 122588849

[3wells-6] «Головоломка» , Успешное фермерство , вып. 13, с. 50, 1914 ; «Загадка колодца и дома» , «Спутник юности» , т. 90, нет. 2, с. 392, 1916 .

[fountains-7] «32. Загадка с фонтаном» , «Собственная книга волшебника, или Все искусство фокусирования» , Нью-Йорк: Дик и Фицджеральд, 1857, стр. 276

[quarrelsome-8] Лойд, Сэм (1959), «82: Ссорливые соседи» , в Гарднере, Мартине (редактор), « Математические головоломки Сэма Лойда» , Dover Books, стр. 79, ISBN 9780486204987

[dixon-9] Перейти обратно: ^а ^б Диксон, AC (1899), «О некоторых деформируемых каркасах» , Вестник математики , 29 : 1–21, JFM 30.0622.02

[henneberg-10] Хеннеберг, Л. (1908), «Графическая статика твердых тел» , Энциклопедия математических наук , том. 4, стр. 345–434 . См., в частности , стр. 403 .

[thomsen-11] Томсен, Юлиус (июль 1886 г.), «Конституция бензола» (PDF) , Отчеты Немецкого химического общества , 19 (2): 2944–2950, номер документа : 10.1002/cber.188601902285

[bollobas-12] Боллобас, Бела (1998), Современная теория графов , Тексты для аспирантов по математике, том. 184, Спрингер-Верлаг, Нью-Йорк, с. 23, номер домена : 10.1007/978-1-4612-0619-4 , ISBN 0-387-98488-7 , МР 1633290

[intuitive-13] Перейти обратно: ^а ^б Харари, Франк (1960), «Некоторые исторические и интуитивные аспекты теории графов», SIAM Review , 2 (2): 123–131, Bibcode : 1960SIAMR...2..123H , doi : 10.1137/1002023 , MR 0111698

[bona-14] Перейти обратно: ^а ^б Бона, Миклош (2011), Прогулка по комбинаторике: введение в перечисление и теорию графов , World Scientific, стр. 275–277, ISBN 9789814335232 . Бона представляет головоломку (в виде трех домов, соединенных с тремя колодцами) на стр. 275, и пишет на с. 277, что это «эквивалентно проблеме рисования $K_{3,3}$ на плоской поверхности без пересечений».

[kuratowski-15] Куратовский, Казимеж (1930), «К проблеме левых кривых в топологии» (PDF) , Fundamenta Mathematicae (на французском языке), 15 : 271–283, doi : 10.4064/fm-15-1-271-283

[ayres-16] Эйрес, WL (1938), «Некоторые элементарные аспекты топологии», The American Mathematical Monthly , 45 (2): 88–92, doi : 10.1080/00029890.1938.11990773 , JSTOR 2304276 , MR 1524194

[trudeau-17] Трюдо, Ричард Дж. (1993), Введение в теорию графов , Dover Books on Mathematics, Нью-Йорк: Dover Publications, стр. 68–70, ISBN 978-0-486-67870-2

[kappraff-18] Каппрафф, Джей (2001), Связи: геометрический мост между искусством и наукой , Серия K&E, посвященная узлам и всему остальному, том. 25, World Scientific, с. 128, ISBN 9789810245863

[harary-19] Харари, Ф. (1964), «Последние результаты в топологической теории графов», Acta Mathematica , 15 (3–4): 405–411, doi : 10.1007/BF01897149 , hdl : 2027.42/41775 , MR 0166775 , S2CID 123170864 ; см. стр. 409.

[parker-20] Паркер, Мэтт (2015), Что делать и делать в четвертом измерении: путешествие математика через нарциссические числа, оптимальные алгоритмы свиданий, по крайней мере два вида бесконечности и многое другое , Нью-Йорк: Фаррар, Штраус и Жиру, стр. 180 –181, 191–192, ISBN 978-0-374-53563-6 , МР 3753642

[obeirne-21] О'Бейрн, TH (21 декабря 1961 г.), «Рождественские головоломки и парадоксы, 51: Для мальчиков, мужчин и героев» , New Scientist , vol. 12, нет. 266, стр. 751–753.

[larsen-22] Ларсен, Могенс Эсром (1994), «Неправильное понимание моих запутанных лабиринтов может сделать меня несчастным», Гай, Ричард К .; Вудро, Роберт Э. (ред.), Материалы конференции памяти Юджина Стренса по развлекательной математике и ее истории, состоявшейся в Университете Калгари, Калгари, Альберта, август 1986 г. , MAA Spectrum, Вашингтон, округ Колумбия: Математическая ассоциация Америки, стр. 289–293, ISBN. 0-88385-516-Х , МР 1303141 . См. рисунок 7, с. 292 .

[streinu-23] Стрейну, Илеана (2005), «Псевдотриангуляции, жесткость и планирование движения», Discrete & Computational Geometry , 34 (4): 587–635, doi : 10.1007/s00454-005-1184-0 , MR 2173930 , S2CID 25281202 . См. стр. 600: «Не все минимально жесткие графы в общем случае имеют вложения в виде псевдотриангуляций, потому что не все являются плоскими графами. Самый маленький пример - это $K_{3,3}$ ".

[wh07-24] Перейти обратно: ^а ^б Уолтер, Д.; Хасти, М.Л. (2007), «О девятизвенной связи, ее возможных конфигурациях и условиях парадоксальной подвижности» (PDF) , в Мерле, Жан-Пьер; Дахан, Марк (ред.), 12-й Всемирный конгресс по механизмам и машиноведению (IFToMM 2007) , Международная федерация содействия развитию механизмов и машиноведения

[tutte-25] Тутте, WT (1947), «Семейство кубических графов», Труды Кембриджского философского общества , 43 (4): 459–474, Бибкод : 1947PCPS...43..459T , doi : 10.1017/s0305004100023720 , MR 0021678 , S2CID 123505185

[cer93-26] Кэмпбелл, СР; Эллингем, Миннесота ; Ройл, Гордон Ф. (1993), «Характеристика хорошо покрытых кубических графов», Журнал комбинаторной математики и комбинаторных вычислений , 13 : 193–212, MR 1220613

[little-27] Литтл, Чарльз Х.К. (1976), «Теорема о плоских графах», в Кассе, Луи Р.А.; Уоллис, Уолтер Д. (ред.), Комбинаторная математика IV: Материалы четвертой австралийской конференции, состоявшейся в Университете Аделаиды 27–29 августа 1975 г. , Конспекты лекций по математике, том. 560, Springer, стр. 136–141, doi : 10.1007/BFb0097375 , MR 0427121.

[ps09-28] Пах, Янош ; Шарир, Миха (2009), «5.1 Пересечения — проблема кирпичного завода», Комбинаторная геометрия и ее алгоритмические приложения: Лекции в Алькале , Математические обзоры и монографии, том. 152, Американское математическое общество , стр. 126–127.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]