Список заданий по ДМ 2к 2016 осень

Материал из Викиконспекты
Версия от 16:16, 11 сентября 2016; 77.234.215.133 (обсуждение) (Новая страница: «<wikitex> # Доказать, что если в ориентированном графе существует цикл, то в нем существует и ...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

<wikitex>

  1. Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
  2. Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
  3. Будем называть согласованным циклом в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.
  4. Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
  5. Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
  6. Харари 2.3
  7. Харари 2.5
  8. Харари 2.9
  9. Харари 2.13
  10. Харари 2.15
  11. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
  12. Харари 2.16
  13. Харари 2.20
  14. Харари 2.22

</wikitex>