Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Плоского графа и его минимального остовного дерева. На каждом ребре указан его вес, который здесь примерно пропорционален его длине.

Минимального связующего дерева ( МСТ ) или минимальный вес покрывающего дерева представляет собой подмножество ребер , подключенного , ребра-взвешенный неориентированный граф , который соединяет все вершины вместе, без каких - либо циклов и с минимальным возможным общий вес края. То есть это остовное дерево , сумма весов ребер которого минимальна. В более общем смысле, любой неориентированный граф, взвешенный по ребрам (не обязательно связный), имеет минимальный остовный лес , который представляет собой объединение минимальных остовных деревьев для его связных компонентов .

Существует довольно много вариантов использования минимальных остовных деревьев. Одним из примеров может быть телекоммуникационная компания, пытающаяся проложить кабель в новом районе. Если ограничено прокладывать кабель только вдоль определенных путей (например, дорог), тогда будет граф, содержащий точки (например, дома), соединенные этими путями. Некоторые из путей могут быть более дорогими, потому что они длиннее или требуют более глубокого прокладки кабеля; эти пути будут представлены ребрами с большим весом. Валюта является приемлемой единицей измерения веса ребра - длина ребер не обязана подчиняться обычным правилам геометрии, таким как неравенство треугольника . Остовпоскольку этот граф был бы подмножеством тех путей, которые не имеют циклов, но все же соединяют каждый дом; возможно несколько остовных деревьев. Минимальное покрывающее дерево будет один с самой низкой общей стоимостью, что составляет наименее затратный путь для прокладки кабеля.

Свойства [ править ]

Возможная кратность [ править ]

Если в графе n вершин, то каждое остовное дерево имеет n - 1 ребро.

Этот рисунок показывает, что в графе может быть более одного минимального остовного дерева. На рисунке два дерева под графом представляют собой две возможности минимального остовного дерева данного графа.

Может быть несколько минимальных остовных деревьев одинакового веса; в частности, если все веса ребер данного графа одинаковы, то каждое остовное дерево этого графа является минимальным.

Уникальность [ править ]

Если каждое ребро имеет отдельный вес, тогда будет только одно уникальное минимальное остовное дерево . Это верно во многих реальных ситуациях, таких , как , например телекоммуникационной компании выше, где это вряд ли какие - либо два пути имеют точно такую же стоимость. Это также распространяется на покрывающие леса.

Доказательство:

  1. Предположим противное , что существует два разных MSTS A и B .
  2. Поскольку A и B различаются, несмотря на то, что они содержат одинаковые узлы, есть по крайней мере одно ребро, принадлежащее одному, но не другому. Пусть среди таких ребер e 1 имеет наименьший вес; этот выбор уникален, потому что веса ребер различны. Не ограничивая общности, предположим , е 1 в А .
  3. Поскольку B является MST, { e 1 } B должен содержать цикл C с e 1 .
  4. Как дерево, не содержит циклов, следовательно , С должен иметь ребро е 2 , которое не находится в A .
  5. Поскольку e 1 было выбрано как единственное ребро с наименьшим весом среди ребер, принадлежащих ровно одному из A и B , вес e 2 должен быть больше веса e 1 .
  6. Поскольку e 1 и e 2 являются частью цикла C, замена e 2 на e 1 в B, таким образом, дает остовное дерево с меньшим весом.
  7. Это противоречит предположению, что B - MST.

В более общем плане, если веса ребер не все различны, то только (мульти) набор весов в минимальных остовных деревьях обязательно будет уникальным; это то же самое для всех минимальных остовных деревьев. [1]

Подграф минимальной стоимости [ править ]

Если веса положительные , то минимальное остовное дерево на самом деле является подграфом с минимальной стоимостью, соединяющим все вершины, поскольку подграфы, содержащие циклы, обязательно имеют больший общий вес. [ необходима цитата ]

Свойство цикла [ править ]

Для любого цикла C на графике, если вес краевых е из С больше , чем отдельные весами всех других ребер C , то этот край не может принадлежать к MST.

Доказательство. Предположим противное , т. Е. Что e принадлежит MST T 1 . Затем удаление e разбивает T 1 на два поддерева, причем два конца e находятся в разных поддеревьях. Остальная часть C воссоединяется поддеревьев, следовательно , существует ребро е из С с концами в различных поддеревьев, то есть, он воссоединяется поддеревьев в дерево T 2 с весом меньше , чем T 1 , так как вес F меньше вес е .

Вырезать свойство [ править ]

На этом рисунке показано свойство сокращения MST. T - единственный MST данного графа. Если S = ​​{A, B, D, E}, таким образом, VS = {C, F}, тогда есть 3 возможности ребра через разрез (S, VS), это ребра BC, EC, EF оригинала. график. Тогда e - одно из ребер с минимальным весом для разреза, поэтому S ∪ {e} является частью MST T.

Для любого разреза C графа, если вес ребра e в разрезе C строго меньше, чем веса всех других ребер разреза C графа, то это ребро принадлежит всем MST графа .

Доказательство. Предположим, что существует MST T , не содержащее e . Добавление e к T даст цикл, который пересекает разрез один раз в точке e и возвращается обратно на другом крае e ' . Удаление е « мы получаем остовного дерева T ∖ {е»} ∪ {е} строго меньшего веса , чем Т . Это противоречит предположению, что T был MST.

По аналогичному аргументу, если более чем одно ребро имеет минимальный вес на разрезе, то каждое такое ребро содержится в некотором минимальном остовном дереве.

Преимущество минимальной стоимости [ править ]

Если ребро e с минимальной стоимостью графа уникально, то это ребро входит в любой MST.

Доказательство: если e не был включен в MST, удаление любого из ребер (большей стоимости) в цикле, образованном после добавления e к MST, дало бы остовное дерево меньшего веса.

Сокращение [ править ]

Если T - дерево ребер MST, то мы можем сжать T в одну вершину, сохраняя при этом инвариант, что MST сжатого графа плюс T дает MST для графа до сжатия. [2]

Алгоритмы [ править ]

Во всех приведенных ниже алгоритмах m - количество ребер в графе, а n - количество вершин.

Классические алгоритмы [ править ]

Первый алгоритм поиска минимального остовного дерева был разработан чешским ученым Отакаром Борувкой в 1926 году (см . Алгоритм Борувки ). Его целью было эффективное электрическое покрытие Моравии . Алгоритм работает в последовательности этапов. На каждом этапе, называемом этапом Борувки , он определяет лес F, состоящий из ребра минимального веса, инцидентного каждой вершине в графе G , а затем формирует граф в качестве входных данных для следующего шага. Здесь обозначает граф, полученный из G стягиванием ребер в F ( свойством Cut, эти ребра принадлежат MST). Каждый шаг Борувки занимает линейное время. Так как количество вершин уменьшается как минимум наполовину на каждом шаге, алгоритм Борувки занимает время O ( m log n ). [2]

Второй алгоритм - это алгоритм Прима , который был изобретен Войтехом Ярником в 1930 году и повторно открыт Примом в 1957 году и Дейкстрой в 1959 году. По сути, он увеличивает MST ( T ) по одному ребру за раз. Изначально T содержит произвольную вершину. На каждом шаге Т увеличивается с наименее веса ребра ( х , у ) , такие , что х находится в Т и у еще не в T . По свойству Cut все ребра, добавленные к T, находятся в MST. Его время выполнения - O ( m logn ) или O ( m + n log n ), в зависимости от используемых структур данных.

Третий широко используемый алгоритм - это алгоритм Крускала , который также занимает время O ( m log n ).

Четвертый алгоритм, который не так широко используется, - это алгоритм обратного удаления , который является обратным алгоритму Крускала. Его время выполнения - O ( m log n (log log n ) 3 ).

Все четыре алгоритма - жадные . Так как они работают в полиномиальное время, задача нахождения таких деревьев в FP , и связанные с ними проблемы , решения , такие как определение , является ли определенный край в MST или определения , если вес минимальный общий превышает определенное значение в P .

Более быстрые алгоритмы [ править ]

Несколько исследователей пытались найти алгоритмы, более эффективные в вычислительном отношении.

В модели сравнения, в которой единственными разрешенными операциями с весами ребер являются попарные сравнения, Karger, Klein & Tarjan (1995) нашли рандомизированный алгоритм с линейным временем, основанный на комбинации алгоритма Борувки и алгоритма обратного удаления. [3] [4]

Самый быстрый алгоритм на основе нерандомизированного сравнения с известной сложностью, созданный Бернаром Шазеллем , основан на мягкой куче - очереди с приблизительным приоритетом. [5] [6] Его время работы составляет O ( m  α ( m , n )), где α - классический функциональный обратный к функции Аккермана . Функция α растет чрезвычайно медленно, так что для всех практических целей ее можно считать константой, не превышающей 4; таким образом, алгоритм Шазеля требует времени, очень близкого к линейному.

Алгоритмы линейного времени в особых случаях [ править ]

Плотные графики [ править ]

Если граф плотный (то есть m / n ≥ log log log n ), то детерминированный алгоритм Фредмана и Тарьяна находит MST за время O ( m ). [7] Алгоритм выполняет несколько этапов. На каждой фазе алгоритм Прима выполняется много раз, каждый для ограниченного числа шагов. Время выполнения каждой фазы составляет O ( m + n ). Если количество вершин перед фазой равно , то количество вершин, оставшихся после фазы, не больше . Следовательно, требуется максимум этапов, что дает линейное время выполнения для плотных графов. [2]

Есть и другие алгоритмы, которые работают в линейное время на плотных графах. [5] [8]

Целочисленные веса [ править ]

Если веса ребер представляют собой целые числа, представленные в двоичном формате, то известны детерминированные алгоритмы, которые решают проблему за O ( m  +  n ) целочисленных операций. [9] Можно ли решить проблему детерминированно для общего графа за линейное время с помощью алгоритма, основанного на сравнении, остается открытым вопросом.

Деревья решений [ править ]

Для данного графа G, где узлы и ребра фиксированы, но веса неизвестны, можно построить двоичное дерево решений (DT) для вычисления MST для любой перестановки весов. Каждый внутренний узел DT содержит сравнение двух ребер, например: «Является ли вес ребра между x и y большим, чем вес ребра между w и z ?». Двум дочерним узлам соответствуют два возможных ответа «да» или «нет». В каждом листе DT есть список ребер из Gкоторые соответствуют MST. Сложность выполнения DT - это наибольшее количество запросов, необходимых для поиска MST, что составляет всего лишь глубину DT. ДТ для графа G называется оптимальным , если он имеет наименьшую глубину всех правильных DTs для G .

Для любого целого числа r можно найти оптимальные деревья решений для всех графов на r вершинах методом перебора . Этот поиск выполняется в два этапа.

A. Создание всех потенциальных DT

  • На r вершинах есть разные графы .
  • Для каждого графа MST всегда можно найти с помощью сравнений r ( r -1), например, с помощью алгоритма Прима .
  • Следовательно, глубина оптимального DT меньше .
  • Следовательно, количество внутренних узлов в оптимальном DT меньше, чем .
  • Каждый внутренний узел сравнивает два ребра. Количество ребер не больше, поэтому разное количество сравнений не больше .
  • Таким образом, число потенциальных DTs меньше: .

B. Определение правильных ОУ Чтобы проверить правильность ОУ , его следует проверить на всех возможных перестановках весов ребер.

  • Количество таких перестановок не больше .
  • Для каждой перестановки решите задачу MST на данном графе, используя любой существующий алгоритм, и сравните результат с ответом, данным DT.
  • Время работы любого алгоритма MST не больше , поэтому общее время, необходимое для проверки всех перестановок, не больше .

Таким образом, общее время , необходимое для нахождения оптимального DT для всех графов с г вершинами: , что меньше , чем: . [2]

См. Также: Модель дерева решений

Оптимальный алгоритм [ править ]

Сет Петти и Виджая Рамачандран нашли доказуемо оптимальный детерминированный алгоритм минимального остовного дерева, основанный на сравнении. [2] Ниже приводится упрощенное описание алгоритма.

  1. Пусть , где n - количество вершин. Найдите все оптимальные деревья решений на r вершинах. Это можно сделать за время O ( n ) (см. Деревья решений выше).
  2. Разбейте граф на компоненты с не более чем r вершинами в каждом компоненте. Этот раздел использует мягкую кучу , которая «портит» небольшое количество ребер графа.
  3. Используйте оптимальные деревья решений, чтобы найти MST для неповрежденного подграфа в каждом компоненте.
  4. Сожмите каждую компоненту связности, охватываемую MST, с одной вершиной и примените любой алгоритм, который работает на плотных графах за время O ( m ), к сжатию неповрежденного подграфа
  5. Добавьте обратно поврежденные ребра в результирующий лес, чтобы сформировать подграф, который гарантированно содержит минимальное остовное дерево и на постоянный коэффициент меньше исходного графа. Рекурсивно примените оптимальный алгоритм к этому графу.

Время выполнения всех шагов в алгоритме - O ( m ), за исключением шага использования деревьев решений . Время выполнения этого шага неизвестно, но было доказано, что он оптимален - ни один алгоритм не может работать лучше, чем оптимальное дерево решений. Таким образом, этот алгоритм обладает тем особенным свойством, что он является доказуемо оптимальным, хотя сложность его выполнения неизвестна .

Параллельные и распределенные алгоритмы [ править ]

