Изменения
Новая страница: «<wikitex> # Доказать, что если в ориентированном графе существует цикл, то в нем существует и ...»
<wikitex>
# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
# Будем называть ''согласованным циклом'' в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.
# Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
# Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
# Харари 2.3
# Харари 2.5
# Харари 2.9
# Харари 2.13
# Харари 2.15
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Харари 2.16
# Харари 2.20
# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
# Будем называть ''согласованным циклом'' в графе класс эквивалентности циклических путей относительно циклического сдвига. При этом циклический путь не должен проходить два раза по одному ребру в разных направлениях. Докажите, что в графе есть согласованный цикл тогда и только тогда когда там есть цикл.
# Петя придумал отношение средней связности: $u$ средне связана с $v$, если из $u$ достижима $v$ или из $v$ достижима $u$. Является ли это отношение отношением эквивалентности?
# Пусть граф $G$ - объединение двух различных простых путей из $u$ в $v$. Докажите, что в $G$ есть цикл.
# Харари 2.3
# Харари 2.5
# Харари 2.9
# Харари 2.13
# Харари 2.15
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Харари 2.16
# Харари 2.20
