Különbségek
A kiválasztott változat és az aktuális verzió közötti különbségek a következők.
|
|
|
oktatas:matematika:kombinatorika:minimalis_koeltsegu_feszitofa [2019/06/04 13:26]
barnkopf ↷ Page moved from matematika:kombinatorika:minimalis_koeltsegu_feszitofa to oktatas:matematika:kombinatorika:minimalis_koeltsegu_feszitofa |
oktatas:matematika:kombinatorika:minimalis_koeltsegu_feszitofa [2019/06/06 10:59] (aktuális)
66.249.70.5 ↷ Links adapted because of a move operation |
| |
| **Értelmezés:** | **Értelmezés:** |
| Adott egy összefüggő, [[grafelmelet#egyszerű gráf]], súlyozott élekkel - ezek a "költségek". Keressünk egy minimális költségű (költségösszegű) olyan részgráfot, mely a gráf összes pontját tartalmazza! | Adott egy összefüggő, [[matematika:kombinatorika:grafelmelet#egyszerű gráf]], súlyozott élekkel - ezek a "költségek". Keressünk egy minimális költségű (költségösszegű) olyan részgráfot, mely a gráf összes pontját tartalmazza! |
| |
| Egy ilyen részgráf nyilván [[matematika:kombinatorika:fa]] kell legyen, ugyanis ha volna benne kör, akkor annak egy tetszőleges élét elhagyva - ezzel a költségek összegét csökkentve - még továbbra is összefüggő maradna a gráf. A keresett gráf tehát egy olyan fa, mely a gráf összes pontját tartalmazza, azaz *feszítő fa*. | Egy ilyen részgráf nyilván [[matematika:kombinatorika:fa]] kell legyen, ugyanis ha volna benne kör, akkor annak egy tetszőleges élét elhagyva - ezzel a költségek összegét csökkentve - még továbbra is összefüggő maradna a gráf. A keresett gráf tehát egy olyan fa, mely a gráf összes pontját tartalmazza, azaz *feszítő fa*. |
