Список заданий по АСД

Материал из Викиконспекты
Версия от 16:07, 5 сентября 2013; 194.85.160.133 (обсуждение) (Новая страница: «<wikitex> = Дискретная математика, алгоритмы и структуры данных, 3 семестр = Некоторые задани...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 3 семестр

Некоторые задания можно найти в книге Харари, Теория графов

  1. Доказать, что если из $u$ достижима $v$, то существует простой путь из $u$ в $v$.
  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

</wikitex>