No.6456
![[1978] Кристофидес - Теория графов. Алгоритмический подход.Pdf](/thumb/pdf/0912/126201432582033s.jpg)
Подумалось, что самый сложный и интересный курс за время моего обучения в университете наверное заслуживает отдельной ветки.
Думать - это хорошо и полезно, так что присоединяемся. Спрашивайте свои ответы, буду отвечать на них по мере компетентности.
Пара простых задач для затравки:
1) Доказать, что в любом графе найдутся две вершины равной степени.
2) Доказать, что у двудольного регулярного графа доли равномощны.
Пара задач, относительно решения которых я до сих пор нахожусь в глубоких непонятках:
3) Граф G 2-связен и для любых двух несмежных вершин u и v граф G-u-v несвязен. Доказать, что граф G является простым циклом.
4) Найти граф G - 2-рёберно-связный, для которого граф G^2 - негамильтонов.
5) Доказать, что граф эйлеров тогда и только тогда, когда любой его блок эйлеров.
блок есть максимальная по включению 2-связная компонента, граф G^2 - граф с тем же множеством вершин, у которого две вершины соединены ребром тогда и только тогда, когда в графе G они соединены некоторой простой цепью длины не более двух.
