Matroid

1. Sablon:Lbl

A matroid egy absztrakt algebrai struktúra, amely a lineáris algebra, a gráfelmélet és a kombinatorika közötti kapcsolatokat modellezi. A matroid fogalma segítségével a függetlenség fogalma általánosítható különböző matematikai rendszerekre.

Definíció

Egy matroid egy rendezett pár $M=(E,ℐ)$, ahol:

• $E$ egy véges alaphalmaz (gyakran "élek" vagy "elemek" halmaza),
• $ℐ$ az $E$ részhalmazainak egy családja, amelyet független halmazoknak nevezünk, és amely kielégíti az alábbi axiómákat:

Függetlenségi axiómák

1. Az üres halmaz független: $\mathrm{\varnothing }\in ℐ$.
2. Ha $I\in ℐ$ és $J\subseteq I$, akkor $J\in ℐ$. (Monotonitás.)
3. Ha $I,J\in ℐ$ és $|I|<|J|$, akkor létezik olyan $e\in J\setminus I$, amelyre $I\cup \{e\}\in ℐ$. (Cseretulajdonság.)

Példák

• Gráfokból származó matroid: Egy gráf esetén az $E$ az élek halmaza, és egy részhalmaz független, ha nem tartalmaz kört.
• Lineáris matroid: Az $E$ egy vektortér vektorainak halmaza, és egy részhalmaz független, ha lineárisan független.

Rangfüggvény

A matroidhoz tartozó rangfüggvény egy $r:2^E\to \mathbb{Z}$ leképezés, amely egy részhalmaz maximális független részhalmazának méretét adja meg. A rangfüggvény kielégíti:

• $0\le r(A)\le |A|$ minden $A\subseteq E$ esetén,
• Ha $A\subseteq B$, akkor $r(A)\le r(B)$,
• $r(A\cup B)+r(A\cap B)\le r(A)+r(B)$ minden $A,B\subseteq E$ esetén. (Szubmodularitás.)

Alkalmazások

A matroidok alkalmazása széleskörű:

• Optimalizálás: Greedy algoritmusok alkalmazása matroidokkal garantáltan optimális megoldást adhat.
• Hálózatelemzés: Hálózatok függetlenségének vizsgálata gráfmatroidokon keresztül.
• Kombinatorikus struktúrák vizsgálata: Például készletgazdálkodás vagy tervezési problémák.

Sablon:Translations Sablon:Trans-top

• Sablon:En: Sablon:T
• Sablon:Fr: Sablon:T+
• Sablon:It: Sablon:T