matroid

Magyar

Kiejtés

• IPA: [ ˈmɒtrojid]

Főnév

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.

Definíció

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

• $E$ egy véges alaphalmaz (gyakran "élek" vagy "elemek" halmaza),
• ${\mathcal {I}}$ 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: $\emptyset \in {\mathcal {I}}$.
2. Ha $I\in {\mathcal {I}}$ és $J\subseteq I$, akkor $J\in {\mathcal {I}}$. (Monotonitás.)
3. Ha $I,J\in {\mathcal {I}}$ és $|I|<|J|$, akkor létezik olyan $e\in J\setminus I$, amelyre $I\cup \{e\}\in {\mathcal {I}}$. (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\leq r(A)\leq |A|$ minden $A\subseteq E$ esetén,
• Ha $A\subseteq B$, akkor $r(A)\leq r(B)$,
• $r(A\cup B)+r(A\cap B)\leq 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.

Fordítások

Tartalom

angol: matroid (en) francia: matroïde (fr) hn olasz: matroide (it) hn

Etimológia

matrix +‎ oid

További információk

• 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)