Матрица Кирхгофа - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:12:33Z

rollbackEdits.php mass rollback

94.16.121.91 в 05:57, 1 сентября 2022

2022-09-01T05:57:09Z

Shersh: /* Источники информации */

2015-09-07T18:00:13Z

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

188.243.62.170 в 20:40, 29 декабря 2014

2014-12-29T20:40:47Z

188.243.62.170 в 20:00, 29 декабря 2014

2014-12-29T20:00:05Z

188.243.62.170 в 19:51, 29 декабря 2014

2014-12-29T19:51:33Z

188.243.62.170 в 17:36, 29 декабря 2014

2014-12-29T17:36:39Z

188.243.62.170 в 16:49, 29 декабря 2014

2014-12-29T16:49:43Z

188.243.62.170 в 13:32, 29 декабря 2014

2014-12-29T13:32:24Z

188.243.62.170 в 13:27, 29 декабря 2014

2014-12-29T13:27:45Z

← Предыдущая		Версия 16:12, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 05:57, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 18:00, 7 сентября 2015
Строка 155:		Строка 155:

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

@@ Строка 48: / Строка 48: @@
 </tex>
-Прибавим к первой строке все остальные строки(это не изменит значение определителя):
+Прибавим к первой строке все остальные строки (это не изменит значение определителя):
 <tex>\begin{vmatrix}
@@ Строка 93: / Строка 93: @@
 {{Утверждение
-|statement=<tex>0</tex> является [[Собственные векторы и собственные значения|собственным значением]] матрицы, кратность его равна числу компонент связности графа.
+|statement=<tex>0</tex> является [[Собственные векторы и собственные значения|собственным значением]] матрицы, кратность его равна числу [[Отношение связности, компоненты связности|компонент связности]] графа.
 |proof=Собственным значением матрицы называют значения <tex>\lambda</tex>, которые удовлетворяют уравнению:
@@ Строка 104: / Строка 104: @@
 </tex>
-Прибавим к первой строке все остальные строки(это не изменит значение определителя):
+Прибавим к первой строке все остальные строки (это не изменит значение определителя):
 <tex>\begin{vmatrix}
@@ Строка 139: / Строка 139: @@
 Пусть дан граф <tex>G</tex> c <tex>n</tex> компонентами связности. Перенумеруем его вершины так, чтобы сначала шли вершины первой компоненты связности, затем второй и т.д. Тогда матрица Кирхгофа примет блочно-диагональный вид, и <tex>i</tex>-тый блок этой матрицы будет являтся матрицей Кирхгофа для <tex>i</tex>-той компоненты связности.
-Из свойства блочно-диагональной матрицы <tex>\det K = \det K_{1} * \det K_{2} * \cdots * \det K_{n}</tex>, где <tex>K_{i}</tex> - матрица Кирхгофа для <tex>i</tex>-той компоненты связности, и свойства, доказанного выше,
+Из свойства блочно-диагональной матрицы <tex>\det K = \det K_{1} \cdot \det K_{2} \cdot \ldots \cdot \det K_{n}</tex>, где <tex>K_{i}</tex> — матрица Кирхгофа для <tex>i</tex>-той компоненты связности, и свойства, доказанного выше,
-(<tex>\det K_{i} = - \lambda * det X_{i} </tex>) следует:
+<tex>\det K_{i} = - \lambda \cdot det X_{i} \quad \Rightarrow \quad \det K = (-1)^{n} \cdot \lambda^{n} \cdot \det X_{1} \cdot \det X_{2} \cdot \ldots \cdot \det X_{n}</tex>
 }}
@@ Строка 154: / Строка 152: @@
 *Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы. стр. 18
-*[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия, Матрица Кирхгофа]
+*[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия — Матрица Кирхгофа]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Остовные деревья ]]

@@ Строка 139: / Строка 139: @@
 Пусть дан граф <tex>G</tex> c <tex>n</tex> компонентами связности. Перенумеруем его вершины так, чтобы сначала шли вершины первой компоненты связности, затем второй и т.д. Тогда матрица Кирхгофа примет блочно-диагональный вид, и <tex>i</tex>-тый блок этой матрицы будет являтся матрицей Кирхгофа для <tex>i</tex>-той компоненты связности.
-По свойству блочно-диагональной матрицы <tex>\det K = \det K_{1} * \det K_{2} * \cdots * \det K_{n}</tex>, где <tex>K_{i}</tex> - матрица Кирхгофа для <tex>i</tex>-той компоненты связности.
+Из свойства блочно-диагональной матрицы <tex>\det K = \det K_{1} * \det K_{2} * \cdots * \det K_{n}</tex>, где <tex>K_{i}</tex> - матрица Кирхгофа для <tex>i</tex>-той компоненты связности, и свойства, доказанного выше,
-из <tex>\det K_{i} = - \lambda * det X_{i} </tex> (по 2 свойству) следует:
+(<tex>\det K_{i} = - \lambda * det X_{i} </tex>) следует:
 <tex>\det K = (-1)^{n} * \lambda^{n} * \det X_{1} * \det X_{2} * \cdots * \det X_{n}</tex>

@@ Строка 31: / Строка 31: @@
 == Некоторые свойства ==
