2014 dxdy logo

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

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




 
 Разбиение кубического графа на два остовных подграфа...
Сообщение27.02.2025, 23:26 
Аватара пользователя
... без изолированных вершин.

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

Пытался решить, подвешивая граф за вершину. Но тут не видно ничего. Ещё задал эту задачу ДипСику.

Сначала он сказал, что рёбра любого графа можно ориентировать так, чтобы входящая и исходящая степени любой вершины отличались не более, чем на 1. Тогда покрасим все входящие в 1 цвет, а исходящие во 2 цвет :P

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

Но оказалось, что в кубических графах всё же бывают мосты, и бывают кубические графы, в которых нет совершенного парасочетания :-(

 
 
 
 Re: Разбиение кубического графа на два остовных подграфа...
Сообщение27.02.2025, 23:47 
Это легко следует из теоремы Визинга (рёбра можно раскрасить в $4$ цвета так, что рёбра одного цвета не имеют общих концов).

 
 
 
 Re: Разбиение кубического графа на два остовных подграфа...
Сообщение01.03.2025, 14:15 
Аватара пользователя
Да, действительно. Спасибо.

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


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