Граф замен — различия между версиями
Shevchen (обсуждение | вклад) м |
м (rollbackEdits.php mass rollback) |
||
(не показано 45 промежуточных версий 10 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Граф замен''' - специальный ориентированный двудольный граф, фигурирующий в [[Теорема Эдмондса-Лоулера|теореме Эдмондса-Лоулера]]. | + | '''Граф замен''' (англ ''exchange graph'') {{---}} специальный [[Основные определения теории графов|ориентированный двудольный граф]], фигурирующий в [[Теорема Эдмондса-Лоулера|теореме Эдмондса-Лоулера]]. |
− | + | Пусть даны матроиды <tex>M_1 = \langle S, \mathcal{I}_1 \rangle</tex>, <tex>M_2 = \langle S, \mathcal{I}_2 \rangle</tex>, множество <tex>(\mathcal{I}_1 \cap \mathcal{I}_2)</tex>. Введем граф замен. | |
+ | {{Определение | ||
+ | |definition = | ||
+ | '''Граф замен для двух матроидов''' <tex>D_{M_1, M_2}(I)</tex> {{---}} граф, левой долей которого являются элементы множества <tex>I</tex>, правой — все остальные элементы <tex>S</tex> и в котором проведены ребра <tex>(y, z): y \in I, z \in S \setminus I, I \setminus y \cup z \in \mathcal{I}_1</tex>, а также <tex>(z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in \mathcal{I}_2</tex> | ||
+ | }} | ||
− | Пусть <tex>I</tex> | + | Пусть <tex>X_1 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_2 \}, P</tex> — кратчайший путь в <tex>D_{M_1, M_2}(I)</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности. |
+ | [[Файл:Graph_DY.png|400px|thumb|center|Граф замен <tex>D_{M_1, M_2}(I)</tex>]] | ||
− | <tex>( | + | Также существует граф замен для одного матроида. |
+ | {{Определение | ||
+ | |id=def_2 | ||
+ | |definition = | ||
+ | Пусть дан матроид <tex>M = (S, \mathcal{I})</tex> и независимый сет <tex>I \in \mathcal{I}</tex>. Тогда '''граф замен''' <tex>D_{M}(I)</tex> (или просто <tex>D(I)</tex>) {{---}} это двудольный граф с долями <tex>I</tex> и <tex>S \setminus I</tex> с рёбрами между <tex>y \in I</tex> и <tex>x \in S \setminus I</tex> если <tex> I - y + x \in \mathcal{I} </tex> | ||
+ | }} | ||
− | + | {{Лемма | |
+ | |id= ==lemma== | ||
+ | |about=о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем | ||
+ | |statement = | ||
+ | Пусть дан двудольный граф замен. В его правой доле выделено два подмножества вершин <tex>X_1 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_2 \}</tex>. <tex>P</tex> {{---}} кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. | ||
+ | <br><tex>G'</tex> {{---}} подграф <tex>G</tex>, включающий множество вершин, лежащих на пути <tex>P</tex>. Тогда в <tex>G'</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]]. | ||
+ | |proof = | ||
+ | [[Файл:Граф_индуцированный_кратчайшим_путем.png | thumb | left | Рис. 1]] | ||
+ | [[Файл:Фрагмент_паросочетания.png | thumb | right | Рис. 2]] | ||
+ | :Так как в правой доле полученного графа <tex>G'</tex> вершин на одну больше, чем в левой, добавим в <tex>G'</tex> фиктивную вершину и отнесем ее к левой доле. | ||
+ | :Рассмотрим <tex>P = (a_1, b_1, a_2, b_2, \ldots , a_k, b_k)</tex> {{---}} кратчайший путь из условия, где <tex>a_1</tex> {{---}} фиктивная вершина (рис. 1). | ||
+ | :В таком случае, полное паросочетание {{---}} это набор ребер <tex>\langle a_i,b_i \rangle</tex>. | ||
− | <tex> | + | Докажем единственность. |
+ | :Пусть существует другое паросочетание <tex>\langle a_i, b_{j_i} \rangle</tex>. Тогда пусть <tex>i_0 = \min \{ i \: \mid \: j_i < i \}</tex>. | ||
+ | :Обозначим <tex>j_{i_0}</tex> как <tex>i_1</tex>. Заметим, что <tex>i_1 < i_0</tex> (так как <tex>j_{i_0} < i_0 </tex> по определению <tex>i_0</tex>) и поэтому не может быть <tex>j_{i_1} < j_{i_0}</tex>, ведь <tex>i_0</tex> — минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = j_{i_0}</tex>, поскольку тогда <tex>a_{i_0}</tex> и <tex>a_{i_1}</tex> имели бы одинаковую пару. | ||
+ | :Следовательно, <tex>j_{i_1} > j_{i_0}</tex> (рис. 2). Это значит, что существует путь <tex>P_1 = (a_1, b_1, \ldots, a_{i_1}, b_{j_{i_1}}, a_{j_{i_1} + 1}, \ldots, a_k, b_k )</tex> короче, чем <tex>P</tex>, что противоречит тому, что <tex>P</tex> {{---}} кратчайший путь. | ||
+ | }} | ||
− | |||
− | == | + | {{Лемма |
− | ''Chandra Chekuri | + | |about= |
+ | о паросочетании в графе замен | ||
+ | |statement= Пусть <tex>M = \langle X,\mathcal{I} \rangle </tex> — [[Определение матроида|матроид]]. Множества <tex>A, B \in \mathcal{I}</tex> {{---}} независимы, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>D_{M}(A)</tex> содержит полное паросочетание на <tex>A \bigtriangleup B</tex>. | ||
+ | |proof= | ||
+ | |||
+ | Индукция по <tex>|A \bigtriangleup B|</tex>. | ||
+ | |||
+ | * '''База | ||
+ | :При <tex>|A \bigtriangleup B| = 0 </tex> имеем пустое паросочетание. | ||
+ | |||
+ | * '''Переход | ||
+ | :Пусть верно для <tex>|A \bigtriangleup B| = N</tex>. | ||
+ | :Пусть <tex>k = |A| = |B|</tex> и <tex>|A \bigtriangleup B| \geqslant 1</tex>. | ||
+ | :Рассмотрим матроид <tex>M_1 = \langle X, \{ A \mid A \in \mathcal{I}, |A| \leqslant k \} \rangle</tex>. Множества <tex>A, B \in \mathcal{I}</tex>, <tex>|A| = |B|</tex> и матроид <tex>M_1</tex> не содержит множеств больших, чем <tex>A</tex>, а значит они являются базами для матроида <tex>M_1</tex>. | ||
+ | :По [[Теорема о базах|сильной теореме о базах]]: <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y \in \mathcal{I}</tex> и <tex>(B \setminus y) \cup x \in \mathcal{I}</tex> | ||
+ | :Из этого следует, что множества <tex>A' = (A \setminus x) \cup y </tex> и <tex>B' = (B \cup x) \setminus y</tex> являются независимыми, а также базами <tex>M_1</tex>. Заметим, что <tex>|A' \bigtriangleup B'| < |A \bigtriangleup B|</tex>, <tex>|A' \bigtriangleup B'| = N</tex>, <tex>|A \bigtriangleup B| = N+1 </tex>. По предположению индукции у <tex> |A' \bigtriangleup B'|</tex> есть полное паросочетание. | ||
+ | :По [[Теорема о базах|теореме о базах]] <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y | ||
+ | \in \mathcal{I}</tex>, следовательно по определению графа <tex>D_M(A), (x, y) \in D_M(A)</tex>. Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>. Индукционный переход доказан. | ||
+ | |||
+ | }} | ||
+ | |||
+ | ==Лемма о единственном паросочетании в графе замен== | ||
+ | {{Утверждение | ||
+ | |statement=Пусть [[Двудольные_графы_и_раскраска_в_2_цвета|двудольный граф]] <tex>G</tex> содержит единственное [[Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольных_графах#Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольном_графе|полное паросочетание]] <tex>M</tex>. Тогда можно упорядочить вершины левой <tex>(a_i \in A)</tex> и правой <tex>(b_i \in B)</tex> долей таким образом, что <tex>\forall j > i : (a_i b_j) \notin G</tex>. При этом рёбра паросочетания будут иметь вид <tex>(a_i b_i)</tex>. | ||
+ | |||
+ | |proof=Индукция по <tex>|A|</tex>.<br/> | ||
+ | * '''База | ||
+ | : При <tex>|A|=1</tex> утверждение очевидно. <br/> | ||
+ | * '''Переход | ||
+ | : Пусть верно для <tex>|A|=n-1</tex>. | ||
+ | : Рассмотрим <tex>|A|=n>1</tex>. Возьмем произвольную вершину в левой доле. Будем строить из неё [[Теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|чередующуюся цепь]], добавляя по очереди ребро, входящее в <tex>M</tex>, и ребро, не входящее в <tex>M</tex>. Заметим, что такой путь не содержит циклов (циклы нечётной длины невозможны, так как граф двудольный, циклы чётной длины отсутствуют из-за единственности паросочетания). Если последнее добавленное ребро не принадлежит <tex>M</tex>, то присоединим к цепи ребро из <tex>M</tex>, инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из <tex>M</tex> при достижении вершины [[Основные определения теории графов#Степень вершины|степени]] <tex>1</tex>. <br/> | ||
+ | :Таким образом, последнее ребро в цепи имеет вид <tex>\langle a, b \rangle \in M</tex>, где <tex>a \in A, b \in B, \deg b = 1</tex>. Положим <tex>a_n=a, b_n=b</tex>. Для <tex>G \setminus \{a_n \cup b_n \}</tex> утверждение верно по предположению индукции. С другой стороны, так как <tex>\deg b_n = 1</tex>, то <tex> \langle a_i, b_n \rangle \notin G</tex> при <tex>i<n</tex>, поэтому для <tex>j = n</tex> утверждение также верно.<br/> | ||
+ | }} | ||
+ | |||
+ | |||
+ | {{Лемма | ||
+ | |about= | ||
+ | о единственном паросочетании в графе замен | ||
+ | |statement= Дан [[Определение матроида|матроид]] <tex>M = \langle X,I \rangle </tex>. Пусть двудольный граф <tex>G_M(A) = \{ (x, y) \mid x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> содержит единственное полное паросочетание на <tex>A \bigtriangleup B</tex>, где <tex>A\in I</tex> и <tex>|A| = |B|</tex>. Тогда <tex>B \in I</tex>. | ||
+ | |proof= | ||
+ | [[Файл:Graph replacement.png|thumb|left|160px|]] | ||
+ | |||
+ | Упорядочим вершины левой <tex>(y_i \in A \setminus B)</tex> и правой <tex>(z_j \in B \setminus A)</tex> долей таким образом, что <tex>\forall j > i : \langle y_i, z_j \rangle \notin G_M(A)</tex>. При таком упорядочивании ребра паросочетания имеют вид <tex> \langle y_i, z_i \rangle</tex>. | ||
+ | :Требуется доказать, что <tex>B</tex> независимо. | ||
+ | :Предположим обратное. Пусть <tex>B \notin I</tex>. Tогда существует [[Теорема о циклах|цикл]] <tex>C \subset B</tex>.<br/> Выберем минимальное <tex>i</tex> такое, что <tex>z_i \in C</tex>. Так как <tex>\forall j > i : \langle y_i, z_j \rangle \notin G_M(A)</tex>, то <tex>A \setminus y_i \cup z_j \notin I</tex>. Cледовательно, <tex>C \setminus z_i \subset \langle A \setminus y_i \rangle </tex>. | ||
+ | |||
+ | :По [[Оператор замыкания для матроидов#theorem|свойствам замыкания 1 и 3]] получаем: | ||
+ | <tex>C \setminus z_i \subset \langle A \setminus y_i \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle \langle A \setminus y_i \rangle \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex> <br/> | ||
+ | Так как <tex>z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex>, то <tex>A \setminus y_i \cup z_i \notin I</tex>, то есть в <tex>G_M(A)</tex> не существует ребра <tex>\langle y_i, z_i \rangle</tex>. | ||
+ | :Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие. | ||
+ | }} | ||
+ | |||
+ | ==См. также== | ||
+ | * [[Пересечение матроидов, определение, примеры]] | ||
+ | * [[Алгоритм построения базы в пересечении матроидов]] | ||
+ | |||
+ | == Источники информации == | ||
+ | *[https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture17.pdf Chandra Chekuri — Combinatorial Optimization] | ||
+ | *[http://math.mit.edu/~goemans/18438F09/lec11.pdf Michel X. Goemans — Matroid Intersection] | ||
+ | *[http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture16.pdf '''Chandra Chekuri — Combinatorial Optimization], с. 6 | ||
+ | |||
+ | |||
+ | [[Категория:Алгоритмы и структуры данных]] | ||
+ | [[Категория:Матроиды]] | ||
+ | [[Категория:Пересечение матроидов]] |
Текущая версия на 19:33, 4 сентября 2022
Граф замен (англ exchange graph) — специальный ориентированный двудольный граф, фигурирующий в теореме Эдмондса-Лоулера.
Пусть даны матроиды
, , множество . Введем граф замен.Определение: |
Граф замен для двух матроидов | — граф, левой долей которого являются элементы множества , правой — все остальные элементы и в котором проведены ребра , а также
Пусть — кратчайший путь в из в . Тогда алгоритм с помощью этого пути либо определяет максимальность набора , либо позволяет найти набор большей мощности.
Также существует граф замен для одного матроида.
Определение: |
Пусть дан матроид | и независимый сет . Тогда граф замен (или просто ) — это двудольный граф с долями и с рёбрами между и если
Лемма (о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем): |
Пусть дан двудольный граф замен. В его правой доле выделено два подмножества вершин . — кратчайший путь из в .
— подграф , включающий множество вершин, лежащих на пути . Тогда в существует единственное полное паросочетание. |
Доказательство: |
Докажем единственность.
|
Лемма (о паросочетании в графе замен): |
Пусть матроид. Множества — независимы, причем . Тогда двудольный граф содержит полное паросочетание на . — |
Доказательство: |
Индукция по .
|
Лемма о единственном паросочетании в графе замен
Утверждение: |
Пусть двудольный граф содержит единственное полное паросочетание . Тогда можно упорядочить вершины левой и правой долей таким образом, что . При этом рёбра паросочетания будут иметь вид . |
Индукция по
|
Лемма (о единственном паросочетании в графе замен): |
Дан матроид . Пусть двудольный граф содержит единственное полное паросочетание на , где и . Тогда . |
Доказательство: |
Упорядочим вершины левой и правой долей таким образом, что . При таком упорядочивании ребра паросочетания имеют вид .
|