ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

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

   Решение

Задачи

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 52]      



Задача 30780  (#002)

Тема:   [ Степень вершины ]
Сложность: 2
Классы: 6,7

Докажите, что не существует графа без петель и кратных рёбер с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.

Прислать комментарий     Решение

Задача 30781  (#003)

Темы:   [ Степень вершины ]
[ Примеры и контрпримеры. Конструкции ]
[ Индукция (прочее) ]
Сложность: 3+
Классы: 7,8

Докажите, что существует граф с 2n вершинами, степени которых равны 1, 1, 2, 2, ..., n, n.

Прислать комментарий     Решение

Задача 30782  (#004)

Темы:   [ Степень вершины ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3
Классы: 7,8

Верно ли, что два графа изоморфны, если
  а) у них по 10 вершин, степень каждой из которых равна 9?
  б) у них по 8 вершин, степень каждой из которых равна 3?
  в) они связны, без циклов и содержат по 6 рёбер?

Прислать комментарий     Решение

Задача 30783  (#005)

Темы:   [ Связность и разложение на связные компоненты ]
[ Четность и нечетность ]
[ Доказательство от противного ]
Сложность: 4-
Классы: 7,8,9

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

Прислать комментарий     Решение

Задача 30784  (#006)

Тема:   [ Деревья ]
Сложность: 2+
Классы: 7,8

Докажите, что граф, в котором каждые две вершины соединены ровно одним простым путем, является деревом.

Прислать комментарий     Решение

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 52]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .