@Nickname2224

Скажите или покажите как доказать что граф не планарный

0

@3D Homer

Можно показать, что не выполняется необходимое условие: следствие теоремы Эйлера о количестве вершин и ребер. Иначе можно по критерию Понтрягина-Куратовского или критерию Вагнера.

0

@Nickname2224

Критерий Понтрягина-Куратовского:
Если граф G содержит подразбиения графа К 5 или К 3.3, то он не планарный
Что значит,что граф G содержит подразбиение?

0

@3D Homer

Это значит, что в G есть подграф, изоморфный подразбиению K_3,3 или K₅. "Подграф" означает, что из G можно убирать как вершины со всеми инцидентными ребрами, так и ребра отдельно. "Подразбиение" означает, что в ребра графа можно посередине (неточный термин) добавлять вершину степени 2.

0

@Nickname2224

А если мне удалось получить граф G(штрих) из графа G и граф G(штрих) является изоморфным к графу К 3.3 или К 5, то можно утверждать, что граф G- не планарный

Добавлено через 5 минут
Можно?

0

@3D Homer

Если G' -- подграф G, то да.

0

@Nickname2224

с помощью удаления ребра,вершины если степень 2,получил подграф G(штрих) графа G

0

@3D Homer

Есть понятие "подграф". Оно не имеет отношения к степени 2, подразбиениям и стягиваниям.

0

@Nickname2224

Еще раз.
Вот смотрите у меня есть граф G. Я удалил в нем некоторые ребра и вершины степени 2. Исходный граф,который я получил изоморфен графу К 5 или К 3.3. Будет ли граф G не планарный?

0

@3D Homer

Ещё раз. Есть понятие "подграф". Оно не имеет отношения к степени 2.

Так исходный или который получил?

0

@Nickname2224

Вот я удалил ребра и удалил 1 вершину степени 2.
Будет ли граф не планарный?
Ведь граф,который получился является измоморфным графу К3.3

Миниатюры

 

0

@3D Homer

Исходный граф действительно не планарный, но не потому, что вы удалили 1 вершину степени 2.

0

@Nickname2224

Так что получается, для того что бы доказать , что граф не планарный нужно применить сначала к этому графу гомеоморфные преобразования и если граф,который мы получили в результате этих преобразований будет изоморфный либо К 5 либо К3.3,то граф будет не планарный?

0

@3D Homer

Граф без перечеркнутых красным ребер не изоморфен K_3,3, поскольку колодцы соединены ребрами.

Нет. Раз вы хотите игнорировать понятие подграфа (см. сообщение 4), продолжайте игнорировать. Удачи.

0

@Nickname2224

Я не хочу игнорировать.
Подграф G(штрих) графа G-значит,что в графе G можно удалить вершины(вершину) со степенью 2 и инцидентные ей ребра илл удалить просто ребра или и то и другое.
Нельзя же удалять вершины(вершину если ее степень не равно 2)

0

@3D Homer

Хмм, давайте посмотрим, сколько раз было сказано противоположное в этой теме.

"Всего" три раза. Но это не означает, что вы усвоили, что определение понятия "подграф" не содержит фразу "вершина степени 2". Я надеюсь, что вы не усвоите это ранее десятого повторения. В таком случае вы сможете претендовать на звание участника форума, который требует наибольшее количество повторений.

Я хочу подчеркнуть, что ваше непонимание темы "планарность" вызвана не сложностью конструкций, не большим количеством вариантов, которые нужно перепробовать, а либо вашим поразительным упрямством, либо не менее поразительной невнимательностью к высказанным замечаниям.

Что вам мешает посмотреть определение подграфа в Википедии или, лучше, в учебнике? Что мешает подумать о нем, нарисовать несколько вариантов, спросить здесь, если нужно? Но нет, вы упорно путаете понятия гомеоморфных графов и подграфа, которые никак не связаны (по крайней мере, на поверхности).

0

@Nickname2224

Вот граф H является подграфом графа G, путем удаления ребер и(или) вершин вместе со всеми инцидентными ей ребрами.

Миниатюры

 

0

@Nickname2224

Вот допустим данный граф будет не планарным,потому что он содержит подграф,гомеоморфный графу К 3.3

Миниатюры

 

0

@3D Homer

Да.

Да, если удалить верхнюю и нижнюю вершины, то останется граф не просто гомеоморфный K_3,3 (то есть являющийся подразбиением K_3,3), но и изоморфный K_3,3.

0

@Nickname2224

Подразбиение это когда мы можем добавить вершину степени на любое ребро К 3.3 ?
А как насчет операции стирания ребра я слышал,что существует такая операция, эта операция применяется к графу Петерсена, всегда ли можно и ко всем графам применять операцию стирания вершины?

0