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
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
16.06.2015, 16:03
Ответы с готовыми решениями:

Определить является ли граф планарным
Помогите пожалуйста с заданием. Определить, является ли граф планарным? Если да, то построить изоморфный плоский граф. Уже целый день...

Доказать, что граф является не планарным
Например дан граф G. С помощью гомеоморфных проеобрахований я получил подграф(G штрих). Подграф G(штрих) является гомеоморфным графу К 3.3,...

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

1
Эксперт по математике/физике
10953 / 7285 / 3938
Регистрация: 14.01.2014
Сообщений: 16,637
16.06.2015, 16:59
Граф непланарный, он стягивается в двудольный граф K3,3, если убрать вершину 4, заменив путь 3-4-5 на ребро 3-5, и стянуть две вершины 6 и 7 в одну (6). Тогда в новом двудольном графе будет шесть вершин: слева три вершины - 1,3,6, а справа - 2,5,8.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
16.06.2015, 16:59
Помогаю со студенческими работами здесь

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

Граф представлен матрицей смежности
С первым справилась, помогите со вторым

По матрице смежности построить граф
По матрице смежности построить граф G2

По заданной матрице смежности построить граф
Задано матрицу смежности графа. Построить граф, соответствует ей. Извиняюсь по этой матрице надо построить граф

Задать граф матрицами инциденций и смежности
Задать граф матрицей инциденций, предварительно пронумеровав элементы множеств V и Е. Задать матрицей смежности дополнительный к данному...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

Новые блоги и статьи
Как писать чистый, тестируемый и качественный код на 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 Статья размещается на сайте с разрешения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru