Версия для печати
Убрать все задачи

---

Доказать, что
  а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
  б) в дереве с n вершинами ровно  n – 1  ребро;
  в) в дереве не меньше двух висячих вершин;
  г) в связном графа из n вершин не меньше  n – 1  ребра;
  д) если в связном графе n вершин и  n – 1  ребро, то он – дерево.

   Решение

Страница: << 39 40 41 42 43 44 45 >> [Всего задач: 383]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 21995

Темы:   [ Принцип Дирихле (прочее) ] [ Теория графов (прочее) ]

Сложность: 3 Классы: 6,7,8

Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.

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

Решение

---

Задача 31079

Темы:   [ Степень вершины ] [ Обход графов ] [ Процессы и операции ]

Сложность: 3 Классы: 6,7,8

Есть 20 карточек, у каждой из которых на двух сторонах написано по числу. При этом все числа от 1 до 20 написаны по два раза.
Доказать, что карточки можно разложить так, чтобы все числа сверху были различны.

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

Решение

---

Задача 31098

Темы:   [ Связность и разложение на связные компоненты ] [ Деревья ]

Сложность: 3 Классы: 6,7,8

Доказать, что
  а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
  б) в дереве с n вершинами ровно  n – 1  ребро;
  в) в дереве не меньше двух висячих вершин;
  г) в связном графа из n вершин не меньше  n – 1  ребра;
  д) если в связном графе n вершин и  n – 1  ребро, то он – дерево.

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

Решение

---

Задача 31354

Темы:   [ Связность и разложение на связные компоненты ] [ Ориентированные графы ]

Сложность: 3 Классы: 5,6,7,8

Лифт в 100-этажном доме имеет 2 кнопки: "+7" и "–9" (первая поднимает лифт на 7 этажей, вторая опускает на 9).Можно ли проехать:
  a) с 1-го на 2-й;
  б) со 2-го на 1-й;
  в) с любого на любой этаж?

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

Решение

---

Задача 32006

Темы:   [ Подсчет двумя способами ] [ Степень вершины ] [ Куб ] [ Доказательство от противного ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3 Классы: 7,8,9

а) Можно ли занумеровать рёбра куба натуральными числами от 1 до 12 так, чтобы для каждой вершины куба сумма номеров рёбер, которые в ней сходятся, была одинаковой?

б) Аналогичный вопрос, если расставлять по рёбрам куба числа –6, –5, –4, –3, –2, –1, 1, 2, 3, 4, 5, 6.

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

Решение

---

Страница: << 39 40 41 42 43 44 45 >> [Всего задач: 383]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями