Внешнепланарный граф

Поделись знанием:
Перейти к: навигация, поиск

В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.

Внешнепланарные графы можно охарактеризовать (аналогично теореме Вагнера для планарных графов) двумя запрещёнными минорами K4и K2,3, или их инвариантами Колен де Вердьера. Эти графы имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Любой внешнепланарный граф раскрашиваем в 3 цвета и имеет вырождение[en] и древесную ширину не больше 2.

Внешнепланарные графы являются подмножеством планарных графов, подграфами параллельно-последовательных графов и круговых графов[en]. Максимальный внешнепланарный граф — это граф, к которому нельзя добавить ребро без потери внешнепланарности. Они также являются хордальными и графами видимости[en].





История

Внешнепланарные графы впервые изучали и назвали Шартран и Харари[1] при рассмотрении задачи определения планарности графов, образованных при помощи совершенных паросочетаний, связывающих две копии базового графа (например, многие из обобщённых графов Петерсена образованы этим способом из двух копий графа-цикла). Как они показали, если базовый граф двусвязен, граф, полученный из него описанным способом, планарен тогда и только тогда, когда базовый граф внешнепланарен и паросочетание образует диэдральные перестановки внешнего цикла.

Определение и описание

Внешнепланарный граф является неориентированным графом, который можно нарисовать на плоскости без пересечений таким образом, что все вершины принадлежат внешней неограниченной грани рисунка. То есть никакая из вершин не окружена полностью рёбрами. Альтернативно граф G внешнепланарен, если граф, образованный из G добавлением новой вершины, соединённой рёбрами со всеми остальными вершинами, планарен[2].

Максимальный внешнепланарный граф — это внешнепланарный граф, к которому нельзя добавить какое-либо ребро, не нарушив свойство внешнепланарности. Любой максимальный внешнепланарный граф с n вершинами имеет в точности 2n − 3 рёбер и любая ограниченная грань максимального внешнепланарного графа является треугольником.

Запрещённые графы

Внешнепланарные графы имеют характеризацию запрещёнными графами, аналогичную теореме Понтрягина — Куратовского и теореме Вагнера для планарных графов — граф внешнепланарен тогда и только тогда, когда он не содержит подразбиения[en] полного графа K4 или полного двудольного графа K2,3 [3]. Альтернативно, граф внешнепланарен тогда и только тогда, когда он не содержит K4 или K2,3 в качестве минора, графа, полученного путём удаления и стягивания рёбер[4].

Граф без треугольников внешнепланарен тогда и только тогда, когда он не содержит подразделений K2,3[5].

Инвариант Колина де Вердьера

Граф внешнепланарен тогда и только тогда, когда его инвариант Колен де Вердьера не превосходит двух. Графы, характеризующиеся подобным образом по значению инварианта Колен де Вердьера (не превосходящего значение 1, 3 или 4) — это линейные леса, планарные графы и вложимые без зацепления графы.

Свойства

Двусвязность и гамильтоновость

Внешнепланарный граф является двусвязным тогда и только тогда, когда внешняя грань образует простой цикл без повторения вершин. Внешнепланарный граф является гамильтоновым тогда и только тогда, когда он двусвязен. В этом случае внешняя грань образует единственный гамильтонов цикл[1][5]. Более обще, размер наиболее длинного цикла во внешнепланарном графе равен числу вершин в наибольшей двусвязной компоненте. По этой причине поиск гамильтоновых циклов и наиболее длинных циклов во внешнепланарных графах может быть осуществлён за линейное время, в контраст к NP-полноте этих задач для произвольных графов.

Любой максимальный внешнепланарный граф удовлетворяет более сильным условиям, чем гамильтоновость — он вершинно панцикличен, что означает, что для любой вершины v и любого числа k в интервале от трёх до числа вершин графа существует цикл длины k, содержащий v. Цикл такой длины может быть найден последовательным удалением треугольника, соединённого с остатком графа единственным ребром, таких, что удаляемая вершина не совпадает с v, пока внешняя грань оставшегося графа не станет длины k[6].

Планарный граф является внешнепланарным тогда и только тогда, когда все его двусвязные компоненты внешнепланарны[5].

Раскраска

Все внешнепланарные графы без петель могут быть раскрашены всего тремя цветами[7]. Этот факт проявляется заметно в упрощенном доказательстве теоремы о картинной галерее[en] Шватала[en] Фиском[8]. Раскраска тремя цветами может быть найдена за линейное время алгоритмом жадной раскраски, который удаляет любую вершину со степенью, не превосходящей двух и раскрашивает оставшийся граф рекурсивно, а затем возвращает каждую из удалённых вершин с цветом, отличным от цветов двух её соседей.

Согласно теореме Визинга хроматический индекс любого графа (минимальное число цветов, необходимых для раскраски рёбер графа так, что никакие два смежных ребра не имеют один цвет) либо равен максимуму степеней вершин графа, либо на единицу больше максимальной степени. Для внешнепланарных графов хроматический индекс равен максимальной степени, если только граф не является циклом нечётной длины[9]. Рёберная раскраска с оптимальным числом цветов может быть найдена за линейное время на основе поиска в ширину слабого двойственного дерева[7].

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

Внешнепланарные графы имеют вырождение[en], не превосходящее 2 — любой подграф внешнепланарного графа содержит вершину со степенью, не превосходящей 2[10].

Внешнепланарные графы имеют древесную ширину, не превосходящую 2, откуда следует, что много задач оптимизации на графах, которые NP-полны для графов общего вида, могут быть решены за полиномиальное время с помощью динамического программирования, если входом служит внешнепланарный граф. Более обще, k-внешнепланарный граф имеет древесную ширину O(k)[11].

Любой внешнепланарный граф можно представить в виде графа пересечений прямоугольников с параллельными осям сторонами, так что внешнепланарные графы имеют интервальную размерность[12][13] максимум два[14][15].

Связанные семейства графов

Любой внешнепланарный граф является планарным. Любой внешнепланарный граф является подграфом параллельно-последовательного графа[16]. Однако не все параллельно-последовательные графы внешнепланарны. Полный двудольный граф K2,3 является планарным и параллельно-последовательным, но не внешнепланарным. С другой стороны, полный граф K4 планарен, но ни параллельно-последователен, ни внешнепланарен. Любой лес и любой кактус внешнепланарны[17].

Cлабо двойственный планарный граф вложенного внешнепланарного графа (граф, имеющий по вершине для каждой ограниченной грани вложения и по ребру для смежных ограниченных граней) является лесом, а слабо двойственный планарный граф графа Халина является внешнепланарным графом. Планарный граф является внешнепланарным тогда и только тогда, когда его слабо двойственный является лесом, и граф является графом Халина тогда и только тогда, когда его слабо двойственный является двусвязным и внешнепланарным[18].

Существует понятие степени внешнепланарности. 1-внешнепланарное вложение графа — это то же самое, что внешнепланарное вложение. Для k > 1 говорят, что планарное вложение является k-внешнепланарным, если удаление вершины из внешней грани приводит к (k − 1)-внешнепланарному вложению. Граф является k-внешнепланарным тогда и только тогда, когда он имеет k-внешнепланарное вложение[19][5].

Любой максимальный внешнепланарный граф является хордальным графом. Любой максимальный внешнепланарный граф является графом видимости[en] простого многоугольника[en][20]. Максимальные внешнепланарные графы образуются как графы триангуляции многоугольников[en]. Они являются также примерами 2-деревьев[en], параллельно-последовательноых графов и хордальных графов.

Любой внешнепланарный граф является круговым графом[en], графом пересечений множества хорд окружности[21][22].

Напишите отзыв о статье "Внешнепланарный граф"

Примечания

  1. ↑ 1 2 Chartrand, Harary, 1967.
  2. ↑ Felsner, 2004.
  3. ↑ Chartrand, Harary (1967); Sysło (1979); Brandstädt, Le, Spinrad (1999), Proposition 7.3.1, p. 117; Felsner (2004).
  4. ↑ Diestel, 2000.
  5. ↑ 1 2 3 4 Sysło, 1979.
  6. ↑ Li, Corneil, Mendelsohn, 2000, с. Proposition 2.5.
  7. ↑ 1 2 Proskurowski, Sysło, 1986.
  8. ↑ Fisk, 1978.
  9. ↑ Fiorini, 1975.
  10. ↑ Lick, White, 1970.
  11. ↑ Baker, 1994.
  12. ↑ Определение интервальной размерности графа можно найти в книге Робертса. Английское название термина — boxicity.
  13. ↑ Робертс, 1986, с. 129.
  14. ↑ Scheinerman, 1984.
  15. ↑ Brandstädt, Le, Spinrad, 1999, с. 54.
  16. ↑ Brandstädt, Le, Spinrad, 1999, с. 174.
  17. ↑ Brandstädt, Le, Spinrad, 1999, с. 169.
  18. ↑ Sysło, Proskurowski, 1983.
  19. ↑ Kane, Basu, 1976.
  20. ↑ El-Gindy (1985); Lin, Skiena (1995); Brandstädt, Le, Spinrad (1999), Theorem 4.10.3, p. 65.
  21. ↑ Wessel, Pöschel, 1985.
  22. ↑ Unger, 1988.

Литература

Ссылки

  • [wwwteo.informatik.uni-rostock.de/isgci/classes/gc_110.html Outerplanar graphs], [wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Classes and Their Inclusions]
  • Weisstein, Eric W. [mathworld.wolfram.com/OutplanarGraph.html Outplanar Graph] (англ.) на сайте Wolfram MathWorld.


<imagemap>: неверное или отсутствующее изображение

 Для улучшения этой статьи желательно?:

Отрывок, характеризующий Внешнепланарный граф

Отдав эти и другие приказания, он вернулся в свою ставку, и под его диктовку была написана диспозиция сражения.
Диспозиция эта, про которую с восторгом говорят французские историки и с глубоким уважением другие историки, была следующая:
«С рассветом две новые батареи, устроенные в ночи, на равнине, занимаемой принцем Экмюльским, откроют огонь по двум противостоящим батареям неприятельским.
В это же время начальник артиллерии 1 го корпуса, генерал Пернетти, с 30 ю орудиями дивизии Компана и всеми гаубицами дивизии Дессе и Фриана, двинется вперед, откроет огонь и засыплет гранатами неприятельскую батарею, против которой будут действовать!
24 орудия гвардейской артиллерии,
30 орудий дивизии Компана
и 8 орудий дивизии Фриана и Дессе,
Всего – 62 орудия.
Начальник артиллерии 3 го корпуса, генерал Фуше, поставит все гаубицы 3 го и 8 го корпусов, всего 16, по флангам батареи, которая назначена обстреливать левое укрепление, что составит против него вообще 40 орудий.
Генерал Сорбье должен быть готов по первому приказанию вынестись со всеми гаубицами гвардейской артиллерии против одного либо другого укрепления.
В продолжение канонады князь Понятовский направится на деревню, в лес и обойдет неприятельскую позицию.
Генерал Компан двинется чрез лес, чтобы овладеть первым укреплением.
По вступлении таким образом в бой будут даны приказания соответственно действиям неприятеля.
Канонада на левом фланге начнется, как только будет услышана канонада правого крыла. Стрелки дивизии Морана и дивизии вице короля откроют сильный огонь, увидя начало атаки правого крыла.
Вице король овладеет деревней [Бородиным] и перейдет по своим трем мостам, следуя на одной высоте с дивизиями Морана и Жерара, которые, под его предводительством, направятся к редуту и войдут в линию с прочими войсками армии.
Все это должно быть исполнено в порядке (le tout se fera avec ordre et methode), сохраняя по возможности войска в резерве.
В императорском лагере, близ Можайска, 6 го сентября, 1812 года».
Диспозиция эта, весьма неясно и спутанно написанная, – ежели позволить себе без религиозного ужаса к гениальности Наполеона относиться к распоряжениям его, – заключала в себе четыре пункта – четыре распоряжения. Ни одно из этих распоряжений не могло быть и не было исполнено.
В диспозиции сказано, первое: чтобы устроенные на выбранном Наполеоном месте батареи с имеющими выравняться с ними орудиями Пернетти и Фуше, всего сто два орудия, открыли огонь и засыпали русские флеши и редут снарядами. Это не могло быть сделано, так как с назначенных Наполеоном мест снаряды не долетали до русских работ, и эти сто два орудия стреляли по пустому до тех пор, пока ближайший начальник, противно приказанию Наполеона, не выдвинул их вперед.
Второе распоряжение состояло в том, чтобы Понятовский, направясь на деревню в лес, обошел левое крыло русских. Это не могло быть и не было сделано потому, что Понятовский, направясь на деревню в лес, встретил там загораживающего ему дорогу Тучкова и не мог обойти и не обошел русской позиции.
Третье распоряжение: Генерал Компан двинется в лес, чтоб овладеть первым укреплением. Дивизия Компана не овладела первым укреплением, а была отбита, потому что, выходя из леса, она должна была строиться под картечным огнем, чего не знал Наполеон.
Четвертое: Вице король овладеет деревнею (Бородиным) и перейдет по своим трем мостам, следуя на одной высоте с дивизиями Марана и Фриана (о которых не сказано: куда и когда они будут двигаться), которые под его предводительством направятся к редуту и войдут в линию с прочими войсками.
Сколько можно понять – если не из бестолкового периода этого, то из тех попыток, которые деланы были вице королем исполнить данные ему приказания, – он должен был двинуться через Бородино слева на редут, дивизии же Морана и Фриана должны были двинуться одновременно с фронта.
Все это, так же как и другие пункты диспозиции, не было и не могло быть исполнено. Пройдя Бородино, вице король был отбит на Колоче и не мог пройти дальше; дивизии же Морана и Фриана не взяли редута, а были отбиты, и редут уже в конце сражения был захвачен кавалерией (вероятно, непредвиденное дело для Наполеона и неслыханное). Итак, ни одно из распоряжений диспозиции не было и не могло быть исполнено. Но в диспозиции сказано, что по вступлении таким образом в бой будут даны приказания, соответственные действиям неприятеля, и потому могло бы казаться, что во время сражения будут сделаны Наполеоном все нужные распоряжения; но этого не было и не могло быть потому, что во все время сражения Наполеон находился так далеко от него, что (как это и оказалось впоследствии) ход сражения ему не мог быть известен и ни одно распоряжение его во время сражения не могло быть исполнено.


Многие историки говорят, что Бородинское сражение не выиграно французами потому, что у Наполеона был насморк, что ежели бы у него не было насморка, то распоряжения его до и во время сражения были бы еще гениальнее, и Россия бы погибла, et la face du monde eut ete changee. [и облик мира изменился бы.] Для историков, признающих то, что Россия образовалась по воле одного человека – Петра Великого, и Франция из республики сложилась в империю, и французские войска пошли в Россию по воле одного человека – Наполеона, такое рассуждение, что Россия осталась могущественна потому, что у Наполеона был большой насморк 26 го числа, такое рассуждение для таких историков неизбежно последовательно.
Ежели от воли Наполеона зависело дать или не дать Бородинское сражение и от его воли зависело сделать такое или другое распоряжение, то очевидно, что насморк, имевший влияние на проявление его воли, мог быть причиной спасения России и что поэтому тот камердинер, который забыл подать Наполеону 24 го числа непромокаемые сапоги, был спасителем России. На этом пути мысли вывод этот несомненен, – так же несомненен, как тот вывод, который, шутя (сам не зная над чем), делал Вольтер, говоря, что Варфоломеевская ночь произошла от расстройства желудка Карла IX. Но для людей, не допускающих того, чтобы Россия образовалась по воле одного человека – Петра I, и чтобы Французская империя сложилась и война с Россией началась по воле одного человека – Наполеона, рассуждение это не только представляется неверным, неразумным, но и противным всему существу человеческому. На вопрос о том, что составляет причину исторических событий, представляется другой ответ, заключающийся в том, что ход мировых событий предопределен свыше, зависит от совпадения всех произволов людей, участвующих в этих событиях, и что влияние Наполеонов на ход этих событий есть только внешнее и фиктивное.
Как ни странно кажется с первого взгляда предположение, что Варфоломеевская ночь, приказанье на которую отдано Карлом IX, произошла не по его воле, а что ему только казалось, что он велел это сделать, и что Бородинское побоище восьмидесяти тысяч человек произошло не по воле Наполеона (несмотря на то, что он отдавал приказания о начале и ходе сражения), а что ему казалось только, что он это велел, – как ни странно кажется это предположение, но человеческое достоинство, говорящее мне, что всякий из нас ежели не больше, то никак не меньше человек, чем великий Наполеон, велит допустить это решение вопроса, и исторические исследования обильно подтверждают это предположение.
В Бородинском сражении Наполеон ни в кого не стрелял и никого не убил. Все это делали солдаты. Стало быть, не он убивал людей.
Солдаты французской армии шли убивать русских солдат в Бородинском сражении не вследствие приказания Наполеона, но по собственному желанию. Вся армия: французы, итальянцы, немцы, поляки – голодные, оборванные и измученные походом, – в виду армии, загораживавшей от них Москву, чувствовали, что le vin est tire et qu'il faut le boire. [вино откупорено и надо выпить его.] Ежели бы Наполеон запретил им теперь драться с русскими, они бы его убили и пошли бы драться с русскими, потому что это было им необходимо.
Когда они слушали приказ Наполеона, представлявшего им за их увечья и смерть в утешение слова потомства о том, что и они были в битве под Москвою, они кричали «Vive l'Empereur!» точно так же, как они кричали «Vive l'Empereur!» при виде изображения мальчика, протыкающего земной шар палочкой от бильбоке; точно так же, как бы они кричали «Vive l'Empereur!» при всякой бессмыслице, которую бы им сказали. Им ничего больше не оставалось делать, как кричать «Vive l'Empereur!» и идти драться, чтобы найти пищу и отдых победителей в Москве. Стало быть, не вследствие приказания Наполеона они убивали себе подобных.
И не Наполеон распоряжался ходом сраженья, потому что из диспозиции его ничего не было исполнено и во время сражения он не знал про то, что происходило впереди его. Стало быть, и то, каким образом эти люди убивали друг друга, происходило не по воле Наполеона, а шло независимо от него, по воле сотен тысяч людей, участвовавших в общем деле. Наполеону казалось только, что все дело происходило по воле его. И потому вопрос о том, был ли или не был у Наполеона насморк, не имеет для истории большего интереса, чем вопрос о насморке последнего фурштатского солдата.
Тем более 26 го августа насморк Наполеона не имел значения, что показания писателей о том, будто вследствие насморка Наполеона его диспозиция и распоряжения во время сражения были не так хороши, как прежние, – совершенно несправедливы.
Выписанная здесь диспозиция нисколько не была хуже, а даже лучше всех прежних диспозиций, по которым выигрывались сражения. Мнимые распоряжения во время сражения были тоже не хуже прежних, а точно такие же, как и всегда. Но диспозиция и распоряжения эти кажутся только хуже прежних потому, что Бородинское сражение было первое, которого не выиграл Наполеон. Все самые прекрасные и глубокомысленные диспозиции и распоряжения кажутся очень дурными, и каждый ученый военный с значительным видом критикует их, когда сражение по ним не выиграно, и самью плохие диспозиции и распоряжения кажутся очень хорошими, и серьезные люди в целых томах доказывают достоинства плохих распоряжений, когда по ним выиграно сражение.
Диспозиция, составленная Вейротером в Аустерлицком сражении, была образец совершенства в сочинениях этого рода, но ее все таки осудили, осудили за ее совершенство, за слишком большую подробность.
Наполеон в Бородинском сражении исполнял свое дело представителя власти так же хорошо, и еще лучше, чем в других сражениях. Он не сделал ничего вредного для хода сражения; он склонялся на мнения более благоразумные; он не путал, не противоречил сам себе, не испугался и не убежал с поля сражения, а с своим большим тактом и опытом войны спокойно и достойно исполнял свою роль кажущегося начальствованья.


Вернувшись после второй озабоченной поездки по линии, Наполеон сказал:
– Шахматы поставлены, игра начнется завтра.
Велев подать себе пуншу и призвав Боссе, он начал с ним разговор о Париже, о некоторых изменениях, которые он намерен был сделать в maison de l'imperatrice [в придворном штате императрицы], удивляя префекта своею памятливостью ко всем мелким подробностям придворных отношений.
Он интересовался пустяками, шутил о любви к путешествиям Боссе и небрежно болтал так, как это делает знаменитый, уверенный и знающий свое дело оператор, в то время как он засучивает рукава и надевает фартук, а больного привязывают к койке: «Дело все в моих руках и в голове, ясно и определенно. Когда надо будет приступить к делу, я сделаю его, как никто другой, а теперь могу шутить, и чем больше я шучу и спокоен, тем больше вы должны быть уверены, спокойны и удивлены моему гению».
Окончив свой второй стакан пунша, Наполеон пошел отдохнуть пред серьезным делом, которое, как ему казалось, предстояло ему назавтра.
Он так интересовался этим предстоящим ему делом, что не мог спать и, несмотря на усилившийся от вечерней сырости насморк, в три часа ночи, громко сморкаясь, вышел в большое отделение палатки. Он спросил о том, не ушли ли русские? Ему отвечали, что неприятельские огни всё на тех же местах. Он одобрительно кивнул головой.
Дежурный адъютант вошел в палатку.
– Eh bien, Rapp, croyez vous, que nous ferons do bonnes affaires aujourd'hui? [Ну, Рапп, как вы думаете: хороши ли будут нынче наши дела?] – обратился он к нему.
– Sans aucun doute, Sire, [Без всякого сомнения, государь,] – отвечал Рапп.
Наполеон посмотрел на него.
– Vous rappelez vous, Sire, ce que vous m'avez fait l'honneur de dire a Smolensk, – сказал Рапп, – le vin est tire, il faut le boire. [Вы помните ли, сударь, те слова, которые вы изволили сказать мне в Смоленске, вино откупорено, надо его пить.]
Наполеон нахмурился и долго молча сидел, опустив голову на руку.
– Cette pauvre armee, – сказал он вдруг, – elle a bien diminue depuis Smolensk. La fortune est une franche courtisane, Rapp; je le disais toujours, et je commence a l'eprouver. Mais la garde, Rapp, la garde est intacte? [Бедная армия! она очень уменьшилась от Смоленска. Фортуна настоящая распутница, Рапп. Я всегда это говорил и начинаю испытывать. Но гвардия, Рапп, гвардия цела?] – вопросительно сказал он.
– Oui, Sire, [Да, государь.] – отвечал Рапп.
Наполеон взял пастильку, положил ее в рот и посмотрел на часы. Спать ему не хотелось, до утра было еще далеко; а чтобы убить время, распоряжений никаких нельзя уже было делать, потому что все были сделаны и приводились теперь в исполнение.
– A t on distribue les biscuits et le riz aux regiments de la garde? [Роздали ли сухари и рис гвардейцам?] – строго спросил Наполеон.
– Oui, Sire. [Да, государь.]
– Mais le riz? [Но рис?]
Рапп отвечал, что он передал приказанья государя о рисе, но Наполеон недовольно покачал головой, как будто он не верил, чтобы приказание его было исполнено. Слуга вошел с пуншем. Наполеон велел подать другой стакан Раппу и молча отпивал глотки из своего.
– У меня нет ни вкуса, ни обоняния, – сказал он, принюхиваясь к стакану. – Этот насморк надоел мне. Они толкуют про медицину. Какая медицина, когда они не могут вылечить насморка? Корвизар дал мне эти пастильки, но они ничего не помогают. Что они могут лечить? Лечить нельзя. Notre corps est une machine a vivre. Il est organise pour cela, c'est sa nature; laissez y la vie a son aise, qu'elle s'y defende elle meme: elle fera plus que si vous la paralysiez en l'encombrant de remedes. Notre corps est comme une montre parfaite qui doit aller un certain temps; l'horloger n'a pas la faculte de l'ouvrir, il ne peut la manier qu'a tatons et les yeux bandes. Notre corps est une machine a vivre, voila tout. [Наше тело есть машина для жизни. Оно для этого устроено. Оставьте в нем жизнь в покое, пускай она сама защищается, она больше сделает одна, чем когда вы ей будете мешать лекарствами. Наше тело подобно часам, которые должны идти известное время; часовщик не может открыть их и только ощупью и с завязанными глазами может управлять ими. Наше тело есть машина для жизни. Вот и все.] – И как будто вступив на путь определений, definitions, которые любил Наполеон, он неожиданно сделал новое определение. – Вы знаете ли, Рапп, что такое военное искусство? – спросил он. – Искусство быть сильнее неприятеля в известный момент. Voila tout. [Вот и все.]


Источник — «http://wiki-org.ru/wiki/index.php?title=Внешнепланарный_граф&oldid=81592900»