Является ли планарным граф, заданный списком смежности?

@Vincent_Low · Регистрация: 12.01.2013

Студворк — интернет-сервис помощи студентам

Если да, нарисовать соответствующий плоский граф, если нет, доказать по признакам планарности.

1 | 2 5 8
2 | 1 3 7
3 | 2 4 6 8
4 | 3 5
5 | 1 4 6
6 | 3 5 7
7 | 2 6 8
8 | 1 3 7

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

@mathmichel · 16.06.2015, 16:59

Граф непланарный, он стягивается в двудольный граф K_3,3, если убрать вершину 4, заменив путь 3-4-5 на ребро 3-5, и стянуть две вершины 6 и 7 в одну (6). Тогда в новом двудольном графе будет шесть вершин: слева три вершины - 1,3,6, а справа - 2,5,8.

@Vincent_Low 0 / 0 / 0 Регистрация: 12.01.2013 Сообщений: 9
		1
	Является ли планарным граф, заданный списком смежности? 16.06.2015, 16:03. Показов 2029. Ответов 1 Метки нет (Все метки) Если да, нарисовать соответствующий плоский граф, если нет, доказать по признакам планарности. 1 \| 2 5 8 2 \| 1 3 7 3 \| 2 4 6 8 4 \| 3 5 5 \| 1 4 6 6 \| 3 5 7 7 \| 2 6 8 8 \| 1 3 7 граф построил, но не понимаю, как действовать дальше. Разбирал примеры и на них все понятно, но в конкретном случае вообще не знаю. 0

@mathmichel $Эксперт по математике/физике$ 8769 / 6353 / 3419 Регистрация: 14.01.2014 Сообщений: 14,606
	16.06.2015, 16:59	2
	Граф непланарный, он стягивается в двудольный граф K_3,3, если убрать вершину 4, заменив путь 3-4-5 на ребро 3-5, и стянуть две вершины 6 и 7 в одну (6). Тогда в новом двудольном графе будет шесть вершин: слева три вершины - 1,3,6, а справа - 2,5,8. 1

Опции темы