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

@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.

Новые блоги и статьи Все статьи Все блоги /
Как писать чистый, тестируемый и качественный код на Python py-thonny 12.07.2025 Помню свой первый проект на Python. Работал тогда быстро, грязно, лишь бы работало. Код был похож на запутанный клубок - переменные по одной букве, функции на 200 строк, комментарии отсутствовали как. . .	Blazor и контроллер сервопривода IoT Meadow Maple Wired 11.07.2025 Я решил разобраться, как можно соединить современные веб-технологии с миром "железа". Интересная комбинация получилась из Blazor в качестве веб-интерфейса и микроконтроллера Meadow с его веб-сервером. . .	Генерация OpenQASM из кода Q# EggHead 10.07.2025 Летом 2024-го я начал эксперименты с библиотекой Q# Bridge, и знаете что? Она оказалась просто находкой для тех, кто работает на стыке разных квантовых экосистем. Основная фишка этой библиотеки -. . .	Изучаем новый шаблон ИИ-чата .NET AI Chat Web App stackOverflow 10.07.2025 В . NET появилось интересное обновление - новый шаблон ИИ-чата под названием . NET AI Chat Web App. Когда я впервые наткнулся на анонс этого шаблона, то сразу понял, что Microsoft наконец-то. . .	Результаты исследования от команды ARP (июль 2025 г.) Programma_Boinc 10.07.2025 Результаты исследования от команды ARP (июль 2025 г. ) Африканский проект по дождям (ARP) World Community Grid снова запущен! Мы рады поделиться обновленной информацией о нашем прогрессе с осени. . .
Angular vs Svelte - что лучше? Reangularity 09.07.2025 Сегодня рынок разделился на несколько четких категорий: тяжеловесы корпоративного уровня (Angular), гибкие универсалы (React), прогрессивные решения (Vue) и новая волна компилируемых фреймворков. . .	Code First и Database First в Entity Framework UnmanagedCoder 09.07.2025 Entity Framework дает нам свободу выбора, предлагая как Code First, так и Database First подходы. Но эта свобода порождает вечный вопрос — какой подход выбрать? Entity Framework — это. . .	Как использовать Bluetooth-модуль HC-05 с Arduino Wired 08.07.2025 Bluetooth - это технология, созданная чтобы заменить кабельные соединения. Обычно ее используют для связи небольших устройств: мобильных телефонов, ноутбуков, наушников и т. д. Работает она на частоте. . .	Руководство по структурам данных Python AI_Generated 08.07.2025 Я отчетливо помню свои первые серьезные проекты на Python - я писал код, он работал, заказчики были относительно довольны. Но однажды мой наставник, взглянув на мою реализацию поиска по огромному. . .	Тестирование энергоэффективности и скорости вычислений видеокарт в BOINC проектах Programma_Boinc 08.07.2025 Тестирование энергоэффективности и скорости вычислений видеокарт в BOINC проектах Опубликовано: 07. 07. 2025 Рубрика: Uncategorized Автор: AlexA Статья размещается на сайте с разрешения. . .

@Vincent_Low 0 / 0 / 0 Регистрация: 12.01.2013 Сообщений: 9

	Является ли планарным граф, заданный списком смежности? 16.06.2015, 16:03. Показов 2388. Ответов 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 $Эксперт по математике/физике$ 10953 / 7285 / 3938 Регистрация: 14.01.2014 Сообщений: 16,637
	16.06.2015, 16:59
	Граф непланарный, он стягивается в двудольный граф K_3,3, если убрать вершину 4, заменив путь 3-4-5 на ребро 3-5, и стянуть две вершины 6 и 7 в одну (6). Тогда в новом двудольном графе будет шесть вершин: слева три вершины - 1,3,6, а справа - 2,5,8. 1

Опции темы