Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Задачи и упражнения

  • 1. Докажите, что однородный граф третьей степени содержит цикл.
  • 2. В некотором государстве 201 город, некоторые из которых соединены дорогами гак, что любые два города соединяет ровно один путь. Сколько дорог в государстве?
  • 3. Волейбольная сетка имеет вид прямоугольника размером 50x600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?
  • 4. Какое наибольшее количество ребер можно удалить из полного графа с п вершинами, чтобы он остался связным?
  • 5. В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый.
  • 6. Докажите, что у любого связного графа, имеющего не менее двух вершин, существует связный подграф.
  • 7. Докажите, что среди 7 деревьев, каждое из которых имеет 6 вершин, есть два изоморфных.
  • 8. Докажите, что любое дерево, имеющее не менее двух вершин, содержит, как минимум, две висячие вершины.
  • 9. Постройте все различные (не изоморфные) деревья с восемью вершинами.
  • 10. Докажите, что любое дерево (с более чем двумя вершинами) можно рассматривать как двудольный граф. Какие деревья являются полными двудольными графами?
 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы