Аксиоматизация матроида рангами

Лемма:

Пусть [math]r: 2^X \to \{0\} \cup \mathbb{N}[/math] удовлетворяет условиям теоремы ниже, [math] B \subset A \in 2^X[/math], [math]r(B) = |B|[/math], и [math] A \setminus B = \{p_1, \ldots p_t\}[/math]. Если [math]r(B \cup p_i) = |B|[/math] для любого [math] i = 1, \ldots , t[/math], то [math]r(A) = |B|[/math]

Доказательство:

[math]\triangleright[/math]

По индукции: предположим, что [math]r(B \cup p_1 \cup \ldots \cup p_j) = |B|[/math] для некоторого [math]j = 1, \ldots ,t-1[/math]. Тогда, применяя (2) и (3), получаем: [math]|B| = r(B) = r(B \cup p_1 \cup \ldots \cup p_j) \leqslant r(B \cup p_1 \cup \ldots \cup p_{j+1}) \leqslant r(B \cup p_1\cup \ldots \cup p_j) + r(B \cup p_{j+1}) -r(B) = |B| + |B| - |B| = |B| [/math]. Следовательно, [math]r(B \cup p_1 \cup \ldots \cup p_{j+1}) = |B|[/math]. Переход доказан, а значит, [math]r(B \cup p_1 \cup \ldots \cup p_t) = |B|[/math].

[math]\triangleleft[/math]

Теорема (об аксиоматизации матроида рангами):

Пусть некоторая функция [math]r: A \in 2^X \to \mathbb{N}[/math], где [math]X[/math] — конечное непустое множество, удовлетворяет условиям: [math] 0 \leqslant r(A) \leqslant |A| [/math]. [math] A \subseteq B \Rightarrow r(A) \leqslant r(B) [/math]. [math]\forall A, B \subset X,[/math] [math]r(A \cup B) + r(A \cap B) \leqslant r(A) + r(B)[/math] Тогда [math]r[/math] является ранговой функцией однозначно определенного матроида на [math]X[/math].

Доказательство:

[math]\triangleright[/math]

Подмножество [math]I \in 2^X[/math] назовем [math]r[/math]-независимым, если выполняется [math]r(I) = |I|[/math]. Обозначим через [math]\mathcal{I} \subseteq 2^X[/math] множество всех [math]r[/math]-независимых подмножеств из [math]2^X[/math]. Докажем, что [math]\mathcal{I}[/math] удовлетворяет аксиомам независимого множества 1, 2 и 3: В силу (1) выполняется [math]r(\emptyset)=0[/math], следовательно [math] \emptyset \in \mathcal{I}[/math]. Пусть [math] I \in \mathcal{I}[/math] и [math]J \subseteq I[/math]. Предположим от противного, что [math]r(J) \lt |J|[/math]. Тогда, используя (1) и (3), получаем: [math]|I| = r(I) = r(J \cup (I \setminus J)) \leqslant r(J) + r(I \setminus J) - r(\emptyset) \lt |J| + |I \setminus J| = |I|[/math], что невозможно. Следовательно, [math]r(J) = |J|[/math], т.е. [math] J \in \mathcal{I} [/math] Пусть [math]I, J \subseteq \mathcal{I}[/math] и [math]|I| \lt |J|[/math]. Положим [math]J \setminus I = \{p_1, \ldots,p_t\}[/math]. Пусть, от противного, [math]I \cup p_i \nsubseteq \mathcal{I}[/math] для любого [math]i = 1, \ldots,t[/math]. Тогда для [math]i = 1, \ldots,t[/math] имеет место: [math] |I| = r(I) \leqslant r(I \cup p_i) \lt |I \cup p_i| = |I| + 1[/math], т.е. [math] r(I \cup p_i) = |I|[/math]. Отсюда, в силу доказанной раннее леммы, получаем [math] r(I \cup J) = |I|[/math]. С другой стороны, [math]|I| \lt |J| = r(J) \leqslant r(I \cup J)[/math]. Противоречие. Все три аксиомы выполняются на [math]\mathcal{I}[/math], соответственно, семейство [math]\mathcal{I}[/math] является семейством независимых множеств некоторого матроида [math] M = \langle X, \mathcal{I} \rangle[/math]. Осталось проверить, что исходная функция [math]r[/math] совпадает с ранговой функцией матроида [math]M[/math]. Так как, по определению, ранговая функция равна мощности максимального независимого подмножества множества (мощности базы множества), для этого достаточно доказать, что для любой базы [math]B[/math] произвольного множества [math]A \in 2^X, B \subseteq A[/math] выполняется [math] r(A) = |B| [/math]. Пусть [math]B[/math] — база множества [math]A \in 2^X[/math]. По определению [math]r [/math] имеем [math] r(B) = |B|[/math] и [math]B[/math] — максимальное [math]r[/math]-независимое подмножество из [math]A[/math]. Если [math]A=B[/math], то, очевидно, [math]r(A)=r(B).[/math] Поэтому пусть [math]B \in A[/math]. Пусть [math] A \setminus B = \{p_1, \ldots ,p_t\}[/math]. В силу максимальности [math]B[/math] для любого [math]i = 1, \ldots,t[/math] множество [math]B \cup p_i[/math] не является [math]r[/math]-независимым, т.е. [math]r(B \cup p_i) \lt |B \cup p_i|[/math]. Тогда имеем: [math] |B| = r(B) \leqslant r(B \cup p_i) \lt |B \cup p_i| = |B| + 1 [/math], т.е. [math] r(B \cup p_i) = |B| [/math]. В силу доказанного утверждения получаем [math]r(A) = |B|[/math].

[math]\triangleleft[/math]

См. также

• Аксиоматизация матроида базами
• Аксиоматизация матроида циклами

Источники информации

• Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2