Изменения
Новая страница: «<wikitex> = Дискретная математика, алгоритмы и структуры данных, 3 семестр = Некоторые задани...»
<wikitex>
= Дискретная математика, алгоритмы и структуры данных, 3 семестр =
Некоторые задания можно найти в книге [http://www.ozon.ru/context/detail/id/4452506/ Харари, Теория графов]
# Доказать, что если из $u$ достижима $v$, то существует простой путь из $u$ в $v$.
# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
# Петя придумал отношение средней связности: $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
</wikitex>
= Дискретная математика, алгоритмы и структуры данных, 3 семестр =
Некоторые задания можно найти в книге [http://www.ozon.ru/context/detail/id/4452506/ Харари, Теория графов]
# Доказать, что если из $u$ достижима $v$, то существует простой путь из $u$ в $v$.
# Доказать, что если в ориентированном графе существует цикл, то в нем существует и простой цикл.
# Доказать, что если в неориентированным графе существует цикл, то в нем существует и простой цикл.
# Петя придумал отношение средней связности: $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
</wikitex>
