Алгоритм двух китайцев - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:41:40Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:29, 1 сентября 2022

2022-09-01T03:29:44Z

188.170.83.4: /* Описание */

2021-03-29T06:54:01Z

‎Описание

188.170.83.4: "конденсацию графа K" -> "конденсацию графа, получившегося на шаге 1"

2021-03-29T06:53:01Z

"конденсацию графа <tex>K</tex>" -> "конденсацию графа, получившегося на шаге 1"

A guy from is: Исправление ошибки в псевдокоде

2018-04-04T23:47:01Z

Исправление ошибки в псевдокоде

37.113.155.62: /* Реализация */

2016-06-07T13:17:05Z

‎Реализация

188.162.65.14: Add link to english wiki page

2014-11-26T06:26:27Z

Add link to english wiki page

178.91.53.64: /* Реализация */

2013-08-17T02:53:26Z

‎Реализация

178.91.53.64: /* Реализация */

2013-08-17T02:33:01Z

‎Реализация

Alex z в 14:31, 17 января 2013

2013-01-17T14:31:27Z

← Предыдущая		Версия 16:41, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Алгоритм двух китайцев''' — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.		'''Алгоритм двух китайцев''' — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.

← Предыдущая		Версия 03:29, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Алгоритм двух китайцев''' — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.		'''Алгоритм двух китайцев''' — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.

@@ Строка 17: / Строка 17: @@
 # Для каждой вершины <tex>u \ne v</tex> графа <tex>G</tex> произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex>, и вычтем вес этого ребра из весов всех рёбер, входящих в <tex>u</tex>. <tex>m(u) = \min \limits_{tu \in E}w(tu), w'(tu) = w(tu) - m(u)</tex>.<br>
 # Строим граф <tex>K = (V,K_0)</tex>, где <tex>K_0</tex> — множество рёбер нулевого веса графа <tex>G</tex> c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым.<br>
-# Если такого дерева нет, то построим граф <tex>C</tex> — конденсацию графа, получившегося на шаге 1. Пусть <tex>y</tex> и <tex>z</tex> — две вершины графа <tex>C</tex>, отвечающие компонентам сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес ребра между вершинами <tex>y</tex> и <tex>z</tex> равным минимальному среди весов рёбер графа <tex>G</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>
+# Если такого дерева нет, то построим граф <tex>C</tex> — конденсацию графа <tex>K</tex>. Пусть <tex>y</tex> и <tex>z</tex> — две вершины графа <tex>C</tex>, отвечающие компонентам сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес ребра между вершинами <tex>y</tex> и <tex>z</tex> равным минимальному среди весов рёбер графа <tex>G</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>
 # Продолжим с пункта 2, используя граф <tex>C</tex> вместо <tex>G</tex>.<br>
 # В <tex>C</tex> построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в <tex>G</tex> с весовой функцией <tex>w'</tex>. Добавим к <tex>T'</tex> все вершины компоненты сильной связности графа <tex>K</tex>, которой принадлежит <tex>v</tex> (по путям нулевого веса из <tex>v</tex>). Пусть в <tex>T</tex> есть ребро <tex>yz</tex>, где <tex>y</tex> отвечает компоненте сильной связности <tex>Y</tex>, а <tex>z</tex> — компоненте сильной связности <tex>Z</tex> графа <tex>K</tex>. Между <tex>Y</tex> и <tex>Z</tex> в графе <tex>G</tex> с весовой функцией <tex>w'</tex> есть ребро <tex>y'z'</tex>, вес которого равен весу ребра <tex>yz</tex>. Добавим это ребро к дереву <tex>T'</tex>. Добавим к <tex>T'</tex> все вершины компоненты <tex>Z</tex> по путям нулевого веса из <tex>z'</tex>. Сделаем так для каждого ребра дерева <tex>T</tex>.<br>

@@ Строка 17: / Строка 17: @@
 # Для каждой вершины <tex>u \ne v</tex> графа <tex>G</tex> произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex>, и вычтем вес этого ребра из весов всех рёбер, входящих в <tex>u</tex>. <tex>m(u) = \min \limits_{tu \in E}w(tu), w'(tu) = w(tu) - m(u)</tex>.<br>
 # Строим граф <tex>K = (V,K_0)</tex>, где <tex>K_0</tex> — множество рёбер нулевого веса графа <tex>G</tex> c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым.<br>
-# Если такого дерева нет, то построим граф <tex>C</tex> — конденсацию графа <tex>K</tex>. Пусть <tex>y</tex> и <tex>z</tex> — две вершины графа <tex>C</tex>, отвечающие компонентам сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес ребра между вершинами <tex>y</tex> и <tex>z</tex> равным минимальному среди весов рёбер графа <tex>G</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>
+# Если такого дерева нет, то построим граф <tex>C</tex> — конденсацию графа, получившегося на шаге 1. Пусть <tex>y</tex> и <tex>z</tex> — две вершины графа <tex>C</tex>, отвечающие компонентам сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес ребра между вершинами <tex>y</tex> и <tex>z</tex> равным минимальному среди весов рёбер графа <tex>G</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>
 # Продолжим с пункта 2, используя граф <tex>C</tex> вместо <tex>G</tex>.<br>
 # В <tex>C</tex> построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в <tex>G</tex> с весовой функцией <tex>w'</tex>. Добавим к <tex>T'</tex> все вершины компоненты сильной связности графа <tex>K</tex>, которой принадлежит <tex>v</tex> (по путям нулевого веса из <tex>v</tex>). Пусть в <tex>T</tex> есть ребро <tex>yz</tex>, где <tex>y</tex> отвечает компоненте сильной связности <tex>Y</tex>, а <tex>z</tex> — компоненте сильной связности <tex>Z</tex> графа <tex>K</tex>. Между <tex>Y</tex> и <tex>Z</tex> в графе <tex>G</tex> с весовой функцией <tex>w'</tex> есть ребро <tex>y'z'</tex>, вес которого равен весу ребра <tex>yz</tex>. Добавим это ребро к дереву <tex>T'</tex>. Добавим к <tex>T'</tex> все вершины компоненты <tex>Z</tex> по путям нулевого веса из <tex>z'</tex>. Сделаем так для каждого ребра дерева <tex>T</tex>.<br>

@@ Строка 104: / Строка 104: @@
      for each <tex>e \in</tex> edges
          if e.to и e.from в разных компонентах
-             добавляем в newEdges ребро с концами в данных компонентах и весом e.w
+             добавляем в newEdges ребро с концами в данных компонентах и весом e.w - minEdge[e.to]
      res += findMST(newEdges, ComponentsCount, newComponents[root])
      return res

@@ Строка 89: / Строка 89: @@
      int res = 0
      int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью.
-     for each <tex>e \in E</tex>
+     for each <tex>e \in </tex> edges
          minEdge[e.to] = min(e.w, minEdge[e.to])
      for each <tex>v \in V \backslash \{root\}</tex>
          res += minEdge[v] //веса минимальных ребер точно будут в результате
      edge zeroEdges[] //создаем массив нулевых ребер
-     for each <tex>e \in E</tex>
+     for each <tex>e \in </tex> edges
          if e.w == minEdge[e.to]
              zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to

@@ Строка 117: / Строка 117: @@
 ==См. также==
 * [[Алгоритм Борувки]]
 * [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/shortest-tree-chinese-2003 Визуализатор алгоритма]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Остовные деревья ]]

@@ Строка 102: / Строка 102: @@
      newComponents = Сondensation(zeroEdges)
      edge newEdges[] //создаем массив ребер в новом графе с вершинами в полученных компонентах
-     for each <tex>e \in</tex> zeroEdges
+     for each <tex>e \in</tex> edges
          if e.to и e.from в разных компонентах
              добавляем в newEdges ребро с концами в данных компонентах и весом e.w

@@ Строка 26: / Строка 26: @@
 === Пример ===
-{|width="70%" align="center"
+{| class = "wikitable" width="70%"
 |-
 |Исходный граф.
@@ Строка 113: / Строка 115: @@
 * [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Остовные деревья ]]