Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика. Сборник задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Поиск хроматического числа

Теоретические сведения

Пусть необходимо раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные цвета, при этом число использованных цветов должно быть наименьшим. Это число называется хроматическим числом графа б, будем его обозначать /?(б).

Если граф является полным, т.е. любые две вершины являются смежными, то хроматическое число такого графа равно п, где п — число вершин.

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

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

Снизу хроматическое число можно ограничить так называемым кликовым числом графа. Клика графа — любой максимальный полный подграф. Кликовое число графа б, обозначаемое как р(б) (густота или плотность), — максимальное число вершин в кликах данного графа.

Тогда чем более плотен граф, тем больше будет кликовое число:

И(С) > р(С). (2.4)

Оценку хроматического числа сверху можно произвести на основе следующего утверждения. Если наибольшая из степеней вершин нетривиального графа б равна 5тах, то этот граф 5тах раскрашиваем (т.е. его хроматическое число не превосходит 5тах) всегда, за исключением двух случаев:

  • 1) граф содержит полный подграф на 5тах + 1 вершине;
  • 2) 5тах = 2, и при этом данный граф содержит контур нечетной длины.

Совокупность таких оценок иногда позволяет определить точное или приблизительное значение хроматического числа без применения трудоемких алгоритмов.

Задачи

Задача 2.152. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) связного графа на семи вершинах, имеющего 19 ребер.

Решение.

В данном случае количество ребер значительно превосходит количество вершин. Поэтому начнем рассмотрение с наихудшего случая, т.е. с полного графа на семи вершинах.

Полный граф на семи вершинах содержит 7(7 - 1 )/2 = 21 ребро. Следовательно, задача свелась к оценке хроматического числа графа, полученного удалением из полного графа двух ребер. Как известно, хроматическое число полного графа на семи вершинах равняется количеству вершин, в нашем случае — семи. Рассмотрим случай, когда два удаляемых ребра смежны. После удаления этих ребер получается одна вершина, несмежная двум другим, но, к сожалению, сами эти вершины оказываются смежными между собой и потому получается сэкономить только на одном цвете. Получившийся граф представлен на рис. 2.28. Хроматическое число равняется шести.

Условие задачи 2.152

Рис. 2.28. Условие задачи 2.152

Теперь рассмотрим случай, когда удаляемые ребра несмежны. В этом случае образуются две пары несмежных вершин. А значит, вершины, входящие в такую пару, можно окрасить в один цвет и таким образом получается сэкономить два цвета. Граф с возможной раскраской вершин представлен на рис. 2.29. Хроматическое число этого графа равняется пяти.

Ответ. И = 5 или 6.

Задача 2.153. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) связного графа на 92 вершинах, цик-ломатическое число которого равно двум.

1

Условие задачи 2.152

Рис. 2.29. Условие задачи 2.152

Решение.

Для начала определимся с количеством ребер в исходном графе. По формуле (2.1) получим, что в графе т = 93 ребра.

Построение графа, удовлетворяющего условию задачи, начнем с рассмотрения самого наилучшего с точки зрения хроматического числа случая — дерева, хроматическое число которого постоянно и равно двум. Но, к сожалению, дерево на 92 вершинах содержит всего 92 —1=91 ребро, а потому не подходит для нашей задачи. Таким образом, задача свелась к рассмотрению всех возможных графов, получаемых добавлением двух ребер к дереву на 92 вершинах.

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

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

Ответ. И = 2 или 3.

Задача 2.154. Чему равно хроматическое число простого цикла на восьми вершинах?

Задача 2.155. Чему равно хроматическое число дополнения простого цикла на восьми вершинах?

Задача 2.156. Чему равно хроматическое число полного графа на 15 вершинах, у которого удалили одно ребро?

Задача 2.157. Чему равно хроматическое число полного графа на 15 вершинах, у которого удалили два несмежных ребра?

Задача 2.158. Чему равно хроматическое число полного графа на 15 вершинах, у которого удалили два смежных ребра?

Задача 2.159. Чему равно хроматическое число полного графа на 15 вершинах, у которого удалили 15 ребер, образующих цикл?

Задача 2.160. Чему равно хроматическое число ациклического графа на десяти вершинах и девяти ребрах?

Задача 2.161. Чему равно хроматическое число произвольного графа на десяти вершинах и девяти ребрах?

Задача 2.162. Чему равно хроматическое число произвольного графа на 16 вершинах и 15 ребрах?

Задача 2.163. Чему равно хроматическое число графа на четырех вершинах и трех ребрах?

Задача 2.164. Чему равно хроматическое число связного графа на девяти вершинах?

Задача 2.165. Чему равно хроматическое число ациклического графа на девяти вершинах?

Задача 2.166. Чему равно хроматическое число графа на девяти вершинах, максимальная степень вершины которого равна единице?

Задача 2.167. Чему равно хроматическое число графа на девяти вершинах, максимальная степень вершины которого равна трем?

Задача 2.168. Чему равно хроматическое число связного графа на девяти вершинах, максимальная степень вершины которого равна трем?

Задача 2.169. Чему равно хроматическое число регулярного графа степени 2 на 11 вершинах?

Задача 2.170. Чему равно хроматическое число дополнения полного двудольного графа К49?

Задача 2.171. Чему равно хроматическое число полного двудольного графа К4 9, у которого удалили девять ребер, имеющих одну общую вершину?

Задача 2.172. Чему равно хроматическое число дополнения полного двудольного графа К49, у которого удалили девять ребер, имеющих одну общую вершину?

Задача 2.173. Сколько ребер надо удалить из полного двудольного графа К49, чтобы его хроматическое число стало равно единице?

Задача 2.174. Чему равно хроматическое число графа, являющегося дополнением полного графа на девяти вершинах?

Задача 2.175. Чему равно хроматическое число графа, являющегося дополнением полного графа на девяти вершинах, у которого удалили одно ребро?

Задача 2.176. Чему равно хроматическое число графа, являющегося дополнением пустого графа на девяти вершинах?

Задача 2.177. Чему равно хроматическое число графа, являющегося дополнением полного графа на девяти вершинах, у которого удалили два несмежных ребра?

Задача 2.178. Чему равно хроматическое число графа, являющегося дополнением полного графа на девяти вершинах, у которого удалили два смежных ребра?

Задача 2.179. Чему равно хроматическое число графа, являющегося дополнением полного графа на девяти вершинах, у которого удалили три несмежных ребра?

Задача 2.180. Чему равно хроматическое число графа, являющегося дополнением полного графа на девяти вершинах, у которого удалили три ребра, образующих простой цикл?

Задача 2.181. Чему равно хроматическое число графа, являющегося дополнением полного графа на девяти вершинах, у которого удалили три ребра, имеющих одну общую вершину?

Задача 2.182. Чему равно хроматическое число графа, полученного в результате объединения полного графа на шести вершинах и простого цикла на 11 вершинах (общих вершин нет)?

Задача 2.183. Чему равно хроматическое число графа, полученного в результате сложения полного графа на шести вершинах и простого цикла на 11 вершинах (общих вершин нет)?

Задача 2.184. Чему равно хроматическое число графа, полученного в результате объединения простого цикла на 15 вершинах и простого цикла на десяти вершинах (одна общая вершина)?

Задача 2.185. Чему равно хроматическое число графа, полученного в результате объединения полного графа на 15 вершинах и полного графа на десяти вершинах (одна общая вершина)?

Задача 2.186. Чему равно хроматическое число графа, полученного в результате сложения полного двудольного графа с долями 7 и 9 и простого цикла на восьми вершинах (общих вершин нет)?

Задача 2.187. Не проводя раскраски, найти точное значение хроматического числа графа на рис. 2.30.

Задача 2.188. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) связного графа на 92 вершинах, цик-ломатическое число которого равно двум.

Задача 2.189. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) ациклического графа, в котором число компонент связности ровно в пять раз меньше, чем ребер, а вершин — нечетное количество.

Задача 2.190. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) связного графа на семи вершинах, имеющего 19 ребер.

Задача 2.191. Определить с достаточным обоснованием, чему может быть равно хроматическое число (указать точную цифру или возможный диапазон значений) связного двудольного графа на 12 вершинах с долями, имеющими нечетное число вершин.

