Mi a minimális feszítőfa matematikai modellje?

"Ez milyen tudományágban van?"

Gráfelmélet.

[link]

Kedves Kérdező!

A kérdésben lévő link rossz, ha esetleg korrigálnád, talán érthetőbb lesz a probléma.

Az élek súlyai az utolsó sorban szerepelnek. Ha a gráfodat úgy módosítod, hogy az élein a súlyokat módosítod, akkor a modellben csak minimize feszitofa sort kell változtatnod.

Az ab:, ..., d: feltételek csak arra szolgálnak, hogy az yAB, ..., yDB beválasztások egy feszítőfát alkossanak.

Közvetlenül nincsen benne a modellben az a feltétel, hogy az élek súlya legyen eggyel kevesebb a csúcsoknál.

De ha elolvasod a szöveget, akkor kiderül, hogy az xAB, ...,xDA egy olyan hálózat, ami az A csúcsból elvisz 3 darab cuccot a B, a C és a D csúcsba. (Illetve csak akkor feszítő fa az x hálózat, ha a "feszitofa:" constraint értéke minimális. Egyébként például minden élt és az ellentettjét is be lehetne venni a hálózatba.)