Matroid forrásának megtekintése

{{hunFn}}
{{hu-noun}}
# {{lbl|hu|math|combinatorics}}  
'''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 <math>M = (E, \mathcal{I})</math>, ahol:
* <math>E</math> egy véges alaphalmaz (gyakran "élek" vagy "elemek" halmaza),
* <math>\mathcal{I}</math> az <math>E</math> 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 ===
# Az üres halmaz független: <math>\emptyset \in \mathcal{I}</math>.
# Ha <math>I \in \mathcal{I}</math> és <math>J \subseteq I</math>, akkor <math>J \in \mathcal{I}</math>. (Monotonitás.)
# Ha <math>I, J \in \mathcal{I}</math> és <math>|I| < |J|</math>, akkor létezik olyan <math>e \in J \setminus I</math>, amelyre <math>I \cup \{e\} \in \mathcal{I}</math>. (Cseretulajdonság.)

== Példák ==
* '''Gráfokból származó matroid:''' Egy gráf esetén az <math>E</math> az élek halmaza, és egy részhalmaz független, ha nem tartalmaz kört.
* '''Lineáris matroid:''' Az <math>E</math> 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 <math>r: 2^E \to \mathbb{Z}</math> 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:
* <math>0 \leq r(A) \leq |A|</math> minden <math>A \subseteq E</math> esetén,
* Ha <math>A \subseteq B</math>, akkor <math>r(A) \leq r(B)</math>,
* <math>r(A \cup B) + r(A \cap B) \leq r(A) + r(B)</math> minden <math>A, B \subseteq E</math> 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.


{{Translations}}
{{trans-top}}
* {{en}}: {{t|en|matroid}}
* {{fr}}: {{t+|fr|matroïde|m}}
* {{it}}: {{t|it|matroide|m}}
{{trans-bottom}}

{{Etymology}}
{{affix|en|matrix|oid}}
{{hunl}}