Викиконспекты - Вклад участника [ru]

Остовные деревья: определения, лемма о безопасном ребре

2015-06-13T14:32:56Z

88.201.190.136: /* Лемма о безопасном ребре */

[[Файл:MST-example.png|right|thumb|200px|Пример минимального остовного дерева.]]
==Необходимые определения==
Рассмотрим связный неориентированный взвешенный [[Основные определения теории графов|граф]] <tex> G =( V, E ) </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|ребер]]. Вес ребра определяется, как функция <tex> w : E \to \mathbb{R} </tex>.
{{Определение
|neat = 1
|definition =
'''Остовное дерево''' (англ. ''spanning tree'') графа <tex> G = ( V, E ) </tex> {{---}} ациклический связный подграф данного связного неориентированного графа.
}}
{{Определение
|definition =
'''Минимальное остовное дерево''' (англ. ''minimum spanning tree'') графа <tex> G = ( V, E ) </tex> {{---}} это его ациклический связный подграф, в который входят все его вершины, обладающий минимальным суммарным весом ребер.
}}
Заметим, что граф может содержать несколько минимальных остовных деревьев.
Для формулировки и доказательства леммы о безопасном ребре рассмотрим следующие определения.

Пусть <tex>G'</tex> {{---}} подграф некоторого минимального остовного дерева графа <tex> G = ( V, E ) </tex>.
{{Определение
|definition =
Ребро <tex> ( u, v ) \notin G' </tex> называется '''безопасным''' (англ. ''safe edge''), если при добавлении его в <tex> G' </tex>, <tex> G' \cup \{ ( u, v ) \}</tex> также является подграфом некоторого минимального остовного дерева графа <tex> G </tex>.
}}{{Определение
|definition =
'''Разрезом''' (англ. ''cut'') неориентированного графа <tex> G = ( V, E ) </tex> называется разбиение <tex> V </tex> на два непересекающихся подмножества: <tex> S </tex> и <tex> T = V \setminus S </tex>. Обозначается как <tex> \langle S, T \rangle </tex>.
}}{{Определение
|definition =
Ребро <tex> ( u, v ) \in E </tex> '''пересекает''' (англ. ''crosses'') разрез <tex> \langle S, T \rangle </tex>, если один из его концов принадлежит множеству <tex> S </tex>, а другой {{---}} множеству <tex> T </tex>.
}}

==Лемма о безопасном ребре==
{{Теорема
|statement=
Рассмотрим связный неориентированный взвешенный граф <tex> G = ( V, E ) </tex> с весовой функцией <tex>w : E \to \mathbb{R}</tex>. Пусть <tex> G' = ( V, E' ) </tex> {{---}} подграф некоторого минимального остовного дерева <tex> G </tex>, <tex> \langle S, T \rangle </tex> {{---}} разрез <tex> G </tex>, такой, что ни одно ребро из <tex> E' </tex> не пересекает разрез, а <tex> ( u, v ) </tex> {{---}} ребро минимального веса среди всех ребер, пересекающих разрез <tex> \langle S, T \rangle </tex>. Тогда ребро <tex> e = ( u, v ) </tex> является безопасным для <tex> G'</tex>.
|proof=
[[Файл:Лемма_о_безопасном_ребре.png‎|right|thumb|300px]]
Достроим <tex> E' </tex> до некоторого минимального остовного дерева, обозначим его <tex>T_{min}</tex>. Если ребро <tex>e \in T_{min}</tex>, то лемма доказана, поэтому рассмотрим случай, когда ребро <tex>e \notin T_{min}</tex>. Рассмотрим путь в <tex>T_{min}</tex> от вершины <tex>u</tex> до вершины <tex>v</tex>. Так как эти вершины принадлежат разным долям разреза, то хотя бы одно ребро пути пересекает разрез, назовем его <tex>e'</tex>. По условию леммы <tex>w(e) \leqslant w(e')</tex>. Заменим ребро <tex>e'</tex> в <tex>T_{min}</tex> на ребро <tex>e</tex>. Полученное дерево также является минимальным остовным деревом графа <tex>G</tex>, поскольку все вершины <tex>G</tex> по-прежнему связаны и вес дерева не увеличился. Следовательно <tex>E' \cup \{e\} </tex> можно дополнить до минимального остовного дерева в графе <tex>G</tex>, то есть ребро <tex>e</tex> {{---}} безопасное.
}}

==Cм. также==
*[[Алгоритм Прима]]
*[[Алгоритм Краскала]]
*[[Алгоритм Борувки]]

==Источники информации==
* Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. {{---}} Алгоритмы. Построение и анализ : Вильямс, 2-е издание, 2005, С. 644-649

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]

Матричное представление перестановок

2015-06-13T06:58:34Z

88.201.190.136: /* Свойства */

== Определение ==
{{Определение
|definition=
'''Матрица перестановки''' — квадратная бинарная матрица, в каждой строке и в каждом столбце которой находится лишь одна единица.}}
{{Определение
|definition=
Если матрица перестановок <tex>P</tex> получена из единичной матрицы <tex>E</tex> перестановкой местами двух строк (или двух столбцов), то такая матрица называется '''элементарной матрицей перестановок'''. }}

Каждая матрица перестановки размера <tex>n \times n</tex> является матричным представлением перестановки порядка <tex>n</tex>.

Пусть дана перестановка <tex>\sigma</tex> порядка <tex>n</tex>:
: <tex>\begin{pmatrix}
1 & 2& \ldots & n\\
\sigma(1)& \sigma(2) & \ldots & \sigma(n)
\end{pmatrix}</tex>

Соответствующей матрицей перестановки является матрица <tex>n \times n</tex> вида:
: <tex>P_\sigma = \begin{pmatrix}
\mathbf{e}_{\sigma(1)}\\
\mathbf{e}_{\sigma(2)}\\
\vdots \\
\mathbf{e}_{\sigma(n)}
\end{pmatrix}</tex>, где <tex>\mathbf{e}_{i}</tex> — двоичный вектор длины <tex>n</tex>, <tex>i</tex>-й элемент которого равен единице, а остальные равны нулю.

== Пример ==

Перестановка:
: <tex>\pi = \begin{pmatrix}
1 & 2 & 3\\
1 & 3 & 2
\end{pmatrix}</tex>

Соответствующая матрица:
: <tex>P = \begin{pmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{pmatrix}</tex>

== Свойства ==

{{Утверждение
|statement=Для любых двух перестановок <tex>\sigma, \pi</tex> их матрицы обладают свойством:

<center><tex>P_\sigma P_\pi = P_{\pi \circ \sigma}</tex></center>

где <tex>\circ</tex> - операция [[Умножение перестановок, обратная перестановка, группа перестановок| умножения двух перестановок]].
|proof=
Рассмотрим <tex>{(P_\sigma P_\pi)}_{i,j} = \sum\limits_{x = 1}^{n}{({P_\sigma}_{i,x} {P_\pi}_{x,j})}</tex>

эта сумма может быть равна нулю или единице, причем единице в том случае, если в <tex>i</tex> - той строчке на <tex>k</tex> - том столбце матрицы <tex>P_\sigma</tex> и в <tex>k</tex> - той строчке на <tex>j</tex> - том столбце матрицы <tex>P_\pi</tex> стоят единицы. <tex>{P_\sigma}_{i,k} = 1</tex> значит, что в перестановке <tex>\sigma</tex> на <tex>i</tex> - том месте стоит элемент <tex>k</tex>, и <tex>{P_\pi}_{k,j} = 1</tex> означает что в перестановке <tex>\pi</tex> на <tex>k</tex> - том месте стоит элемент <tex>j</tex>, а <tex>{(P_\sigma P_\pi)}_{i,j} = 1</tex> означает что в перестановке, которой соответствует эта матрица, так же на <tex>i</tex> - том месте стоит элемент <tex>j</tex>. Но также известно, что <tex> (\pi \circ \sigma)(i) = \pi(\sigma(i)) = j </tex>. В результате если <tex>{(P_\sigma P_\pi)}_{i,j} = 1</tex>, то <tex>({P_{\pi \circ \sigma}})_{i,j} = 1</tex>. Аналогичные рассуждения можно провести когда <tex>{(P_\sigma P_\pi)}_{i,j} = 0</tex>, и также получим, что <tex>({P_{\pi \circ \sigma}})_{i,j} = 0</tex>. Поэтому для любых <tex>i,j</tex> справедливо <tex>{(P_\sigma P_\pi)}_{i,j} = ({P_{\pi \circ \sigma}})_{i,j}</tex>, а раз такое равентсво выполняется, то <tex>P_\sigma P_\pi = P_{\pi \circ \sigma}</tex>.
}}
{{Утверждение
|statement=
Для любой матрицы перестановок существует обратная:
<center><tex>P_\sigma^{-1} = P_\sigma^T</tex></center>
где <tex>P^T</tex> - транспонированная матрица <tex>P</tex>.
|proof=
Так как перестановки являются группой, то для любой перестановки существует обратная. Так как любая перестановка имеет свою матрицу перестановки, то утверждение о существовании обратной матрицы перестановки также справедливо.
}}
{{Утверждение|statement=Для любой матрицы перестановок <tex>P</tex> справедливо:
<center><tex>P^T P = P P^T = E</tex></center> где <tex>E</tex> - единичная матрица.
|proof=
Также следует из того, что перестановки являются группой.}}

{{Утверждение|statement=Произведение матриц перестановок есть матрица перестановок.
|proof=
Произведение перестановок есть перестановка, значит и произведение матриц перестановок есть матрица перестановок.}}

{{Утверждение|statement=
Умножение произвольной матрицы <tex>A</tex> на перестановочную соответственно меняет местами её столбцы.
Умножение перестановочной матрицы на произвольную <tex>A</tex> меняет местами строки в <tex>A</tex>.
|proof=
Рассмотрим произвольную матрицу <tex>A</tex> и матрицу перестановки <tex>P</tex>:
возьмем <tex>i</tex> - тую строчку матрицы <tex>A</tex> и умножим на <tex>j</tex> - тый столбец <tex>P</tex>,
так как <tex>j</tex> - тый столбец матрицы <tex>P</tex> это двоичный вектор с одной единицей, то от <tex>i</tex> - той строчки матрицы <tex>A</tex> выживет один элемент, причем на <tex>j</tex> - том месте.
Умножив <tex>i</tex> - тую строчку матрицы <tex>A</tex>, на остальные столбцы матрицы <tex>P</tex>, получим, что в <tex>i</tex> - той строке матрицы <tex>A</tex> элементы поменяются местами. Умножая другие строки матрицы <tex>A</tex>, будем наблюдать похожее (так как умножаем на те же самые столбцы матрицы <tex>P</tex>). Таким образом получим, что в матрице <tex>A</tex> столбцы поменялись местами.

Доказательство второго утверждения аналогично.
}}

{{Утверждение|statement=Квадрат элементарной матрицы перестановок есть единичная матрица.
}}

{{Утверждение|statement=Матрица перестановок <tex>n</tex>-го порядка может быть представлена в виде произведения <tex>(n - 1)</tex> элементарных матриц перестановок.
}}

== Применение ==

Благодаря своим свойствам, матрицам перестановок нашлось применение в линейной алгебре:

пусть задана матрица перестановки <tex>P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix}</tex>, которая соответствует перестановке <tex>\pi = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}</tex>, и матрица <tex>A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix}</tex>,

тогда перемножив получим:

* <tex>PA = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix} \times \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 7 & 8 & 9 \\ 4 & 5 & 6 \\ \end{pmatrix}</tex>,

видно, что вторая и третья строки поменялись местами;

* <tex>AP = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{pmatrix} \times \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ \end{pmatrix} = \begin{pmatrix} 1 & 3 & 2 \\ 4 & 6 & 5 \\ 7 & 9 & 8 \\ \end{pmatrix}</tex>,

видно, что второй и третий столбец поменялись местами.

== Ссылки ==
*[http://ru.wikipedia.org/wiki/Матрица_перестановки Матрица перестановки — Википедия]
*[http://portal.tpu.ru/SHARED/k/KONVAL/Sites/Russian_sites/1/23.htm Матрица перестановки]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]