matroid rangja

Magyar

Kiejtés

• IPA: [ ˈmɒtrojidrɒŋɡjɒ]

Főnév

matroid rangja

1. (matematika) A matroid rangja a matroidok elméletében egy fontos fogalom, amely egy halmaz maximális független részhalmazainak méretével van összefüggésben.

Definíció

Egy \( M = (E, \mathcal{I}) \) matroid rangja az \( E \) alaphalmaz maximális független részhalmazainak elemeinek száma. Matematikailag:

$r(M)=\max\{|I|\ :\ I\in {\mathcal {I}}\},$

ahol \( \mathcal{I} \) az \( M \) matroid független halmazainak rendszere.

Jellemzők

• A rang mindig egy nemnegatív egész szám.
• Ha egy \( A \subseteq E \) részhalmazra vonatkoztatjuk, akkor \( r(A) \) az \( A \)-ban található maximális független részhalmaz mérete.
• A rangfüggvény (\( r: 2^E \to \mathbb{Z} \)) kielégít bizonyos axiómákat, például:
  • Nemnegativitás: \( r(A) \geq 0 \).
  • Monotonitás: Ha \( A \subseteq B \), akkor \( r(A) \leq r(B) \).
  • Szubmodularitás: \( r(A \cup B) + r(A \cap B) \leq r(A) + r(B) \) minden \( A, B \subseteq E \)-re.

Példa

Tekintsük a gráfokhoz kapcsolódó függőségi matroidot. Egy gráf \( G = (V, E) \) esetén az élhalmazon alapuló matroidban a független halmazok azok az élhalmazok, amelyek nem tartalmaznak kört. Ennek a matroidnak a rangja a gráf maximális feszítőfájának élszáma, amely egyenlő a csúcsok számával (\( |V| \)) mínusz 1 (feltéve, hogy a gráf összefüggő).

Fordítások

Tartalom

angol: rank of a matroid (en)

További információk

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