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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.06.2015, 16:03
Ответы с готовыми решениями:

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

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

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

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

1
Эксперт по математике/физике
8769 / 6353 / 3419
Регистрация: 14.01.2014
Сообщений: 14,606
16.06.2015, 16:59 2
Граф непланарный, он стягивается в двудольный граф K3,3, если убрать вершину 4, заменив путь 3-4-5 на ребро 3-5, и стянуть две вершины 6 и 7 в одну (6). Тогда в новом двудольном графе будет шесть вершин: слева три вершины - 1,3,6, а справа - 2,5,8.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.06.2015, 16:59
Помогаю со студенческими работами здесь

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru