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

Материал из Викиконспекты
Перейти к: навигация, поиск

<wikitex>

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

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

  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

</wikitex>