Задача 2.192. Определить все возможные значения хроматического числа графов на 17 вершинах, цикломатическое число которых не превосходит двух.

Задача 2.193. Определить все возможные значения хроматического числа для связных графов на 72 вершинах, цикломатическое число которых не превосходит двух.

Задача 2.194. Определить все возможные значения хроматического числа для графа, полученного в результате объединения <7| и (72, где С| и С2 — простые циклы длиной 4 (наличие общих вершин, их количество и относительное расположение неизвестны).

Комбинированные задачи на поиск инвариантов при операциях на графах

Теоретические сведения

Основная теоретическая информация по таким параметрам, как диаметр, цикломатическое и хроматические числа, представлена в предыдущих разделах. Дополним ее двумя фактами, касающимися хроматического числа. При объединении двух графов, не имеющих общих вершин, хроматическое число результирующего графа равно максимальному из хроматических чисел исходных графов. Если (7= (7, иС2, К, п У2 = 0, то

/?(<7) = тах^СД, А((72». (2.5)

При сложении двух графов, не имеющих общих вершин, хроматическое число результирующего графа равно сумме хроматических чисел исходных графов. Итак, если (7 = (7, + (72, V, п У2 = 0, то

А(б) = ОД) + ОД). (2.6)

В случае если общие вершины есть, нужно принимать в расчет их количество и взаимное расположение. Отдельные тонкие моменты рассмотрим на примере задачи 2.195.

Задачи

Задача 2.195. Вычислить диаметр, цикломатическое и хроматическое числа графа ((7, иС2) + С3, где (7| — простой цикл на 20 вершинах; <72 — полный граф на шести вершинах, у которого удалили три ребра, образующих цикл; (73 — полный двудольный граф с долями 6 и 17, у которого удалили одно ребро. При этом графы не имеют общих вершин.

Решение.

Для всех задач данного типа рекомендуется заполнить таблицу, с помощью которой проще отслеживать результаты операций (табл. 2.13).

Таблица 2.13

Таблица для записи решения задачи 2.195

Графы

С,

с,

с2

с2

Сз

Сз

1-я операция

2-я операция

п

т

к

У

И

б

Начнем с графа Єх. Простой цикл на 20 вершинах имеет 20 ребер, он связный (к = 1), его пикломатическое число равно единице (т - п + к = 20 - 20 + 1 = 1). Хроматическое число простого цикла с четным числом вершин равно двум. Диаметр такого графа равен половине длины цикла, т.е. десяти.

Дополнение графа (7] содержит столько же вершин (20), а количество его ребер равно количеству ребер в полном графе на 20 вершинах (20 • 19/2 = 190) за вычетом имеющихся 20, т.е. 170. Компонент связности по-прежнему будет одна, пикломатическое число рассчитывается по формуле т - п + к = 170- 20 + 1 = 151. Интерес представляет расчет хроматического числа: оно будет равно половине числа вершин с округлением вверх, т.е. ]20[ = 10. Диаметр, как видно, равен двум. В итоге заполнены первые два столбца (табл. 2.14).

Таблица 2.14

Решение задачи 2.195, этап первый

Графы

С,

п

20

20

т

20

20- 19/2-20= 170

к

1

1

У

1

170-20+ 1 = 151

А

2

Ю

О

II

о

б

10

2

Перейдем ко второму графу. С2 — полный граф на шести вершинах, у которого удалили три ребра, образующих цикл. Подсчитаем количество ребер: 6 • 5/2 -3 = 12. Граф связный = 1), его циклома-тическое число равно т-п + к= 12-6+1=7. Интерес представляет расчет хроматического числа — оно будет равно: шесть исходных цветов минус два цвета, которые удастся сэкономить, итого четыре. Судя по внешнему виду графа, диаметр будет равен двум (рис. 2.31, а), так как между вершинами, инцидентными удаленным ребрам, расстояние равно двум.

Операция дополнения графа С

Рис. 2.31. Операция дополнения графа С2

Дополнение графа С2 содержит столько же вершин (6), а количество его ребер равно количеству ребер в полном графе на шести вершинах (6 • 5/2 = 15) за вычетом имеющихся 12, т.е. три (еще проще — число ребер в дополнении равно числу ребер, которые были удалены из исходного полного графа, а их было удалено именно три штуки). Компонент связности, исходя из внешнего вида графа, будет четыре (одна компонента на трех вершинах и три изолированные вершины), цикломатическое число рассчитывается по формуле т-пл-к-Ъ-- 6 + 4 = 1 (что хорошо согласуется с внешним видом графа на рис. 2.31, б). В силу наличия цикла нечетной длины хроматическое число будет равно трем. Диаметр равен бесконечности на основании того, что граф несвязный. Сводные результаты представлены в табл. 2.15.

Следующий этап касается графа С3 — это полный двудольный граф с долями 6 и 17, у которого удалили одно ребро. Соответственно, у него 6 + 17 = 23 вершины. Подсчитаем количество ребер: 6 • 17-1 (удаленное) = 102 - 1 = 101. Граф связный = 1), его цикломатическое число равно т - п + к - 101 -(6+ 17)+ 1 = 79. Как и у любого двудольного графа, хроматическое число равно двум. Диаметр

Решение задачи 2.195, этап второй

Графы

с2

С2

п

6

6

т

6- 5/2-3= 12

6 5/2 - 12 = 15 - 12 = 3

к

1

4

У

12-6+ 1 =7

3-6+4=1

А

6- (3 - 1) = 4

3

с!

2

Бесконечность

полного двудольного графа равен двум, при удалении ребра диаметр возрастает до трех.

Дополнение графа (73 содержит столько же вершин (23), а количество его ребер равно количеству ребер в полном графе на 23 вершинах (23 • 22/2 = 253) за вычетом имеющихся 101, т.е. 253 - 101 = 152. Можно посчитать иначе: в верхней доле на 17 вершинах будет образован полный граф на 17 вершинах, и число ребер в нем равно 17 • 16/2 = 136; в нижней доле аналогично получится полный граф на шести вершинах (15 ребер) плюс одно ребро, удаленное в исходном графе, что суммарно равно 136 + 15 + 1 = 152. Компонента связности ровно одна (рис. 2.32).

Операция дополнения графа (7

Рис. 2.32. Операция дополнения графа (73

Цикломатическое число рассчитывается по формуле т - п + к = = 152 - 23 + 1 = 130. Хроматическое число определяется по мощности максимального полного подграфа и равно в этом случае 17. Диаметр равен трем, так как из любой вершины одной доли можно за один

ход добраться в вершину у,-, оттуда по ребру (у,-, уу) — во вторую долю и уже из у,- — в любую вершину второй доли (табл. 2.16).

Таблица 2.16

Решение задачи 2.195, этап третий

Графы

Сз

Сз

п

6+17 = 23

23

т

6- 17-1 = 101

23-22/2- 101 = 152

к

1

1

У

101 -(6 + 17) + 1 = 79

152-23+ 1 = 130

И

2

17

с!

3

3

В результате объединения двух графов (графы не имеют общих вершин) получим следующие характеристики. Количество вершин складывается (20 + 6 = 26), то же верно в отношении ребер (170 + 3 = = 173) и компонент (1 + 4 = 5). Цикломатическое число при объединении графов в случае отсутствия общих вершин также получается путем сложения цикломатических чисел исходных графов. Хроматическое число можно вычислить по формуле (2.3), а диаметр равен бесконечности, так как граф несвязный (табл. 2.17).

Таблица 2.17

Решение задачи 2.195, этап четвертый

Графы

С.

С2

1 -я операция (7, и (72

п

20

6

20 + 6 = 26

т

170

3

170 + 3= 173

к

1

4

1+4 = 5

У

151

1

151 + 1 = 152

А

10

3

тах(10, 3) = 10

с!

2

Бесконечность

Бесконечность

В результате сложения получим следующие характеристики. Количество вершин складывается (26 + 23 = 49), при подсчете ребер к сумме ребер в исходном графе важно не забыть добавить ребра, связующие эти два графа по принципу «каждый с каждым» (173 + + 152 + 23 • 26 = 923). При сложении двух графов без общих вершин всегда получается одна компонента.

Цикломатическое число необходимо считать по формуле (2.2): т-п + к = 923 -49 + 1 = 875. Хроматическое число, рассчитываемое по формуле (2.5), равно 10 + 17 = 27. Диаметр при сложении двух неполных графов без общих вершин равен двум (табл. 2.18).

Таблица 2.18

Решение задачи 2.195, этап пятый

Графы

1 -я операция (7, и 6?2

Сз

2-я операция ((7, и С2) + (73

п

26

23

26 + 23 = 49

т

173

152

173+ 152 + 23-26 = 923

к

5

1

1

У

152

130

923-49 + 1 = 875

А

10

17

10+17 = 27

СІ

Бесконечность

3

2

Ответ. Цикломатическое число равно 875, хроматическое число — 27, диаметр равен 2.

Задача 2.196. Даны графы (рис. 2.33).

Условие задачи 2.196

Рис. 2.33. Условие задачи 2.196

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

  • а) (/[ и С3 и <75 (нет общих вершин);
  • б) (72 и (?5 (одна общая вершина);
  • в) <73 и (?4 (одна общая вершина степени 3);
  • г) (Я* и <75 (три общие вершины степени 1);
  • д) б) и (две общие вершины степени 3);
  • е) (?! и С2 и б3 (одна общая вершина степени 2);
  • ж) б, + б5 (нет общих вершин);
  • з) б, + б2 (две общие вершины степени 2, несмежные в обоих графах);
  • и) б) + б3 (две общие вершины степени 3, несмежные в обоих графах);
  • к) б4 + б5 (три общие вершины, попарно несмежные в обоих графах);
  • л) б3 + б5 (три общие вершины, попарно несмежные в обоих графах);
  • м) б3 + б4 (три общие вершины, попарно несмежные в обоих графах).

Задача 2.197. Вычислить диаметр, цикломатическое и хроматическое числа графа (б, иб2)+ б3, где б] — простой цикл на 20 вершинах; б2 — полный граф на шести вершинах, у которого удалили три ребра, образующих цикл; б3 — полный двудольный граф с долями 6 и 17, у которого удалили одно ребро. При этом графы б] и б2 имеют ровно одну общую вершину.

Задача 2.198. Вычислить диаметр, цикломатическое и хроматическое числа графа (б] иб2)+ б3, где б| — полный граф на девяти вершинах, у которого удалили пять ребер, образующих простой цикл;

62 — полный граф на 13 вершинах, у которого удалили пять ребер, имеющих одну общую вершину; б3 — простой цикл на 21 вершине. При этом графы не имеют общих вершин.

Задача 2.199. Вычислить диаметр, цикломатическое и хроматическое числа графа(б] +б2)иб3, где б] — простой цикл на 70 вершинах; б2 — простой цикл на шести вершинах; б3 — полный двудольный граф с долями 15 и 8, у которого удалили одно ребро. При этом графы б[ и б2 имеют ровно одну общую вершину.

Задача 2.200. Вычислить цикломатическое и хроматическое числа

графа (б1 иб2) + б3, где б, — полный двудольный граф с долями 7 и 9, у которого удалили одно ребро; б2 — полный граф на 11 вершинах, у которого удалили три ребра, имеющих одну общую вершину;

63 — простой цикл на семи вершинах. При этом графы не имеют общих вершин.

Задача 2.201. Вычислить цикломатическое и хроматическое числа

графа (б[ иб2) + б3, где б| — простой цикл на 29 вершинах; б2 — полный граф на шести вершинах; б3 — полный граф на семи вершинах, у которого удалили шесть смежных ребер. При этом графы и (72 имеют ровно одну общую вершину.

Задача 2.202. Вычислить цикломатическое и хроматическое числа

графа (С, + 62) и <73, где — полный граф на девяти вершинах, у которого удалили пять ребер, образующих простой цикл; Є2 полный граф на 13 вершинах, у которого удалили пять ребер, имеющих одну общую вершину; <73 — простой цикл на 21 вершине. При этом графы не имеют общих вершин.

Задача 2.203. Вычислить цикломатическое и хроматическое числа

графа (<7[ +С2)и(/з, где — простой цикл на 70 вершинах; (72 — простой цикл на шести вершинах; <73 — полный двудольный граф с долями 15 и 8, у которого удалили одно ребро. При этом графы (?, и (72 имеют ровно одну общую вершину.

Задача 2.204. Вычислить цикломатическое и хроматическое числа

графа ((7, иС2) + (73, где (7] — полный двудольный граф с долями 7 и 9, у которого удалили одно ребро; <72 — полный граф на 11 вершинах, у которого удалили три ребра, имеющих одну общую вершину; (73 — простой цикл на семи вершинах. При этом графы не имеют общих вершин.

Определение планарности графов

Теоретические сведения

Пусть задан неориентированный граф (7= (К, Ц). Пусть каждой вершине V,- из Vсопоставлена точка я, в некотором евклидовом пространстве, причем а і Ф я, при / Ф у. Пусть каждому ребру и = (у,-, уу) из V сопоставлена непрерывная кривая Ь, соединяющая точки я, и а] и не проходящая через другие точки ак. Тогда если все кривые, сопоставленные ребрам графа, не имеют общих точек, кроме концевых, то это множество точек и кривых называется геометрической реализацией графа (7. Граф называется планарным, если существует его геометрическая реализация на плоскости.

Элементарным стягиванием называется такая процедура: берем ребро е (вместе с инцидентными ему вершинами, например У] и у2) и «стягиваем» его, т.е. удаляем е и отождествляем У] и у2. Полученная при этом вершина инцидентна тем ребрам (отличным от с), которым первоначально были инцидентны У| или у2. Граф (7 называется стягиваемым к графу Я, если Я можно получить из С с помощью некоторой последовательности элементарных стягиваний.

На этом понятии основана важнейшая теорема — критерий планарности. Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в К5 или К3 3.

Также при решении задач может быть полезно следующее соотношение. Для любого связного планарного графа без петель и кратных ребер выполняется неравенство т < 3(п - 2), где п = У;т = (/.

Задачи

Задача 2.205. Является ли планарным полный граф на пяти вершинах? Если да, то уложить его на плоскости.

Задача 2.206. Является ли планарным полный граф на шести вершинах? Если да, то уложить его на плоскости.

Задача 2.207. Является ли планарным полный двудольный граф с долями 3 и 3? Если да, то уложить его на плоскости.

Задача 2.208. Является ли планарным полный двудольный граф с долями 3 и 4? Если да, то уложить его на плоскости.

Задача 2.209. Является ли планарным связный граф с 19 вершинами и 18 ребрами? Если да, то уложить его на плоскости.

Задача 2.210. Является ли планарным связный граф с 20 вершинами и 20 ребрами? Если да, то уложить его на плоскости.

Задача 2.211. Является ли планарным связный граф с шестью вершинами и 14 ребрами? Если да, то уложить его на плоскости.

Задача 2.212. Является ли планарным дополнение простого цикла на шести вершинах? Если да, то уложить его на плоскости.

Задача 2.213. Является ли планарным дополнение простого цикла на семи вершинах? Если да, то уложить его на плоскости.

Задача 2.214. Является ли планарным дополнение простого цикла на восьми вершинах? Если да, то уложить его на плоскости.

Задача 2.215. Проверить, является ли граф, заданный матрицей смежности (табл. 2.19), планарным. Если да, то уложить его на плоскости.

Задача 2.216. Проверить, является ли граф, заданный матрицей смежности (табл. 2.20), планарным. Если да, то уложить его на плоскости.

Условие задачи 2.215

1

2

3

4

5

6

7

8

9

1

1

1

2

1

1

1

1

3

1

1

1

4

1

1

5

1

1

6

1

1

1

7

1

1

8

1

1

1

9

1

1

1

Таблица 2.20

Условие задачи 2.216

1

2

3

4

5

6

1

1

1

1

2

1

1

1

1

1

3

1

1

1

4

1

1

1

1

1

5

1

1

1

6

1

1

1

 
<<   СОДЕРЖАНИЕ   >>