Определить является ли граф планарным

@Maxick94 · Регистрация: 08.12.2012

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

Помогите пожалуйста с заданием.
Определить, является ли граф планарным? Если да, то построить изоморфный плоский граф. Уже целый день сижу, ничего не получается. И подграф $https://www.cyberforum.ru/cgi-bin/latex.cgi?{K}_{33}$ пробовал искать, и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{K}_{5}$ , и строить - ничего не выходит.

Байт · 25.12.2014, 19:13

Maxick94, по формуле Эйлера https://ru.wikipedia.org/wiki/... 0%B0%D1%84

@Maxick94 · 25.12.2014, 22:12 **[ТС]**

Байт,
Все дело в том, что я не могу построить это. Раскладываю на плоскость - ребра пересекаются, стягиваю в графы K33 или K5 - то ребра не хватает, то вершины не стягиваются.

Байт · 25.12.2014, 22:34

Сообщение от Байт

по формуле Эйлера

Да, вершины и ребра пересчитать не сложно. Вот как пересчитать грани? Грань это - цикл. Но скорее всего - не всякий. Наверное, "простейший" цикл, не допускающий представления в виде "суммы" других циклов. Какие-то понятия в ТГ на этот счет были.

Не по теме:

Я не большой специалист по ТГ, просто какие-то обрывки из университетского курса в голове задержались, да и интересно было, штука-то удивительной красоты! Но по жизни работать плотно не пришлось. Так что я на твой граф смотрю таким же бараном, ну, может быть слегка искоса:)

Сообщение от Maxick94

Раскладываю на плоскость

Слушай, покажи какую-нибудь из расскладок, помедитируем, может найдем выход?
я все-таки уперся в формулу Эйлера. Она очень ловко доказывает непланарность Докажет - пойдем пиво пить

Не докажет - значит дальше головы ломать.

@Alamira · 25.12.2014, 22:42

Байт, Maxick94, формулу Эйлера можно применять для связного плоского графа (а такой априори планарен).

Добавлено через 1 минуту
Мне бы с вами пива... Но придётся голову ломать.

Добавлено через 3 минуты
И, Байт, в Вашей ссылке на Вики есть "признаки непланарных графов". Может, их попробовать. Хотя, если честно, пользоваться не приходилось.

Байт · 25.12.2014, 22:51

Сообщение от Alamira

признаки непланарных графов

Ну, это те самые K₅ и K_3,3 (3 старушки-3 колодца). И ТС вот уже 3 часа безуспешно пытается их найти.

Сообщение от Alamira

формулу Эйлера можно применять

Связный-то он как-бы связный. Но если он под Эйлера не уложится - тогда привет - задача решена! Я тут как-то не могу сообразить, что является "гранями" или "странами" в геополитической формулировке. "Базовые" или "простые" циклы, да? А как их посчитать?

@Alamira · 25.12.2014, 23:20

Да не о старушках и колодцах я! Необходимое условие — если граф непланарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2. Так-то оно проще отнестись к исходному изображению. Хотя, опять же, пользоваться не приходилось.

Байт · 25.12.2014, 23:31

Alamira, Вершин степени > 3 в графе ровно 4. Степени > 2 - немеряно (8, кажется). Но ИМХО, второй критерий не впечатляет. На спор могу построить планарный граф со сколь угодным числом вершин степени > 2

@Alamira · 25.12.2014, 23:38

Больше 2 и я могу. А вот 3?..

Добавлено через 4 минуты
Ну а, может, попробовать? Граф на шести вершинах, степень каждой равна 3?

Добавлено через 2 минуты
И потом построить его плоскую укладку: изобразить так, чтобы любые два ребра пересекались только в вершинах графа?

@Maxick94 · 25.12.2014, 23:45 **[ТС]**

Байт,
Все, получилось. Стянулся в К5.

Байт · 25.12.2014, 23:45

Alamira,

Сообщение от Alamira

Необходимое условие

Блин! Так это ж необходимое! И в данном случае ни к чему не обязывающее. Ладно, время позднее. Посмотрим, как откликнется ТС. В конце-концов, это его задача.

@Alamira · 25.12.2014, 23:47

Угу.

Добавлено через 1 минуту
О-о-о! И у него получилось! Хочется верить.