Дополнительная информация: Параллельные алгоритмы для минимальных остовных деревьев

Исследователи также рассмотрели параллельные алгоритмы для задачи минимального остовного дерева. При линейном количестве процессоров можно вовремя решить проблему . [10] [11] Бадер и Конг (2006) демонстрируют алгоритм, который может вычислять MST в 5 раз быстрее на 8 процессорах, чем оптимизированный последовательный алгоритм. [12]

Другие специализированные алгоритмы были разработаны для вычисления минимальных остовных деревьев графа, настолько большого, что большая его часть должна постоянно храниться на диске. Эти алгоритмы внешнего хранилища , например, описанные в статье «Разработка алгоритма минимального связующего дерева внешней памяти» Романа, Дементьева и др. [13], могут работать, по утверждениям авторов, всего в 2-5 раз медленнее, чем традиционные алгоритм в памяти. Они полагаются на эффективные алгоритмы сортировки внешнего хранилища и методы сжатия графа для эффективного уменьшения размера графа.

К проблеме также можно подойти распределенным образом . Если каждый узел считается компьютером и ни один узел не знает ничего, кроме своих собственных подключенных связей, можно все же вычислить распределенное минимальное связующее дерево .

MST на полных графиках [ править ]

Алан М. Фриз показал, что для полного графа на n вершинах с весами ребер, которые являются независимыми одинаково распределенными случайными величинами с удовлетворяющей функцией распределения , тогда, когда n приближается к + ∞, ожидаемый вес приближается к MST , где - дзета-функция Римана ( точнее - постоянная Апери ). Фриз и Стил также доказали сходимость по вероятности. Сванте Янсон доказал центральную предельную теорему для веса MST.

Для равномерных случайных весов в точный ожидаемый размер минимального остовного дерева был вычислен для небольших полных графов. [14]

ВершиныОжидаемый размерПримерный ожидаемый размер
21/20,5
33/40,75
431/350,8857143
5893/9240,9664502
6278/2731.0183151
730739/291721,053716
8199462271/1848483781.0790588
9126510063932/1152288530251.0979027

Приложения [ править ]

Минимальные остовные деревья имеют прямое применение при проектировании сетей, включая компьютерные сети , телекоммуникационные сети , транспортные сети , сети водоснабжения и электрические сети (для чего они были впервые изобретены, как упоминалось выше). [15] Они вызываются в виде подпрограмм в алгоритмах для других задач, в том числе алгоритма Христофидес для аппроксимации задачи коммивояжера , [16] аппроксимирующего многотерминальной проблему минимального разреза (что эквивалентно в одном-концевом случае к потоку максимального проблема ), [17]и аппроксимация взвешенного идеального соответствия с минимальной стоимостью . [18]

Другие практические приложения, основанные на минимальных остовных деревьях, включают:

  • Таксономия . [19]
  • Кластерный анализ : точки кластеризации на плоскости, [20] одинарная кластеризация (метод иерархической кластеризации ), [21] теоретико-графовая кластеризация, [22] и кластеризация данных экспрессии генов . [23]
  • Построение деревьев для вещания в компьютерных сетях. [24]
  • Регистрация изображений [25] и сегментация [26] - см. Минимальную сегментацию на основе связующего дерева .
  • Выделение криволинейных признаков в компьютерном зрении . [27]
  • Распознавание почерка математических выражений. [28]
  • Схема схемы : реализация эффективного многократного умножения констант, как в фильтрах с конечной импульсной характеристикой . [29]
  • Районирование социально-географических территорий, группировка территорий в однородные, смежные регионы. [30]
  • Сравнение данных экотоксикологии . [31]
  • Топологическая наблюдаемость в энергосистемах. [32]
  • Измерение однородности двумерных материалов. [33]
  • Минимаксный контроль процесса . [34]
  • Минимальные остовные деревья также можно использовать для описания финансовых рынков. [35] [36] Корреляционная матрица может быть создана путем вычисления коэффициента корреляции между любыми двумя акциями. Эта матрица может быть представлена ​​топологически как сложная сеть, и минимальное остовное дерево может быть построено для визуализации взаимосвязей.

Связанные проблемы [ править ]

Минимальные деревья Штейнера вершин правильных многоугольников с N = от 3 до 8 сторон. Наименьшая длина сети L для N > 5 - это длина окружности без одной стороны. Квадраты представляют собой точки Штейнера.

Проблема поиска дерева Штейнера для подмножества вершин, то есть минимального дерева, охватывающего данное подмножество, известна как NP-полная . [37]

