Связь матрицы Кирхгофа и матрицы инцидентности

2011-12-08T17:25:56Z

Berkut:

{{Определение
|definition=
Пусть <tex>G</tex> - произвольный граф. Превратим каждое его ребро в дугу, придав ребру одно из двух возможных направлений. Полученный [[ориентированный граф|орграф]] на том же самом множестве вершин будем называть '''ориентацией''' графа <tex>G</tex>.
}}

{{Лемма
|statement=
Пусть <tex>K</tex>- матрица Кирхгофа графа <tex>G</tex>, <tex>I</tex>- матрица инцидентности <tex>G</tex> с некоторой ориентацией. Тогда
<tex>K = I \cdot I^T.</tex>

|proof=
При умножении <tex>i</tex>-й строки исходной матрицы <tex>I</tex> на <tex>j</tex>-й столбец транспонированной матрицы <tex>I^T </tex> перемножаются <tex>i</tex>-я и <tex>j</tex>-я строки исходной матрицы. При умножении <tex>i</tex>-й строки на саму себя на диагонали полученной матрицы получится сумма квадратов элементов <tex>i</tex>-й строки, которая равна, очевидно, <tex>deg(v_i)</tex>. Пусть теперь <tex>i \ne j</tex>. Если <tex> (v_i, v_j) \in E </tex>, то существует ровно одно ребро, соединяющее <tex> v_i </tex> и <tex> v_j </tex>, следовательно результат перемножения <tex>i</tex>-й и <tex>j</tex>-й строк равен -1, в противном случае он равен 0 в силу отсутствия ребра, инцидентного обеим вершинам. Определенная данными условиями матрица и является матрицей Кирхгофа.
}}
{|class="wikitable"
!Граф
!Матрица Кирхгофа
!Матрица инцидентности
|-
|[[Файл:Kirhgof.png|175px]]
|<tex>\left(\begin{array}{rrrrrr}
2 & -1 & 0 & 0 & -1 & 0\\
-1 & 3 & -1 & 0 & -1 & 0\\
0 & -1 & 2 & -1 & 0 & 0\\
0 & 0 & -1 & 3 & -1 & -1\\
-1 & -1 & 0 & -1 & 3 & 0\\
0 & 0 & 0 & -1 & 0 & 1\\
\end{array}\right)</tex>
|<tex>\begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 0 & 0\\
1 & 1 & 0 & 0 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{pmatrix}</tex>
|}

==Источники==

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.

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

Коды Прюфера

2011-11-29T12:36:19Z

Berkut: /* Пример декодирования кода Прюфера */

== Коды Прюфера. ==
Кодирование Прюфера переводит помеченные деревья порядка <tex>n</tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
Пока количество вершин больше одной {
1. Выбирается лист <tex>v</tex> с минимальным номером.
2. В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>.
3. Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
}
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.

{{Лемма
|statement=
Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом или <tex>v</tex> имеет номер <tex>n</tex>.
|proof=
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
# Если вершина не является листом, то у неё на некотором шаге была смежная вершина - лист, следовательно номер этой вершины встречается в коде.
# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален ее сосед, следовательно ее номер не встречается в коде.

Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные - нет.
}}

{{Лемма
|statement=
По любой последовательности длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево,
для которого эта последовательность является кодом Прюфера.
|proof=
Доказательство проведем по индукции.
База. <tex>n = 1</tex> - верно.
 
Переход от <tex>n</tex> к <tex>n + 1</tex>.
 
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. По предыдущей лемме <tex>v</tex> - вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.
}}

{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
# Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
# Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.
}}

Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].

== Пример построения кода Прюфера ==
[[Файл: Prufer.png|500px]]

== Пример декодирования кода Прюфера ==
[[Файл: backprufer.png|700px]]

== Источники ==
[http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]

Коды Прюфера

2011-11-29T12:35:54Z

Berkut:

== Коды Прюфера. ==
Кодирование Прюфера переводит помеченные деревья порядка <tex>n</tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
Пока количество вершин больше одной {
1. Выбирается лист <tex>v</tex> с минимальным номером.
2. В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>.
3. Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
}
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.

{{Лемма
|statement=
Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом или <tex>v</tex> имеет номер <tex>n</tex>.
|proof=
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
# Если вершина не является листом, то у неё на некотором шаге была смежная вершина - лист, следовательно номер этой вершины встречается в коде.
# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален ее сосед, следовательно ее номер не встречается в коде.

Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные - нет.
}}

{{Лемма
|statement=
По любой последовательности длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево,
для которого эта последовательность является кодом Прюфера.
|proof=
Доказательство проведем по индукции.
База. <tex>n = 1</tex> - верно.
 
Переход от <tex>n</tex> к <tex>n + 1</tex>.
 
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. По предыдущей лемме <tex>v</tex> - вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.
}}

{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
# Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
# Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.
}}

Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].

== Пример построения кода Прюфера ==
[[Файл: Prufer.png|500px]]

== Пример декодирования кода Прюфера ==
[[Файл: backprufer.png|500px]]

== Источники ==
[http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]

Файл:Backprufer.png

2011-11-29T12:34:58Z

Berkut:

Коды Прюфера

2011-11-29T12:15:46Z

Berkut: /* Пример построения кода Прюфера */

== Коды Прюфера. ==
Кодирование Прюфера переводит помеченные деревья порядка <tex>n</tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
Пока количество вершин больше одной {
1. Выбирается лист <tex>v</tex> с минимальным номером.
2. В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>.
3. Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
}
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.

