2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Грани и рёбра в графе
Сообщение18.09.2016, 20:42 
Аватара пользователя
Во всех найденных доказательствах непланарности $K_{3,3}$ используется то, что любая грань ограничена не менее чем четырьмя рёбрами. Почему так? Ведь при взгляде на рисунок сразу видны и треугольные грани, ограниченные лишь тремя отрезками рёбер.
Изображение

 
 
 
 Re: Грани и рёбра в графе
Сообщение18.09.2016, 21:16 
Если бы эту штуку можно было нарисовать на плоскости без пересечений рёбер -- вот тогда была бы
Hasek в сообщении #1152405 писал(а):
любая грань ограничена не менее чем четырьмя рёбрами
-- потому что рёбра, которые ограничивают грань, образуют цикл.

 
 
 
 Re: Грани и рёбра в графе
Сообщение18.09.2016, 22:11 
Аватара пользователя
Благодарю, понял. Зря я пытался осознать это на заведомо неподходящей картинке (ведь граф предполагается планарным в доказательстве от противного).

 
 
 
 Re: Грани и рёбра в графе
Сообщение18.09.2016, 22:15 
Аватара пользователя
Hasek в сообщении #1152405 писал(а):
Ведь при взгляде на рисунок сразу видны и треугольные грани, ограниченные лишь тремя отрезками рёбер.
«Отрезками» не считается. Настоящая треугольная грань имела бы рёбра, соединяющие вершины одного цвета, чего в данном графе нет.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group