Связанная с этим проблема - это k -минимальное остовное дерево ( k -MST), которое представляет собой дерево, которое охватывает некоторое подмножество из k вершин в графе с минимальным весом.

Набор k-наименьших остовных деревьев - это подмножество k остовных деревьев (из всех возможных остовных деревьев), такое, что никакое остовное дерево вне подмножества не имеет меньшего веса. [38] [39] [40] (Обратите внимание, что эта проблема не связана с k -минимальным остовным деревом.)

Евклидово минимальное покрывающее дерево является покрывающее дерево графа с весами ребер , соответствующих евклидова расстояния между вершинами , которые являются точками на плоскости (или пространства).

Прямолинейное минимальное покрывающее дерево является покрывающее дерево графа с весами ребер , соответствующих расстоянию прямолинейного между вершинами , которые являются точками на плоскости (или пространства).

В распределенной модели , где каждый узел считается компьютером и ни один узел не знает ничего, кроме своих собственных связанных ссылок, можно рассматривать распределенное минимальное связующее дерево . Математическое определение проблемы такое же, но есть разные подходы к решению.

Капаситированный минимальный покрывающее дерево является деревом , которое имеет выраженный узел (происхождение, или корень) , и каждый из поддерев , прикрепленных к узлу содержит не более гр узлов. c называется емкостью дерева. Решение корочки оптимально является NP-трудным , [41] но хорошие эвристики , таких как Исав-Williams и плодоовощных решения Шарма близки к оптимальному в полиномиальное время.

Степени ограничена минимальное покрывающее дерево является минимальным связующим деревом , в котором каждая вершина не соединена с не более чем д других вершин, в течение некоторого заданного числа г . Случай d  = 2 является частным случаем задачи коммивояжера , поэтому минимальное остовное дерево с ограничениями по степени в целом является NP-трудным .

Для ориентированных графов проблема минимального остовного дерева называется проблемой арборесценции и может быть решена за квадратичное время с помощью алгоритма Чу – Лю / Эдмондса .

Максимальный покрывающее дерево является покрывающим деревом с весом , превышающим или равным весом любого другого покрывающего дерева. Такое дерево можно найти с помощью таких алгоритмов, как Prim или Kruskal, после умножения весов ребер на -1 и решения проблемы MST на новом графе. Путь в максимальном остовном дереве - это самый широкий путь в графе между двумя его конечными точками: среди всех возможных путей он максимизирует вес ребра с минимальным весом. [42] Максимальные остовные деревья находят применение в алгоритмах синтаксического анализа естественных языков [43] и в алгоритмах обучения условных случайных полей .

Проблема динамического MST касается обновления ранее вычисленного MST после изменения веса ребра в исходном графе или вставки / удаления вершины. [44] [45] [46]

Задача минимального разметки остовного дерева состоит в том, чтобы найти остовное дерево с наименьшим количеством типов меток, если каждое ребро в графе связано с меткой из конечного набора меток вместо веса. [47]

Ребро узкого места - это край с самым высоким весом в остовном дереве. Остовное дерево - это остовное дерево с минимальным узким местом (или MBST ), если граф не содержит остовного дерева с меньшим весом ребра узкого места. MST обязательно является MBST (доказывается свойством cut ), но MBST не обязательно является MST. [48] [49]