{{Лемма
|statement=
Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом или <tex>v</tex> имеет номер <tex>n</tex>.
|proof=
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
# Если вершина не является листом, то у неё на некотором шаге была смежная вершина - лист, следовательно номер этой вершины встречается в коде.
# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален ее сосед, следовательно ее номер не встречается в коде.

Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные - нет.
}}

{{Лемма
|statement=
По любой последовательности длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево,
для которого эта последовательность является кодом Прюфера.
|proof=
Доказательство проведем по индукции.
База. <tex>n = 1</tex> - верно.
 
Переход от <tex>n</tex> к <tex>n + 1</tex>.
 
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. По предыдущей лемме <tex>v</tex> - вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.
}}

{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
# Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
# Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.
}}

Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].

== Пример построения кода Прюфера ==
[[Файл: Prufer.png|500px]]

== Источники ==
[http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]

Коды Прюфера

2011-11-29T12:15:27Z

Berkut:

== Коды Прюфера. ==
Кодирование Прюфера переводит помеченные деревья порядка <tex>n</tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
Пока количество вершин больше одной {
1. Выбирается лист <tex>v</tex> с минимальным номером.
2. В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>.
3. Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
}
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.

{{Лемма
|statement=
Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом или <tex>v</tex> имеет номер <tex>n</tex>.
|proof=
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
# Если вершина не является листом, то у неё на некотором шаге была смежная вершина - лист, следовательно номер этой вершины встречается в коде.
# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален ее сосед, следовательно ее номер не встречается в коде.

Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные - нет.
}}

{{Лемма
|statement=
По любой последовательности длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево,
для которого эта последовательность является кодом Прюфера.
|proof=
Доказательство проведем по индукции.
База. <tex>n = 1</tex> - верно.
 
Переход от <tex>n</tex> к <tex>n + 1</tex>.
 
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. По предыдущей лемме <tex>v</tex> - вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.
}}

{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
# Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
# Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.
}}

Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].

== Пример построения кода Прюфера ==
[[Файл: Prufer.png|200px]]

== Источники ==
[http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]

Коды Прюфера

2011-11-29T12:14:04Z

Berkut:

== Коды Прюфера. ==
Кодирование Прюфера переводит помеченные деревья порядка <tex>n</tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
Пока количество вершин больше одной {
1. Выбирается лист <tex>v</tex> с минимальным номером.
2. В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>.
3. Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева.
}
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.

Пример построения кода Прюфера
[[Файл: Prufer.png]]

{{Лемма
|statement=
Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом или <tex>v</tex> имеет номер <tex>n</tex>.
|proof=
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
# Если вершина не является листом, то у неё на некотором шаге была смежная вершина - лист, следовательно номер этой вершины встречается в коде.
# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален ее сосед, следовательно ее номер не встречается в коде.

Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные - нет.
}}

{{Лемма
|statement=
По любой последовательности длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево,
для которого эта последовательность является кодом Прюфера.
|proof=
Доказательство проведем по индукции.
База. <tex>n = 1</tex> - верно.
 
Переход от <tex>n</tex> к <tex>n + 1</tex>.
 
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. По предыдущей лемме <tex>v</tex> - вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.
}}

{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
# Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
# Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.
}}

Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].

== Источники ==
[http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]

2011-11-29T11:04:20Z

Berkut:

== Определение матрицы Кирхгофа ==

{{Определение
|definition=
'''Матрицей Кирхгофа''' простого графа <tex>G = (V,E) </tex> называется матрица <tex> K (|V| \times |V|) = \parallel k_{i,j} \parallel </tex>, элементы которой определяются равенством: <tex>
k_{i,j} =
\begin{cases}
\deg(v_i), \ i = j \\
-1, \ (v_i,v_j) \in E \\
0, \mbox{ else}.
\end{cases}
</tex>
}}
Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении i-й строки и j-го столбца (<tex>i \ne j</tex>) стоит -1, если вершины с номерами i и j смежны, и 0 в противном случае.

== Пример матрицы Кирхгофа==
Пример матрицы Кирхгофа простого графа.
{|class="wikitable"
![[Помеченный граф]]
!Матрица Кирхгофа
|-
|[[image:6n-graf.svg|175px]]
|<math>\left(\begin{array}{rrrrrr}
2 & -1 & 0 & 0 & -1 & 0\\
-1 & 3 & -1 & 0 & -1 & 0\\
0 & -1 & 2 & -1 & 0 & 0\\
0 & 0 & -1 & 3 & -1 & -1\\
-1 & -1 & 0 & -1 & 3 & 0\\
0 & 0 & 0 & -1 & 0 & 1\\
\end{array}\right)</math>
|}

== Некоторые свойства ==

1) Матрица Кирхгофа является симметрической (т.е. симметрична относительно главной диагонали).

2) Связь с матрицей смежности:

<tex> K =
\begin{pmatrix}
deg(v_1) & 0 & \cdots & 0 \\
0 & deg(v_2) & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & deg(v_n)
\end{pmatrix} - A,
</tex>

где <tex>A</tex> - матрица смежности графа <tex>G</tex>.

3) [[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]: <tex> K = I \cdot I^T, </tex> где <tex>I</tex> - матрица инцидентности с некоторой ориентацией.

==Источники==

Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.

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