Циклическое пространство графа - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:25:30Z

rollbackEdits.php mass rollback

103.251.167.21 в 05:02, 1 сентября 2022

2022-09-01T05:02:36Z

188.227.78.144 в 19:08, 20 октября 2016

2016-10-20T19:08:49Z

188.227.78.144 в 18:58, 20 октября 2016

2016-10-20T18:58:09Z

Shersh: /* Применение */

2014-12-26T18:39:37Z

‎Применение

Alexey Katsman в 18:38, 26 декабря 2014

2014-12-26T18:38:07Z

Alexey Katsman в 18:32, 26 декабря 2014

2014-12-26T18:32:51Z

Alexey Katsman в 18:29, 26 декабря 2014

2014-12-26T18:29:55Z

Alexey Katsman в 18:29, 26 декабря 2014

2014-12-26T18:29:31Z

Alexey Katsman в 18:23, 26 декабря 2014

2014-12-26T18:23:05Z

← Предыдущая		Версия 16:25, 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 Майкл Наки].
−	\|}
−
	__TOC__		__TOC__
	== Циклическое пространство графа ==		== Циклическое пространство графа ==

← Предыдущая		Версия 05:02, 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 Майкл Наки].
		+	\|}
		+
	__TOC__		__TOC__
	== Циклическое пространство графа ==		== Циклическое пространство графа ==

@@ Строка 17: / Строка 17: @@
 {{Лемма
-|id = lemma
+|id = lemma1
 |statement=
 Пространство <tex> C </tex> изоморфно <tex> T </tex>, где <tex> T </tex>{{---}} пространство, элементами которого являются наборы [[Основные_определения_теории_графов#def_graph_edge_1 | ребер]], из которых можно составить несколько простых реберно непересекающихся [[Основные_определения_теории_графов#def_graph_cycle_1 | циклов]].

@@ Строка 17: / Строка 17: @@
 {{Лемма
 |statement=
 Пространство <tex> C </tex> изоморфно <tex> T </tex>, где <tex> T </tex>{{---}} пространство, элементами которого являются наборы [[Основные_определения_теории_графов#def_graph_edge_1 | ребер]], из которых можно составить несколько простых реберно непересекающихся [[Основные_определения_теории_графов#def_graph_cycle_1 | циклов]].

@@ Строка 59: / Строка 59: @@
 == Применение ==
-Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf | Карпов В.Д. Теория графов - с.281 - Применения циклического пространства графа]</ref>.
+Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf  Карпов В.Д. Теория графов - с.281 - Применения циклического пространства графа]</ref>.
 == См. также ==

@@ Строка 24: / Строка 24: @@
 Рассмотрим граф <tex> G_1(V_1,E_1) </tex>, где <tex>  E_1 </tex> {{---}} множество ребер, таких, что на соответствующих местах вектора <tex> x </tex> стоят единицы, а <tex> V_1 = V(G) </tex> .
-В силу определения обобщенного цикла: <tex> \forall v  : v \in V_1 ~ deg(v) \equiv 0\mod~) </tex>.
+В силу определения обобщенного цикла: <tex> \forall v  : v \in V_1 ~ deg(v) \equiv 0\mod~2 </tex>.
 Покажем по индукции, что <tex> G </tex> можно декомпозировать  на несколько реберно непересекающихся простых циклов. Ведем индукцию по числу ребер.

@@ Строка 24: / Строка 24: @@
 Рассмотрим граф <tex> G_1(V_1,E_1) </tex>, где <tex>  E_1 </tex> {{---}} множество ребер, таких, что на соответствующих местах вектора <tex> x </tex> стоят единицы, а <tex> V_1 = V(G) </tex> .
-В силу определения обобщенного цикла: <tex> \forall v  : v \in V_1 ~ deg(v) \equiv 0(\mod~2) </tex>.
+В силу определения обобщенного цикла: <tex> \forall v  : v \in V_1 ~ deg(v) \equiv 0\mod~) </tex>.
 Покажем по индукции, что <tex> G </tex> можно декомпозировать  на несколько реберно непересекающихся простых циклов. Ведем индукцию по числу ребер.
 База индукции <tex> |E_1(G)|=0 </tex> очевидно выполняется.
-Рассмотрим <tex> G_1 </tex>. <tex>   \forall v  : v \in V_1 ~ deg(v) \equiv 0(\mod~2) \Rightarrow |E_1(G)| > |V(G)| - 1 \Rightarrow  </tex> существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что четность степеней вершин не изменилась, по предположению индукции декомпозируем оставшийся граф.
+Рассмотрим <tex> G_1 </tex>. <tex>   \forall v  : v \in V_1 ~ deg(v) \equiv 0\mod~2 \Rightarrow |E_1(G)| > |V(G)| - 1 \Rightarrow  </tex> существует цикл, добавим его в декомпозицию, удалим ребра, принадлежащие ему. В силу того, что четность степеней вершин не изменилась, по предположению индукции декомпозируем оставшийся граф.
 Отсюда следует, что каждому обобщенному циклу соответствуют ребра, которые образуют набор реберно непересекающихся простых циклов.

@@ Строка 59: / Строка 59: @@
 == Применение ==
-Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа.
+Циклическое пространство графа позволяет доказать некоторые теоремы из теории графов, а также описать условия существования отдельных подвидов графа. В частности, благодаря введенному понятию, можно доказать необходимое и достаточное условие планарности графа<ref>[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf | Применения циклического пространства графа]</ref>.
 == См. также ==
@@ Строка 65: / Строка 65: @@
 *[[Ядро_и_образ_линейного_оператора|Ядро и образ линейного оператора]]
 == Источники информации ==