Matroid rangja

1. Sablon:Label 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 ℐ\},$

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ő).

Sablon:-ford- Sablon:Trans-top

• Sablon:En: Sablon:T