Матроїд

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Матроїд - класифікація підмножин деякої множини, що являє собою узагальнення ідеї незалежності елементів, аналогічно незалежності елементів лінійного простору, на довільну множину.

Аксіоматичне визначення[ред.ред. код]

Матроїд - пара  (X, I) , де  X - скінченна множина, звана носієм матроїда, а  I - деяка множина підмножин  X , звана сімейством незалежних множин, тобто  I \subset  2 ^ X . При цьому повинні виконуватися наступні умови:

  1. \varnothing \in I
  2. Якщо A \in I та B \subset A, то B \in I
  3. Якщо A, B \in I і потужність A більша потужності B, то існує x \in A \setminus B такий, що B \cup \{x\} \in I

Базами матроїда називаються максимальні по включенню незалежні множини. Підмножини  X , які не належать  I , називаються залежними множинами. Мінімальні по включенню залежні множини називаються циклами матроїда, це поняття використовується в альтернативному визначенні матроїда.

Визначення у термінах циклів[ред.ред. код]

Матроїд - пара  (X, C) , де  X - носій матроїда, а  C - сімейство непустих підмножин  X , зване множиною Циклів матроїда, для яких виконуються наступні умови: [1]

  1. Жоден цикл не є підмножиною іншого.
  2. Якщо x \in C_1 \cap C_2, то C_1 \cup C_2 \setminus \{x\} містить цикл.

Визначення у термінах правильного замикання[ред.ред. код]

Нехай (P, \le) - частково впорядкована множина. H: P \to P - замикання в (P, \le), якщо

  1. Для будь-якого x з P:  H (x) \ge x
  2. Для будь-яких x,y з P: x \le y \Rightarrow H(x) \le H (y)
  3. Для будь-якого x з P: H\left(H\left(x\right)\right) = H(x)

Розглянемо (P, \le) = (2^S, \le) випадок, коли частково впорядкована множина - булева алгебра. Нехай A \to H (A) - замикання A \subset S.

  1. Замикання правильне (аксіома правильного замикання), якщо (p \not \in A, p \in H(A \cup \left\{ q \right\}) ) \Rightarrow q \in H(A \cup \left\{ p \right\})
  2. Для будь-якого  A \subset S існує таке  B \subset A, що
    1.  | B | <+ \infty
    2. H \left (B \right) = H \left (A \right)

Пара (S, A \to H (A)) , де  A \to H (A) - правильне замикання на  (2^S, \le), називається матроїдом.

Приклади[ред.ред. код]

  1. Універсальний матроїд Unk. Множина X має потужність n, незалежними множинами є підмножини потужністю не більше k. Бази - підмножини потужністю k.
  2. Матроїд циклів графа. Множина X - множина ребер графа, незалежні множини - ациклічні підмножини цих ребер, цикли - прості цикли графа. Базами є кістякові дерева графа. Матроїд називається 'графічним', якщо він є матроїдом циклів деякого графа. [2]
  3. Матроїд підмножин множини ребер графа, таких що видалення підмножини залишає граф зв'язаним.
  4. Матроїд коциклів графа. Множина X - множина ребер, коцикли - мінімальні множини, видалення яких призводить до втрати зв'язності графа. Матроїд називається 'кографічним', якщо він є матроїдом коциклів деякого графа. [2]
  5. Матричний матроїд. Сімейство всіх лінійно незалежних підмножин будь-якої скінченної множини векторів довільного непорожнього векторного простору є матроїдом.

Визначимо множину E, як таку, що складається з {1, 2, 3, .., n} - номерів стовпців деякої матриці, а множину I, як таку, яка складається з підмножин E, таких що вектори, які визначаються ними, є лінійно незалежними над полем дійсних чисел R. Виникає питання - якими властивостями володіє побудована множина I?

  1. Множина I - непорожня. Навіть якщо вихідна множина E була б порожньою - E = ∅, то I буде складатися з одного елемента - множини, що містить порожню множину I = ∅.
  2. Будь-яка підмножина будь-якого елемента множини I також буде елементом цієї множини. Ця властивість зрозуміла - якщо деякий набір векторів лінійно незалежний над полем, то лінійно незалежним буде також будь-який його піднабір.
  3. Якщо A, B ∈ I, причому | A | = | B | + 1, тоді існує елемент x ∈ A - B, такий що B ∪ {x} ∈ I.

Доведемо, що в розглянутому прикладі множина лінійно незалежних стовпців дійсно є матроїдом. Для цього достатньо довести третю властивість з визначення матроїда. Проведемо доведення методом від протилежного.

Доведення. Нехай A, B ∈ I і | A | = | B | + 1. Нехай W буде простором векторів, які охоплюють A ∪ B. Зрозуміло, що його розмірність буде не меншою | A |. Припустимо, що B ∪ {x} буде лінійно залежною для всіх x ∈ A - B (тобто третя властивість не буде виконуватися). Тоді B утворює базис в просторі W. З цього випливає, що | A | ≤ dim W ≤ | B |. Але, так як за умовою A і B складаються з лінійно незалежних векторів і | A |> | B |, одержуємо суперечність. Така множина векторів буде матроїдом.

Додаткові поняття[ред.ред. код]

  • Двоїстим до даного матроїду називається матроїд, носій якого збігається з носієм даного матроїда, а бази - з доповненням баз даного матроїда до носія. Тобто X* = X, а безліч баз двоїстого матроїда - це множина таких B*, що B* = X\B, де B - база даного матроїда.
  • Циклом в матроїді називається така множина A ⊂ X, що A ∉ I, і для будь-якого B ⊂ A, якщо B ≠ A, то B ∈ I
  • Рангом матроїда називається потужність його баз. Ранг тривіального матроїда дорівнює нулю.

Матроїд Фано[ред.ред. код]

Матроїд Фано

Матроїди з невеликим числом елементів часто зображують у вигляді діаграм. Точки - це елементи основної множини, а криві «протягнуті» через кожен трьохелементний ланцюг (3-element circuit). Діаграма показує 3-ранговий матроїд, званий матроїдом Фано, приклад якого з'явився в 1935 в статті Уїтні (Whitney).

Назва виникла з того факту, що матроїд Фано являє собою проективну площину другого порядку, відому як площина Фано, чиє координатне поле - це двохелементне поле. Це означає, що матроїд Фано - це векторний матроїд, пов'язаний з сімома ненульовими векторами в тривимірному векторному просторі над полем двох елементів.

З проективної геометрії відомо, що матроїд Фано не може бути представлений довільною множиною векторів в дійсному або комплексному векторному просторі (або в будь-якому векторному просторі над полем, характеристики якого відрізняються від 2).

Теореми[ред.ред. код]

  • Всі бази матроїда мають однакову потужність.
  • Матроїд однозначно задається носієм і базами.
  • Цикл не може бути підмножиною іншого циклу
  • Якщо C_1 і C_2 - цикли, то для будь-якого x \in C_1\cap C_2: C_1 \cup C_2 \setminus \{x\} містить цикл
  • Якщо B - база і x \notin B, то B \cup \{x\} містить рівно один цикл.

Застосування[ред.ред. код]

Посилання та примітки[ред.ред. код]

  1. Ф. Харарі Теорія графів стр. 57
  2. а б Ф. Харарі Теорія графів стр. 186