Rešitev: Najcenejše vpeto drevo

Iz MaFiRaWiki

Naloga: Najcenejše vpeto drevo

Primeren format za predstavitev vhodnih podatkov je matrika. Vhodni podatki so torej matrika uteži grafa.

  Clear[NVD, NVDGraf]

NVD::usage = "NVD[m] vrne matriko sosednjosti najcenejšega vpetega drevesa v neusmerjenem grafu z matriko uteži m.";

  NVD[m_List] /; SymmetricQ[m] := \MatrixForm[ToAdjacencyMatrix
  [MinimumSpanningTree[FromAdjacencyMatrix[m, \EdgeWeight]]]]
  NVD[m_List] := "Matrika ni simetrična."

NVDGraf::usage = "NVDGraf[m] v neusmerjenem grafu z matriko uteži m označi najcenejše vpeto drevo.";

   NVDGraf[m_List] /; SymmetricQ[m] := Module[{a, b, c},
   a = FromAdjacencyMatrix[m, EdgeWeight];
   a = SetEdgeLabels[a, GetEdgeWeights[a]];
   b = Map[#1 &, MinimumSpanningTree[a]1];
   a = Highlight[a, {b}, HighlightedEdgeColors -> {Red}];
   ShowGraph[a]
   ]
  NVDGraf[m_List] := "Matrika ni simetrična."
  Clear[Matrika]

Matrika::usage = "Matrika[n,p,t] vrne matriko uteži naključnega obteženega neusmerjenega povezanega grafa z n vozlišči, v karerem je verjetnost, da sta dve vozlišči povezani, enaka p (p≥0.1) in so teže povezav naravna števila do največ t.";

   Matrika[n_Integer, p_, t_Integer] /; p ≥ 0.1 := Module[{x, y, z},
   x = RandomGraph[n, p];
   While[! ConnectedQ[x], x = RandomGraph[n, p];];
   x = ToAdjacencyMatrix[x, EdgeWeight];
   y = Table[Random[Integer, {1, t}], {i, 1, n}, {j, 1, n}];
   z = Floor[(y*x + Transpose[y*x])/2];
   Return[z]
   ]
Osebna orodja