Tudd Intuíció, előadás, kapzsi és matroid
Kivonat: matroid. Rado-Edmonds tétel. Súlyozott megfelelő.
Mohó algoritmusok és matroidok
Kapzsi (gradiens) egy algoritmus elven működő „legnagyobb erősítés minden lépésnél.” Ez a stratégia nem mindig vezet a végső siker - néha sokkal jövedelmezőbb kell tennie, hogy nem a legjobb, úgy tűnik, a választás a következő lépés annak érdekében, hogy végre kap az optimális megoldást. De ez indokolt valamilyen feladat használja mohó algoritmusok. Az egyik jól ismert probléma az ilyen jellegű probléma az optimális keretet. Van egy közös elmélet, amely indokolja az alkalmazhatóságát mohó algoritmusok problémák egy bizonyos típusú, amelyek közé tárgyalt az „utolsó előadás” Kruskal algoritmus. Ez az előadás kap egy vázlatot az elmélet. Ezután a mohó algoritmus lesz szó együtt módszer egyre módon megoldani a problémát, a maximális súlya párosítást egy páros gráf súlyozott csúcsot.
Amikor felmerült a kérdés, hogy mi a körülményeket, amelyek a mohó algoritmus rezultativen, egyébként - mi a különleges a feladatokat, amelyekre ez biztosítja a pontos megoldást, azt találtuk, hogy a matematikai elmélet, amellyel valamit, ami lehet tiszta, már létezik . Ez az elmélet a matroidok. amelynek alapjait Whitney 1935 célja az elmélet matroidok tanulmányozása volt kombinatorikus szempontjait lineáris függetlenség, és később kiderült a különböző alkalmazások matroidot fogalmak. az eredeti nem a rendelkezésre álló eszközökkel.
Definíció. Matroid egy pár, ahol - véges, nem üres halmaz, - egy család részhalmazát olyan, hogy:
- (1), ha majd;
- (2) ha, és van egy elem olyan, hogy.
A halmaz elemeinek nevezzük az elemek egy matroid. és meghatározza a család - független készlet matroid. Max, hogy tartalmazza a független halmaz az úgynevezett alap matroid. A axióma (2) az következik, hogy az összes bázist Matroid áll az azonos számú elemet.
Amikor - több sor egy mátrix, és magában foglalja az összes lineárisan független készlet sora ez a mátrix, a pár képez matroidot. úgynevezett mátrix matroidot.
Egy másik fontos típusa matroidok vannak grafikon matroidok. Let - rendes grafikonon. A részhalmaza az úgynevezett gyűrűs. ha a gráf. kialakított bordák ezen alcsoportjában nem tartalmaz ciklusok, azaz Ez egy erdőben.
1. Tétel Ha a - rendes grafikon. - a család minden részhalmaza gyűrűs, akkor a pár egy matroid.
Bizonyítás. Axióma (1) teljesül, mivel minden részhalmaza aciklusos sokaságát nyilvánvalóan aciklikus. Azt állítják, hogy végezzük, és (2). Let - két és gyűrűs. Tegyük fel, hogy nincs ilyen él, a készlet gyűrűs. Ezután hozzáadjuk bármely bordák sokasága van kialakítva, hogy több cikluson keresztül. Ez azt jelenti, hogy a végén minden ilyen borda tartoznak az egyik csatlakoztatott komponens spanning részgráfot sokaságával képzett bordák. Ezután minden területen kapcsolat részgráfot szereplő bármely területén részgráfot kapcsolat. De a csatlakoztatott komponensek minden ilyen részgráfok - fák, és a tetején a fa tartalmaz pontosan élek. Ezért ebben az esetben az élek száma nem lehet nagyobb, mint az élek száma a, ami ellentmond a hipotézist.
Graph matroidnak bázisok összes keretét a grafikon. Egy gráf akkor minden feszít®fája.