matroid

• IPA:

matroid

1. (matematika, kombinatorika)

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.

Egy matroid egy rendezett pár ${\displaystyle M=(E,{\mathcal {I}})}$, ahol:

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

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

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

A matroidhoz tartozó rangfüggvény egy ${\displaystyle 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:

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

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.

matrix +‎ oid

• matroid - Értelmező szótár (MEK)
• matroid - Etimológiai szótár (UMIL)
• matroid - Szótár.net (hu-hu)
• matroid - DeepL (hu-de)
• matroid - Яндекс (hu-ru)
• matroid - Google (hu-en)
• matroid - Helyesírási szótár (MTA)
• matroid - Wikidata
• matroid - Wikipédia (magyar)