Ссылки [ править ]

  1. ^ "Имеют ли минимальные остовные деревья взвешенного графа одинаковое количество ребер с заданным весом?" . cs.stackexchange.com . Проверено 4 апреля 2018 года .
  2. ^ a b c d e Петти, Сет; Рамачандрану, Виджая (2002), "Оптимальный минимальный древовидный алгоритм" (PDF) , Журнал Ассоциации по вычислительной технике , 49 (1): 16-34, DOI : 10,1145 / 505241,505243 , MR 2148431 , S2CID 5362916   .
  3. ^ Каргер, Дэвид Р .; Klein, Philip N .; Тарьян, Роберт Е. (1995), «Рандомизированное алгоритм линейного времени , чтобы найти минимум связующих деревьев», Журнал Ассоциации вычислительной техники , 42 (2): 321-328, DOI : 10,1145 / 201019,201022 , MR 1409738 , S2CID 832583  
  4. ^ Петти, Сет; Рамачандран, Виджая (2002), «Минимизация случайности в минимальном остовном дереве, параллельная связность и алгоритмы установки максимума», Proc. 13-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '02) , Сан-Франциско, Калифорния, стр. 713–722.
  5. ^ Б Chazelle, Bernard (2000), "Минимальный древовидный алгоритм со сложностью типа обратного Аккерман", Журнал Ассоциации вычислительной техники , 47 (6): 1028-1047, DOI : 10,1145 / 355541,355562 , MR 1866456 , S2CID 6276962  .
  6. ^ Chazelle, Bernard (2000), "Мягкая куча: приблизительная приоритетная очередь с оптимальной частотой ошибок" (PDF) , Журнал Ассоциации вычислительной техники , 47 (6): 1012-1027, DOI : 10,1145 / 355541,355554 , MR 1866455 , S2CID 12556140   .
  7. ^ Фредман, ML; Tarjan, RE (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети». Журнал ACM . 34 (3): 596. DOI : 10,1145 / 28869,28874 . S2CID 7904683 . 
  8. ^ Габоу, HN; Галил, З .; Спенсер, Т .; Tarjan, RE (1986). «Эффективные алгоритмы поиска минимальных остовных деревьев в неориентированных и ориентированных графах». Combinatorica . 6 (2): 109. DOI : 10.1007 / bf02579168 . S2CID 35618095 . 
  9. ^ Фредман, ML ; Willard, DE (1994), "Транс-дихотомические алгоритмы минимальных остовных деревьев и кратчайших путей", журнал компьютерных и системных наук , 48 (3): 533-551, DOI : 10.1016 / S0022-0000 (05) 80064-9 , Руководство по ремонту 1279413 .
  10. ^ Чонг, Ка Вонг; Хан, Ицзе; Lam, Так Ва (2001), "Параллельные потоки и оптимальное минимальное параллельное остовных деревьев Алгоритм", Журнал Ассоциации вычислительной техники , 48 (2): 297-323, DOI : 10,1145 / 375827,375847 , МР 1868718 , S2CID 1778676  .
  11. ^ Петти, Сет; Рамачандрану, Виджая (2002), "Рандомизированное времени работы алгоритма оптимальной параллельной для нахождения минимального остовного леса" (PDF) , SIAM журнал по вычислениям , 31 (6): 1879-1895, DOI : 10,1137 / S0097539700371065 , MR 1954882  .
  12. ^ Бадер, Дэвид А .; Конг, Гоцзин (2006), «Быстрые алгоритмы с общей памятью для вычисления минимального остовного леса разреженных графов», Журнал параллельных и распределенных вычислений , 66 (11): 1366–1378, doi : 10.1016 / j.jpdc.2006.06. 001 , S2CID 2004627 .
  13. ^ Дементьев, Роман; Сандерс, Питер; Шультес, Доминик; Сибейн, Джоп Ф. (2004), "Разработка алгоритма минимального остовного дерева внешней памяти", Proc. 18-й Всемирный компьютерный конгресс IFIP, 3-я Международная конференция TC1 по теоретической информатике (TCS2004) (PDF) , стр. 195–208 .
  14. ^ Стил, Дж. Майкл (2002), «Минимальные остовные деревья для графов со случайной длиной ребер», Математика и информатика, II (Версаль, 2002) , Trends Math., Базель: Birkhäuser, стр. 223–245, MR 1940139 
  15. ^ Грэм, RL ; Ад, Pavol (1985), "Об истории минимального остовного дерева проблем", Анналы истории вычислительной техники , 7 (1): 43-57, DOI : 10,1109 / MAHC.1985.10011 , MR 0783327 , S2CID 10555375  
  16. ^ Никос Христофидес , Пессимистический анализ нового эвристики для задачи коммивояжера , Отчет 388, Высшая школа промышленного управления, КМУ, 1976.
  17. ^ Dahlhaus, E .; Джонсон, DS ; Пападимитриу, Швейцария ; Сеймур, PD ; Яннакакис, М. (август 1994 г.). «Сложность многотерминальных разрезов» (PDF) . SIAM Journal on Computing . 23 (4): 864–894. DOI : 10,1137 / S0097539792225297 . Архивировано из оригинального (PDF) 24 августа 2004 года . Проверено 17 декабря 2012 года .
  18. ^ Supowit, Кеннет Дж .; Плейстед, Дэвид А .; Рейнгольд, Эдвард М. (1980). Эвристика для взвешенного идеального соответствия . 12-й ежегодный симпозиум ACM по теории вычислений (STOC '80). Нью-Йорк, Нью-Йорк, США: ACM. С. 398–419. DOI : 10.1145 / 800141.804689 .
  19. ^ Снит, PHA (1 августа 1957). «Применение компьютеров в таксономии» . Журнал общей микробиологии . 17 (1): 201–226. DOI : 10.1099 / 00221287-17-1-201 . PMID 13475686 . 
  20. ^ Асано, Т .; Bhattacharya, B .; Keil, M .; Яо, Ф. (1988). Алгоритмы кластеризации на основе минимального и максимального остовных деревьев . Четвертый ежегодный симпозиум по вычислительной геометрии (SCG '88). 1 . С. 252–257. DOI : 10.1145 / 73393.73419 .
  21. ^ Гауэр, JC; Росс, GJS (1969). «Минимальные связующие деревья и кластерный анализ единственной связи». Журнал Королевского статистического общества . C (Прикладная статистика). 18 (1): 54–64. DOI : 10.2307 / 2346439 . JSTOR 2346439 . 
  22. ^ Пяйвинен, Нину (1 мая 2005). «Кластеризация с минимальным остовным деревом безмасштабной структуры». Письма с распознаванием образов . 26 (7): 921–930. DOI : 10.1016 / j.patrec.2004.09.039 .
  23. ^ Xu, Y .; Olman, V .; Сюй Д. (1 апреля 2002 г.). «Кластеризация данных экспрессии генов с использованием теоретико-графического подхода: применение минимальных остовных деревьев» . Биоинформатика . 18 (4): 536–545. DOI : 10.1093 / биоинформатики / 18.4.536 . PMID 12016051 . 
  24. ^ Далал, Йоген К .; Меткалф, Роберт М. (1 декабря 1978 г.). «Пересылка широковещательных пакетов по обратному пути». Коммуникации ACM . 21 (12): 1040–1048. DOI : 10.1145 / 359657.359665 . S2CID 5638057 . 
  25. ^ Ma, B .; Герой, А .; Gorman, J .; Мишель, О. (2000). Регистрация изображений с помощью алгоритма минимального остовного дерева (PDF) . Международная конференция по обработке изображений. 1 . С. 481–484. DOI : 10,1109 / ICIP.2000.901000 .
  26. ^ P. Felzenszwalb, D. Huttenlocher: Эффективная графическая сегментация изображений. IJCV 59 (2) (сентябрь 2004 г.)
  27. ^ Сук, Минсу; Сон, Охён (1 июня 1984 г.). «Извлечение криволинейных объектов с использованием минимальных остовных деревьев». Компьютерное зрение, графика и обработка изображений . 26 (3): 400–411. DOI : 10.1016 / 0734-189X (84) 90221-4 .
  28. ^ Тапиа, Эрнесто; Рохас, Рауль (2004). «Распознавание он-лайн рукописных математических выражений с использованием конструкции минимального связующего дерева и доминирования символов» (PDF) . Распознавание графики. Последние достижения и перспективы . Конспект лекций по информатике. 3088 . Берлин Гейдельберг: Springer-Verlag. С. 329–340. ISBN  978-3540224785.
  29. ^ Олссон, H. (2004). Реализация КИХ-фильтров низкой сложности с использованием минимального остовного дерева . 12-я Средиземноморская электротехническая конференция IEEE (MELECON 2004). 1 . С. 261–264. DOI : 10.1109 / MELCON.2004.1346826 .
  30. ^ AssunÇão, RM; MC Neves; Г. Камара; К. Да Коста Фрейтас (2006 г.). «Эффективные методы регионализации для социально-экономических географических единиц с использованием минимальных остовных деревьев» . Международный журнал географической информатики . 20 (7): 797–811. DOI : 10.1080 / 13658810600665111 . S2CID 2530748 . 
  31. ^ Devillers, J .; Доре, JC (1 апреля 1989 г.). «Эвристическая эффективность метода минимального остовного дерева (MST) в токсикологии». Экотоксикология и экологическая безопасность . 17 (2): 227–235. DOI : 10.1016 / 0147-6513 (89) 90042-0 . PMID 2737116 . 
  32. ^ Мори, H .; Цузуки, С. (1 мая 1991 г.). «Быстрый метод анализа топологической наблюдаемости с использованием метода минимального остовного дерева». IEEE Transactions on Power Systems . 6 (2): 491–500. Bibcode : 1991ITPSy ... 6..491M . DOI : 10.1109 / 59.76691 .
  33. ^ Филлибен, Джеймс Дж .; Кафадар, Карен ; Шайер, Дуглас Р. (1 января 1983 г.). «Проверка на однородность двумерных поверхностей» . Математическое моделирование . 4 (2): 167–189. DOI : 10.1016 / 0270-0255 (83) 90026-X .
  34. ^ Калаба, Роберт Э. (1963), Теория графов и автоматическое управление (PDF)
  35. Перейти ↑ Mantegna, RN (1999). Иерархическая структура финансовых рынков . Европейский физический журнал B-конденсированное вещество и сложные системы, 11 (1), 193-197.
  36. ^ Djauhari, М., & Gan, С. (2015). Проблема оптимальности сетевой топологии в анализе фондового рынка . Physica A: Статистическая механика и ее приложения, 419, 108-114.
  37. ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5. ND12
  38. ^ Gabow, Гарольд Н. (1977), "Два алгоритма для генерирования взвешенных с учетом связующих деревьев в порядке", SIAM журнал по вычислениям , 6 (1): 139-150, DOI : 10,1137 / 0206011 , МР 0441784 .
  39. ^ Эпштайна, Дэвид (1992), "Нахождение K наименьшие связующих деревьев", БИТ , 32 (2): 237-248, DOI : 10.1007 / BF01994879 , MR 1172188 , S2CID 121160520  .
  40. ^ Фредериксон, Грег Н. (1997), "амбивалентные структуры данных для динамического 2-кра-соединения и K наименьшее остовных деревьев" , SIAM журнал по вычислениям , 26 (2): 484-538, DOI : 10,1137 / S0097539792226825 , МР 1438526 .
  41. ^ Jothi Раджа; Рагхавачари, Баладжи (2005), «Алгоритмы аппроксимации для задачи минимального связующего дерева с ограниченными возможностями и ее варианты в проектировании сети», ACM Trans. Алгоритмы , 1 (2): 265-282, DOI : 10,1145 / 1103963,1103967 , S2CID 8302085 
  42. ^ Ху, TC (1961), "Максимальная емкость проблема маршрута", исследование операций , 9 (6): 898-900, DOI : 10,1287 / opre.9.6.898 , JSTOR 167055 .
  43. ^ Макдональд, Райан; Перейра, Фернандо; Рибаров, Кирилл; Гайч, Ян (2005). «Непроективный анализ зависимостей с использованием алгоритмов связующего дерева» (PDF) . Proc. HLT / EMNLP .
  44. ^ Спира, PM; Пан, А. (1975), "О поиске и обновлении связующих деревьев и кратчайших путей" (PDF) , SIAM журнал по вычислениям , 4 (3): 375-380, DOI : 10,1137 / 0204032 , MR 0378466  .
  45. ^ Холм, Джейкоб; де Лихтенберг, Кристиан; Thorup, Миккель (2001), "Поли-логарифмические детерминированные полностью динамические алгоритмы для подключения, минимальный остов, 2-кромка, и biconnectivity", Журнал Ассоциации вычислительной техники , 48 (4): 723-760, DOI : 10,1145 /502090.502095 , МР 2144928 , S2CID 7273552  .
  46. ^ Подбородок, F .; Хоук, D. (1978), "Алгоритмы для обновления минимальных остовных деревьев", журнал компьютерных и системных наук , 16 (3): 333-344, DOI : 10.1016 / 0022-0000 (78) 90022-3.
  47. ^ Чанг, RS; Leu, SJ (1997), "Минимальная маркировка остовных деревьев", Information Processing Letters , 63 (5): 277-282, DOI : 10.1016 / s0020-0190 (97) 00127-0.
  48. ^ "Все о связующем дереве узких мест" . flashing-gotits.blogspot.ru . Проверено 4 апреля 2018 года .
  49. ^ http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf

Дальнейшее чтение [ править ]

  • Отакар Борувка о проблеме минимального остовного дерева (перевод обеих статей 1926 года, комментарии, история) (2000) Ярослав Нешетржил , Ева Милкова, Хелена Несетрилова. (В разделе 7 приводится его алгоритм, который выглядит как нечто среднее между алгоритмом Прима и Крускала.)
  • Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Глава 23: Минимальные остовные деревья, стр. 561–579. 
  • Эйснер, Джейсон (1997). Современные алгоритмы для минимальных остовных деревьев: обсуждение в учебном пособии . Рукопись, Пенсильванский университет, апрель. 78 стр.
  • Кромковский, Джон Дэвид. «Все еще не растаял после всех этих лет», в Annual Editions, Race and Ethnic Relations, 17 / e (McGraw Hill 2009) (Использование минимального остовного дерева в качестве метода демографического анализа этнического разнообразия в США).

Внешние ссылки [ править ]

  • Реализована в BGL, Библиотека графов ускорения.
  • Репозиторий алгоритмов Стоуни-Брук - минимальные коды связующего дерева
  • Реализовано в QuickGraph для .Net