Редактирование: Произвольно вычерчиваемые из заданной вершины графы
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 2: | Строка 2: | ||
|definition= | |definition= | ||
[[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из вершины <tex>v</tex>''' (англ. ''Arbitrarily traceable graph''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. }} | [[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из вершины <tex>v</tex>''' (англ. ''Arbitrarily traceable graph''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. }} | ||
| − | + | <br>Любой произвольно вычерчиваемый из вершины <tex>v</tex> граф является [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеровым графом]]. | |
| − | |||
| − | |||
{{Теорема | {{Теорема | ||
| Строка 11: | Строка 9: | ||
|proof= | |proof= | ||
[[Файл:ATG_part1.jpg|200px|right]] | [[Файл:ATG_part1.jpg|200px|right]] | ||
| − | <tex>\Rightarrow</tex> | + | <tex>\Rightarrow</tex> Пусть в <tex>G</tex> <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br> |
| − | Пусть в <tex>G</tex> <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br> | ||
Рассмотрим <tex>G_1 = G/C</tex> (здесь и далее это означает удаление только ребер, не трогая вершины). При удалении цикла все степени вершин остались четными, потому что каждая вершина содержит четное количество ребер цикла, и следовательно <tex>G_1</tex> {{---}} эйлеров. Тогда в <tex>G_1</tex> <tex>\exists</tex> эйлеров цикл. Если начать обход по эйлерову циклу из <tex>v</tex>, то и закончится он в <tex>v</tex>. Если теперь вернуть цикл <tex>C</tex>, то мы никак не сможем его обойти, так как из вершины <tex>v</tex> больше нет не посещенных ребер <tex>\Rightarrow</tex> <tex>G</tex> не свободно вычерчиваемый из <tex>v</tex>. | Рассмотрим <tex>G_1 = G/C</tex> (здесь и далее это означает удаление только ребер, не трогая вершины). При удалении цикла все степени вершин остались четными, потому что каждая вершина содержит четное количество ребер цикла, и следовательно <tex>G_1</tex> {{---}} эйлеров. Тогда в <tex>G_1</tex> <tex>\exists</tex> эйлеров цикл. Если начать обход по эйлерову циклу из <tex>v</tex>, то и закончится он в <tex>v</tex>. Если теперь вернуть цикл <tex>C</tex>, то мы никак не сможем его обойти, так как из вершины <tex>v</tex> больше нет не посещенных ребер <tex>\Rightarrow</tex> <tex>G</tex> не свободно вычерчиваемый из <tex>v</tex>. | ||
| − | [[Файл:ATG_part2.jpg|200px| | + | [[Файл:ATG_part2.jpg|200px|left]] |
| − | <tex>\Leftarrow</tex> | + | <tex>\Leftarrow</tex> Пусть дан эйлеров граф <tex>G</tex>, вершина <tex>v</tex> принадлежит всем его циклам.<br> |
| − | Пусть дан эйлеров граф <tex>G</tex>, вершина <tex>v</tex> принадлежит всем его циклам.<br> | + | Рассмотрим произвольный путь <tex>P = (v,w)</tex>. Пусть <tex>G_1 = G/P</tex>. Возможны 2 случая: |
| − | Рассмотрим произвольный путь <tex>P = v | ||
# Если <tex>v = w</tex>, то <tex>P</tex> {{---}} цикл, значит степени всех вершин в <tex>G_1</tex> остались четными <tex>\Rightarrow</tex> <tex>G_1</tex> {{---}} эйлеров.<br> | # Если <tex>v = w</tex>, то <tex>P</tex> {{---}} цикл, значит степени всех вершин в <tex>G_1</tex> остались четными <tex>\Rightarrow</tex> <tex>G_1</tex> {{---}} эйлеров.<br> | ||
| − | # Если <tex>v \neq w</tex>, то так как <tex>G</tex> эйлеров граф <tex>\exists</tex> эйлеров путь <tex>w | + | # Если <tex>v \neq w</tex>, то так как <tex>G</tex> эйлеров граф <tex>\exists</tex> эйлеров путь <tex>(w,v) \in G_1</tex>. |
Покажем, что в обоих случаях эйлеров обход пройдет по всем ребрам <tex>G_1</tex>. | Покажем, что в обоих случаях эйлеров обход пройдет по всем ребрам <tex>G_1</tex>. | ||
| − | В <tex>G</tex> <tex>\exists</tex> единственная компонента связности, содержащая ребра. При удалении <tex>P</tex> их количество не могло увеличится, иначе должен быть цикл, не содержащий <tex>v</tex>(смотри рисунок). Значит в <tex>G_1</tex> <tex>\exists</tex> единственная компонента связности содержащая ребра, причем <tex>G_1</tex> либо полуэйлеров, либо эйлеров <tex>\Rightarrow</tex> в <tex>G_1</tex> <tex>\exists</tex> эйлерова цепь <tex>Q = w | + | В <tex>G</tex> <tex>\exists</tex> единственная компонента связности, содержащая ребра. При удалении <tex>P</tex> их количество не могло увеличится, иначе должен быть цикл, не содержащий <tex>v</tex>(смотри рисунок). Значит в <tex>G_1</tex> <tex>\exists</tex> единственная компонента связности содержащая ребра, причем <tex>G_1</tex> либо полуэйлеров, либо эйлеров <tex>\Rightarrow</tex> в <tex>G_1</tex> <tex>\exists</tex> эйлерова цепь <tex>Q = (w,v)</tex> <tex>\Rightarrow</tex> <tex>P+Q</tex> эйлеров цикл в графе <tex>G</tex>. |
}} | }} | ||
| Строка 31: | Строка 27: | ||
Опираясь на теорему опишем строение всех графов, произвольно вычерчиваемых из вершины <tex>v</tex>. <br> | Опираясь на теорему опишем строение всех графов, произвольно вычерчиваемых из вершины <tex>v</tex>. <br> | ||
Возьмем произвольный [[Дерево, эквивалентные определения|лес]] <tex>H</tex>, не содержащий вершину <tex>v</tex>. Каждую вершину нечетной степени соединим некоторым нечетным числом кратных ребер с <tex>v</tex>, а каждую вершину четной степени <tex>-</tex> четным числом кратных ребер с <tex>v</tex> (не исключая <tex>0</tex>), причем каждую изолированную вершину обязательно соединим с <tex>v</tex>.<br> | Возьмем произвольный [[Дерево, эквивалентные определения|лес]] <tex>H</tex>, не содержащий вершину <tex>v</tex>. Каждую вершину нечетной степени соединим некоторым нечетным числом кратных ребер с <tex>v</tex>, а каждую вершину четной степени <tex>-</tex> четным числом кратных ребер с <tex>v</tex> (не исключая <tex>0</tex>), причем каждую изолированную вершину обязательно соединим с <tex>v</tex>.<br> | ||
| − | Полученный граф <tex>G</tex>: | + | Полученный граф <tex>G</tex>: связен, имеет только вершины четной степени и является произвольно вычерчиваемым из <tex>v</tex>, как эйлеров граф, у которого <tex>v</tex> принадлежит всем циклам. |
| − | |||
| − | |||
| − | |||
Теперь докажем, почему таким образом можно получить все графы, произвольно вычерчиваемые из вершины <tex>v</tex>. Пусть какой-то такой граф нельзя получить методом описанным выше. Тогда уберем все ребра из вершины <tex>v</tex> и посмотрим на граф, который остался. Он не является лесом, иначе мы могли бы получить этот граф нашим методом. Но если он не является лесом, то в нем есть хотя бы один цикл, который не содержит <tex>v</tex>. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно. | Теперь докажем, почему таким образом можно получить все графы, произвольно вычерчиваемые из вершины <tex>v</tex>. Пусть какой-то такой граф нельзя получить методом описанным выше. Тогда уберем все ребра из вершины <tex>v</tex> и посмотрим на граф, который остался. Он не является лесом, иначе мы могли бы получить этот граф нашим методом. Но если он не является лесом, то в нем есть хотя бы один цикл, который не содержит <tex>v</tex>. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно. | ||
==См. также== | ==См. также== | ||
| − | * [[Покрытие | + | * [[Покрытие ребер графа путями]] |
* [[Алгоритм построения Эйлерова цикла]] | * [[Алгоритм построения Эйлерова цикла]] | ||
