Как найти минимальное ребро покрытия взвешенного двудольного графа с помощью Mathematica 8? - PullRequest
Новая
       28

Как найти минимальное ребро покрытия взвешенного двудольного графа с помощью Mathematica 8?

8 голосов
/ 11 сентября 2011

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

Я нахожучто в новой версии 8 Mathematica появился новый пакет функций для теории графов (начните с Graph []). Но я не нашел ни одной функции, которая бы выполняла эту работу.Я нахожу функцию с именем FindEdgeCover [], которая может найти только край обложки , но не минимальный.

1 Ответ

6 голосов
/ 11 сентября 2011

Я провел несколько экспериментов и, хотя и не задокументирован, кажется, что FindEdgeCover[] делает то, что вы хотите.

Рассмотрим для примера: 

 h[list_] := CompleteGraph[4, EdgeWeight -> list]

 FindEdgeCover[h@Range@6]
 (*
 ->  {1->2,1->3,1->4}
 *)

Но 

 FindEdgeCover[h@Reverse@Range@6]
 (*
 -> {1->2,3->4}
 *)

конечно без гарантии ...

Редактировать

Здесь у вас есть некоторый код для экспериментов с использованием различных взвешенных матриц смежности 

adj = {{\[Infinity], 1, 1, 1, 1}, {1, \[Infinity], 2, 2, 2}, 
       {1, 2, \[Infinity], 2, 2}, {1, 2, 2, \[Infinity], 2}, 
       {1, 2, 2, 2, \[Infinity]}}
g = WeightedAdjacencyGraph[adj];
g = WeightedAdjacencyGraph[adj, VertexShapeFunction -> "Name", 
  EdgeLabels -> 
   MapThread[
    Rule, {EdgeList@g, AbsoluteOptions[g, EdgeWeight] /. {_ -> x_} -> x}], 
  GraphHighlight -> FindEdgeCover[g]]

enter image description here

Примечание: код совсем не хорош, но я не смог найти способ использовать EdgeLabels -> “EdgeWeight”. Я разместил this question, чтобы посмотреть, сможет ли кто-нибудь это сделать.

...