Гамильтонов путь. Решение/Гилязев Руслан - История изменений

StasFomin: Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]]

2020-05-20T20:50:04Z

Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]]

StasFomin в 18:14, 3 июня 2015

2015-06-03T18:14:17Z

StasFomin в 18:09, 3 июня 2015

2015-06-03T18:09:49Z

Ruslan1 в 15:36, 3 июня 2015

2015-06-03T15:36:19Z

Ruslan1 в 13:18, 24 мая 2015

2015-05-24T13:18:27Z

Ruslan1: Новая страница: « Выберем произвольное ребро. Получим путь длины 1. Покажем как можно увеличить путь на 1. П…»

2015-05-24T13:15:51Z

Новая страница: « Выберем произвольное ребро. Получим путь длины 1. Покажем как можно увеличить путь на 1. П…»

Новая страница

Выберем произвольное ребро. Получим путь длины 1. Покажем как можно увеличить путь на 1. Пусть у нас имеется путь T длины k < n. Пусть последняя вершина пути "b", а первая - "a". Возьмем любую вершину "c" не входящую в T. Если есть ребро (b -> c) или ребро (c -> a), то мы сможем увеличить путь. Если нет, то есть ребра (с -> b) и (a -> c). Тогда переберем все вершины из T. Очевидно, что найдется пара соседних вершин пути "u" и "v" (u - > v) такие, что есть ребра (u -> c) и (с -> v), тогда заменим (u -> v) этими ребрами. Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n^2).

[[Категория:Предложенные студентами задачи]]

← Предыдущая		Версия 20:50, 20 мая 2020
Строка 34:		Строка 34:
	Где гамильтонов граф?		Где гамильтонов граф?

−	[[Category:~~Проблемы в решении~~]]	+	[[Category:Уже не исправить]]

← Предыдущая		Версия 18:14, 3 июня 2015
Строка 12:		Строка 12:
	Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n²).		Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n²).

−	[[~~Категория~~:~~Предложенные студентами задачи~~]]	+	----
		+	[[Участник:StasFomin\|StasFomin]] ([[Обсуждение участника:StasFomin\|обсуждение]]) 21:14, 3 июня 2015 (MSK):
		+	Вот полный граф, без петель
		+
		+	<graph>
		+	graph G{
		+	A--B--C--A
		+	}
		+	</graph>
		+
		+
		+	Вот случайная ориентация
		+
		+	<graph>
		+	digraph G{
		+	A->B->C
		+	A->C
		+	}
		+	</graph>
		+
		+	Где гамильтонов граф?
		+
		+	[[Category:Проблемы в решении]]

← Предыдущая		Версия 18:09, 3 июня 2015
Строка 1:		Строка 1:
		+	Выберем произвольное ребро. Получим путь длины 1.

−	~~Выберем произвольное ребро. Получим путь длины 1.~~ Покажем как можно увеличить путь на 1. Пусть у нас имеется путь T из k < n вершин. Пусть последняя вершина пути ~~"b"~~, а ~~первая - "a"~~. Возьмем любую вершину ~~"c"~~ не входящую в T. Если есть ребро (b -> c) или ребро (c -> a), то мы сможем увеличить путь. Если нет, то есть ребра (с -> b) и (a -> c). Тогда переберем все вершины из T. Очевидно, что найдется пара соседних вершин пути ~~"u"~~ и ~~"v"~~ (~~u -~~ > v) такие, что есть ребра (u -> c) и (с -> v), тогда заменим (u -> v) этими ребрами. Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(~~n^2~~).	+	Покажем как можно увеличить путь на 1.
		+
		+	Пусть у нас имеется путь T из k < n вершин. Пусть последняя вершина пути «b», а первая — «a». Возьмем любую вершину «c» не входящую в T.
		+	* Если есть ребро (b -> c) или ребро (c -> a), то мы сможем увеличить путь.
		+	* Если нет, то есть ребра (с -> b) и (a -> c).
		+	Тогда переберем все вершины из T.
		+
		+	Очевидно, что найдется пара соседних вершин пути «u» и «v» (u — > v) такие, что есть ребра (u -> c) и (с -> v), тогда заменим (u -> v) этими ребрами.
		+
		+	Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n²).

	[[Категория:Предложенные студентами задачи]]		[[Категория:Предложенные студентами задачи]]

← Предыдущая		Версия 15:36, 3 июня 2015
Строка 1:		Строка 1:

−	Выберем произвольное ребро. Получим путь длины 1. Покажем как можно увеличить путь на 1. Пусть у нас имеется путь из k < n вершин. Пусть последняя вершина пути "b", а первая - "a". Возьмем любую вершину "c" не входящую в T. Если есть ребро (b -> c) или ребро (c -> a), то мы сможем увеличить путь. Если нет, то есть ребра (с -> b) и (a -> c). Тогда переберем все вершины из T. Очевидно, что найдется пара соседних вершин пути "u" и "v" (u - > v) такие, что есть ребра (u -> c) и (с -> v), тогда заменим (u -> v) этими ребрами. Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n^2).	+	Выберем произвольное ребро. Получим путь длины 1. Покажем как можно увеличить путь на 1. Пусть у нас имеется путь T из k < n вершин. Пусть последняя вершина пути "b", а первая - "a". Возьмем любую вершину "c" не входящую в T. Если есть ребро (b -> c) или ребро (c -> a), то мы сможем увеличить путь. Если нет, то есть ребра (с -> b) и (a -> c). Тогда переберем все вершины из T. Очевидно, что найдется пара соседних вершин пути "u" и "v" (u - > v) такие, что есть ребра (u -> c) и (с -> v), тогда заменим (u -> v) этими ребрами. Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n^2).

	[[Категория:Предложенные студентами задачи]]		[[Категория:Предложенные студентами задачи]]

← Предыдущая		Версия 13:18, 24 мая 2015
Строка 1:		Строка 1:

−	Выберем произвольное ребро. Получим путь длины 1. Покажем как можно увеличить путь на 1. Пусть у нас имеется путь ~~T длины~~ k < n. Пусть последняя вершина пути "b", а первая - "a". Возьмем любую вершину "c" не входящую в T. Если есть ребро (b -> c) или ребро (c -> a), то мы сможем увеличить путь. Если нет, то есть ребра (с -> b) и (a -> c). Тогда переберем все вершины из T. Очевидно, что найдется пара соседних вершин пути "u" и "v" (u - > v) такие, что есть ребра (u -> c) и (с -> v), тогда заменим (u -> v) этими ребрами. Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n^2).	+	Выберем произвольное ребро. Получим путь длины 1. Покажем как можно увеличить путь на 1. Пусть у нас имеется путь из k < n вершин. Пусть последняя вершина пути "b", а первая - "a". Возьмем любую вершину "c" не входящую в T. Если есть ребро (b -> c) или ребро (c -> a), то мы сможем увеличить путь. Если нет, то есть ребра (с -> b) и (a -> c). Тогда переберем все вершины из T. Очевидно, что найдется пара соседних вершин пути "u" и "v" (u - > v) такие, что есть ребра (u -> c) и (с -> v), тогда заменим (u -> v) этими ребрами. Итак, мы увеличили путь. Таким образом построим гамильтонов путь. Алгоритм работает за O(n^2).

	[[Категория:Предложенные студентами задачи]]		[[Категория:Предложенные студентами задачи]]