Jak znaleźć minimalną krawędź krawędziową ważonego wykresu dwudzielnego za pomocą programu Mathematica 8?

Teoretycznie wykres używamy algorytm węgierski obliczania minimalnej ochrony krawędzi ważonego dwustronnym wykresu (zestaw krawędzi, które pada na co wierzchołki tej z minimalnej wadze całkowitej).Jak znaleźć minimalną krawędź krawędziową ważonego wykresu dwudzielnego za pomocą programu Mathematica 8?

znaleźć że nowy wersja 8 Mathematica, istnieje całkiem nowy pakiet funkcji dla Teorii Grafów (zacznij od Graph [].) Ale nie znalazłem żadnej funkcji, która wykonałaby tę pracę. Znajduję funkcję o nazwie FindEdgeCover [], która może znaleźć tylko krawędź krawędzi , a nie minimalną.

Źródło

2011-09-11 trVoldemort

Czy jesteś pewien, że funkcja nie spełnia Twoich oczekiwań? Zgodnie z dokumentacją FindEdgeCover [g] znajduje pokrycie krawędzi wykresu g z minimalną liczbą krawędzi. Więc czy nie jest to znalezienie minimalnej osłony krawędzi w razie potrzeby? W przeciwnym razie udzielono by więcej niż jednej odpowiedzi, w tym nie-minimalnych okładek krawędzi. – Verbeia

Nie, mam na myśli minimalną całkowitą wagę krawędzi w zestawie, a nie liczbę krawędzi. – trVoldemort

Ah, a więc wersja nieważona. Możliwe, że funkcja ta nie została jeszcze wbudowana. – Verbeia

Zrobiłem kilka eksperymentów i, chociaż nie udokumentowane, wydaje się, że FindEdgeCover[] robi to, co chcesz.

Rozważmy na przykład:

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

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

Ale

FindEdgeCover[[email protected]@[email protected]] 
(* 
-> {1->2,3->4} 
*)

oczywiście bez gwarancji ...

Edytuj

Tu masz trochę kodu do eksperymentowania z przez stosując różne ważone sąsiedztwo ma trices

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, {[email protected], AbsoluteOptions[g, EdgeWeight] /. {_ -> x_} -> x}], 
    GraphHighlight -> FindEdgeCover[g]]

enter image description here

NB: Kod nie jest dobre na wszystko, ale nie mogłem znaleźć sposób na wykorzystanie EdgeLabels -> “EdgeWeight”. Wysłałem this question, aby sprawdzić, czy ktoś może to zrobić.

Źródło

2011-09-11 06:03:37

Jak znaleźć minimalną krawędź krawędziową ważonego wykresu dwudzielnego za pomocą programu Mathematica 8?

Odpowiedz

Powiązane problemy