-'''1.''' Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
+{{Утверждение
 : <tex>\ \sum_{i=1}^{|V|} k_{i,j} = 0</tex>.
-'''2.''' Определитель матрицы Кирхгофа равен нулю:
+{{Утверждение
 : <tex>\det K=0</tex>
+|proof=<tex>  \det K =
 \begin{vmatrix}
 k_{1, 1} & k_{1, 2} & \cdots & k_{1, |V|} \\
@@ Строка 67: / Строка 67: @@
 \end{vmatrix} = 0
 </tex>
-'''3.''' Матрица Кирхгофа простого графа симметрична:
+{{Утверждение
 : <tex>\ k_{i,j} = k_{j,i}\quad i,j=1, \ldots, |V|</tex>.
-'''4.''' Связь с [[Матрица смежности графа|матрицей смежности]]:
+{{Утверждение
 :<tex> K =
 \begin{pmatrix}
@@ Строка 81: / Строка 85: @@
 </tex>
 где <tex>A</tex> — матрица смежности графа <tex>G</tex>.
-'''5.''' [[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:
+{{Утверждение
 :<tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
-'''6.''' <tex>0</tex> является собственным значением матрицы.
+}}
-Собственным значением матрицы называют значения <tex>\lambda</tex>, которые удовлетворяют уравнению:
+{{Утверждение
 <tex>\begin{vmatrix}
@@ Строка 102: / Строка 108: @@
 <tex>\begin{vmatrix}
 k_{1, 1} + k_{2, 1} + \cdots + k_{|V|, 1} - \lambda & k_{1, 2} + k_{2, 2} + \cdots + k_{|V|, 2} - \lambda & \cdots & k_{1, |V|} + k_{2, |V|} + \cdots + k_{|V|, |V|} - \lambda \\
-k_{2, 1} & k_{2, 2} & \cdots & k_{2, |V|} \\
+k_{2, 1} & k_{2, 2} - \lambda & \cdots & k_{2, |V|} \\
 \vdots & \vdots & \ddots & \vdots \\
-k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|}
+k_{|V|, 1} & k_{|V|, 2} & \cdots & k_{|V|, |V|} - \lambda
 \end{vmatrix}
 </tex>
@@ Строка 127: / Строка 133: @@
 </tex>
-Следовательно, <tex>0</tex> является собственным значением
+Следовательно, <tex>0</tex> является собственным значением.
 ==См. также==

@@ Строка 53: / Строка 53: @@
 *[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:
 :<tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
-*<tex>0</tex> является собственным значением матрицы, кратность его равна числу связных компонент графа.
+*<tex>0</tex> является собственным значением матрицы, кратность его равна числу компонент связности графа.

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
-'''Матрицей Кирхгофа''' [http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B9_%D0%B3%D1%80%D0%B0%D1%84#.D0.BF.D1.80.D0.BE.D1.81.D1.82.D0.BE.D0.B9_.D0.B3.D1.80.D0.B0.D1.84 простого графа] <tex>G = (V,E) </tex> называется матрица <tex> K (|V| \times |V|) = \parallel k_{i,j} \parallel  </tex>, элементы которой определяются равенством: <tex>
+'''Матрицей Кирхгофа''' [[Основные определения теории графов#def_simple_graph|простого графа]] <tex>G = (V,E) </tex> называется матрица <tex> K (|V| \times |V|) = \parallel k_{i,j} \parallel  </tex>, элементы которой определяются равенством: <tex>
 k_{i,j} =
 \begin{cases}
@@ Строка 10: / Строка 10: @@
 </tex>
 }}
-Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении <tex>i</tex>-й строки и <tex>j</tex>-го столбца (<tex>i \ne j</tex>) стоит -1, если вершины с номерами <tex>i</tex> и <tex>j</tex> смежны, и 0 в противном случае.
+Иными словами, на главной диагонали матрицы Кирхгофа находятся степени вершин, а на пересечении <tex>i</tex>-й строки и <tex>j</tex>-го столбца (<tex>i \ne j</tex>) стоит <tex>-1</tex>, если вершины с номерами <tex>i</tex> и <tex>j</tex> смежны, и <tex>0</tex> в противном случае.
 == Пример матрицы Кирхгофа==
 {|class="wikitable"
 !Граф
@@ Строка 30: / Строка 31: @@
 == Некоторые свойства ==
-*Матрица Кирхгофа является симметрической (т.е. симметрична относительно главной диагонали).
+* Сумма элементов каждой строки (столбца) матрицы Кирхгофа равна нулю:
-*Связь с матрицей смежности:
+*Связь с [[Матрица смежности графа|матрицей смежности]]:
-<tex> K =
+:<tex> K =
 \begin{pmatrix}
 deg(v_1) & 0 & \cdots & 0 \\
@@ Строка 45: / Строка 51: @@
 где <tex>A</tex> — матрица смежности графа <tex>G</tex>.
-*[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]: <tex> K = I \cdot I^T, </tex> где <tex>I</tex> — матрица инцидентности некоторой ориентации графа.
+*[[Связь матрицы Кирхгофа и матрицы инцидентности|Связь с матрицей инцидентности]]:
 ==См. также==
 *[[Связь матрицы Кирхгофа и матрицы инцидентности]]
 *[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
@@ Строка 54: / Строка 63: @@
 ==Источники==
-''Асанов М., Баранский В., Расин В.'' — Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.<br>
+*Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы
-[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия, Матрица Кирхгофа]
+*[http://ru.wikipedia.org/wiki/%CC%E0%F2%F0%E8%F6%E0_%CA%E8%F0%F5%E3%EE%F4%E0 Википедия, Матрица Кирхгофа]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Остовные деревья ]]