Байт · 25.12.2014, 23:55

Сообщение от Maxick94

Все, получилось. Стянулся в К55.

Если жаба не душит, покажи. Интересно, все-таки. Столько ума потратили.

Так планарный, или нет?

@Maxick94 · 25.12.2014, 23:56 **[ТС]**

Байт,
Не планарный. Мне лень уже выкладывать. Тема закрыта.

Байт · 25.12.2014, 23:58

Не по теме:

Сообщение от Maxick94

Тема закрыта.

Ну вот... Только разыгрались...:cry:

@Alamira · 26.12.2014, 00:05

Не по теме:

Присоединяюсь...:cry:

Байт · 26.12.2014, 00:20

Не по теме:

Сообщение от Alamira

Присоединяюсь..

Чувствую себя уже не так одиноко:)
Но в каждой шутке есть доля шутки... Но эту я бессовестно слямзил. Как то с небольшого бодуна пошел разговор об эпитафиях. И тут моя очень хорошая знакомая говорит. "А я хочу чтоб на моем камушке было написано красивыми буквами Ну вот, только разыгрались..."

@kquick · 03.01.2015, 16:48

Сообщение от Alamira

граф не планарный

Можно добавить, что если в графе есть вершина степени 5 и выше, то граф не планарный.

Байт · 04.01.2015, 12:18

Сообщение от kquick

если в графе есть вершина степени 5 и выше, то граф не планарный.

Чего это вдруг?
Ну хоть "колесо" возьми.

@kquick · 05.01.2015, 03:53

Сообщение от Байт

Ну хоть "колесо" возьми

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

@Maxick94 1 / 1 / 1 Регистрация: 08.12.2012 Сообщений: 47
	25.12.2014, 23:45 [ТС]	10
	Байт, Все, получилось. Стянулся в К5. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	25.12.2014, 23:45	11
	Alamira, Сообщение от Alamira Необходимое условие Блин! Так это ж необходимое! И в данном случае ни к чему не обязывающее. Ладно, время позднее. Посмотрим, как откликнется ТС. В конце-концов, это его задача. 0

@Maxick94 1 / 1 / 1 Регистрация: 08.12.2012 Сообщений: 47
		1
	Определить является ли граф планарным 25.12.2014, 17:38. Показов 20384. Ответов 23 Метки нет (Все метки) Помогите пожалуйста с заданием. Определить, является ли граф планарным? Если да, то построить изоморфный плоский граф. Уже целый день сижу, ничего не получается. И подграф $https://www.cyberforum.ru/cgi-bin/latex.cgi?{K}_{33}$ пробовал искать, и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{K}_{5}$ , и строить - ничего не выходит. Миниатюры 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	25.12.2014, 19:13	2
	Maxick94, по формуле Эйлера https://ru.wikipedia.org/wiki/... 0%B0%D1%84 0

@Maxick94 1 / 1 / 1 Регистрация: 08.12.2012 Сообщений: 47
	25.12.2014, 22:12 [ТС]	3
	Байт, Все дело в том, что я не могу построить это. Раскладываю на плоскость - ребра пересекаются, стягиваю в графы K33 или K5 - то ребра не хватает, то вершины не стягиваются. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	25.12.2014, 22:34	4
	Сообщение от Байт по формуле Эйлера Да, вершины и ребра пересчитать не сложно. Вот как пересчитать грани? Грань это - цикл. Но скорее всего - не всякий. Наверное, "простейший" цикл, не допускающий представления в виде "суммы" других циклов. Какие-то понятия в ТГ на этот счет были. Не по теме: Я не большой специалист по ТГ, просто какие-то обрывки из университетского курса в голове задержались, да и интересно было, штука-то удивительной красоты! Но по жизни работать плотно не пришлось. Так что я на твой граф смотрю таким же бараном, ну, может быть слегка искоса:) Сообщение от Maxick94 Раскладываю на плоскость Слушай, покажи какую-нибудь из расскладок, помедитируем, может найдем выход? я все-таки уперся в формулу Эйлера. Она очень ловко доказывает непланарность Докажет - пойдем пиво пить Не докажет - значит дальше головы ломать. 0

@Alamira 163 / 151 / 36 Регистрация: 04.11.2014 Сообщений: 303
	25.12.2014, 22:42	5
	Байт, Maxick94, формулу Эйлера можно применять для связного плоского графа (а такой априори планарен). Добавлено через 1 минуту Мне бы с вами пива... Но придётся голову ломать. Добавлено через 3 минуты И, Байт, в Вашей ссылке на Вики есть "признаки непланарных графов". Может, их попробовать. Хотя, если честно, пользоваться не приходилось. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	25.12.2014, 22:51	6
	Сообщение от Alamira признаки непланарных графов Ну, это те самые K₅ и K_3,3 (3 старушки-3 колодца). И ТС вот уже 3 часа безуспешно пытается их найти. Сообщение от Alamira формулу Эйлера можно применять Связный-то он как-бы связный. Но если он под Эйлера не уложится - тогда привет - задача решена! Я тут как-то не могу сообразить, что является "гранями" или "странами" в геополитической формулировке. "Базовые" или "простые" циклы, да? А как их посчитать? 0

@Alamira 163 / 151 / 36 Регистрация: 04.11.2014 Сообщений: 303
	25.12.2014, 23:20	7
	Да не о старушках и колодцах я! Необходимое условие — если граф непланарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2. Так-то оно проще отнестись к исходному изображению. Хотя, опять же, пользоваться не приходилось. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	25.12.2014, 23:31	8
	Alamira, Вершин степени > 3 в графе ровно 4. Степени > 2 - немеряно (8, кажется). Но ИМХО, второй критерий не впечатляет. На спор могу построить планарный граф со сколь угодным числом вершин степени > 2 0

@Alamira 163 / 151 / 36 Регистрация: 04.11.2014 Сообщений: 303
	25.12.2014, 23:38	9
	Больше 2 и я могу. А вот 3?.. Добавлено через 4 минуты Ну а, может, попробовать? Граф на шести вершинах, степень каждой равна 3? Добавлено через 2 минуты И потом построить его плоскую укладку: изобразить так, чтобы любые два ребра пересекались только в вершинах графа? 0

@Alamira 163 / 151 / 36 Регистрация: 04.11.2014 Сообщений: 303
	25.12.2014, 23:47	12
	Угу. Добавлено через 1 минуту О-о-о! И у него получилось! Хочется верить. 0

	05.01.2015, 03:53

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	25.12.2014, 23:55	13
	Сообщение от Maxick94 Все, получилось. Стянулся в К55. Если жаба не душит, покажи. Интересно, все-таки. Столько ума потратили. Так планарный, или нет? 1

@Maxick94 1 / 1 / 1 Регистрация: 08.12.2012 Сообщений: 47
	25.12.2014, 23:56 [ТС]	14
	Байт, Не планарный. Мне лень уже выкладывать. Тема закрыта. 0

Байт
	25.12.2014, 23:58 #15
	Не по теме: Сообщение от Maxick94 Тема закрыта. Ну вот... Только разыгрались...:cry: 0

@Alamira
	26.12.2014, 00:05 #16
	Не по теме: Присоединяюсь...:cry: 1

Байт
	26.12.2014, 00:20 #17
	Не по теме: Сообщение от Alamira Присоединяюсь.. Чувствую себя уже не так одиноко:) Но в каждой шутке есть доля шутки... Но эту я бессовестно слямзил. Как то с небольшого бодуна пошел разговор об эпитафиях. И тут моя очень хорошая знакомая говорит. "А я хочу чтоб на моем камушке было написано красивыми буквами Ну вот, только разыгрались..." 0

@kquick 6 / 6 / 5 Регистрация: 15.05.2014 Сообщений: 104
	03.01.2015, 16:48	18
	Сообщение от Alamira граф не планарный Можно добавить, что если в графе есть вершина степени 5 и выше, то граф не планарный. 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	04.01.2015, 12:18	19
	Сообщение от kquick если в графе есть вершина степени 5 и выше, то граф не планарный. Чего это вдруг? Ну хоть "колесо" возьми. 1

@kquick 6 / 6 / 5 Регистрация: 15.05.2014 Сообщений: 104
	05.01.2015, 03:53	20
	Сообщение от Байт Ну хоть "колесо" возьми ага, я хотел сказать, что в планарном графе всегда найдется вершина со степенью не более 5 0