| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| | {{Определение | | {{Определение |
| | |definition= | | |definition= |
| − | [[Основные определения теории графов|Граф]] называется '''произвольно вычерчиваемым из вершины <tex>v</tex>''' (англ. ''Arbitrarily traceable graph''), если любая цепь с началом в вершине <tex>v</tex> может быть продолжена до эйлерового цикла графа <tex>G</tex>. }}
| + | Граф называется '''произвольно вычерчиваемым из вершины v''' (англ. '''Arbitrarily traceable graph'''), если любая цепь с началом в вершине v может быть продолжена до эйлеровой цепи графа G. Разумеется, если граф произвольно вычерчиваем из вершины v, то он является эйлеровым графом. }} |
| − | {{Утверждение
| |
| − | |statement=Любой произвольно вычерчиваемый из вершины <tex>v</tex> граф является [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеровым графом]].
| |
| − | }} | |
| − | | |
| | {{Теорема | | {{Теорема |
| | |statement= | | |statement= |
| − | [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|Эйлеров граф]] <tex>G</tex>, содержащий хотя бы одно ребро, является произвольно вычерчиваемым из вершины <tex>v</tex> <tex>\Longleftrightarrow</tex> вершина <tex>v</tex> принадлежит всем циклам графа <tex>G</tex>.<br> | + | Неодноэлементный [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов|эйлеров граф]] ''G'' является произвольно вычерчиваемым из вершины ''v'' тогда и только тогда, когда вершина ''v'' принадлежит любому циклу графа ''G''.<br> |
| | |proof= | | |proof= |
| − | [[Файл:ATG_part1.jpg|200px|right]]
| + | Пусть вершина ''v'' эйлерова графа ''G'' принадлежит любому циклу. Рассмотрим произвольную (''v, w'')-цепь ''P'' и покажем, что её можно продолжить до эйлеровой цепи. Обозначим через <math>G_1</math> подграф графа ''G'', полученный удалением из ''G'' всех рёбер цепи ''P''. Если ''w=v'', то все вершины подграфа <math>G_1</math> имеют чётную степень, если же ''w≠v'', то <math>G_1</math> содержит в точности две вершины нечётной степени. Пусть <math>H_0</math> – компонента связности графа <math>G_1</math> , содержащая вершину ''v''. Ясно, что вершина ''w'' принадлежит <math>H_0</math> . Следовательно, <math>H_0</math> – полуэйлеров граф, и потому в <math>H_0</math> существует эйлерова (''w,v'')-цепь ''Q''. Очевидно, что <math>H_0</math> содержит все рёбра графа <math>G_1</math>. Предположим, что <math>G_1</math> содержит неодноэлементную компоненту связности ''H'', отличную от <math>H_0</math> . Тогда ''H'' – эйлеров граф, и потому в ''H'' содержится цикл. Этот цикл не проходит через вершину ''v'', что невозможно. Следовательно, все компоненты связности подграфа <math>G_1</math>, отличные от <math>H_0</math>, одноэлементны.<br> |
| − | <tex>\Rightarrow</tex> <br>
| + | Таким образом, цепь ''Q'' содержит все рёбра графа <math>G_1</math>. Отсюда вытекает, что объединение цепей ''P'' и ''Q'' – эйлерова цепь в графе ''G'', являющаяся продолжением цепи ''P''.<br> |
| − | Пусть в <tex>G</tex> <tex>\exists</tex> цикл <tex>C, v \notin C</tex>.<br> | + | Обратно, пусть в графе ''G'' существует цикл ''C'', не содержащий вершину ''v''. Рассмотрим подграф <math>G_1</math>, полученный удалением из ''G'' всех ребер цикла ''С''. Пусть ''H'' – компонента связности подграфа <math>G_1</math>, содержащая вершину ''v''. Легко понять, что ''H'' – эйлеров граф. Обозначим через ''P'' эйлерову цепь подграфа . Можно считать, что началом и концом цепи ''P'' является вершина ''v''. Поскольку ''v'' не принадлежит циклу ''C'', цепь ''P'' нельзя продолжить до эйлеровой цепи графа ''G''. |
| − | Рассмотрим <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|right]]
| |
| − | <tex>\Leftarrow</tex> <br> | |
| − | Пусть дан эйлеров граф <tex>G</tex>, вершина <tex>v</tex> принадлежит всем его циклам.<br>
| |
| − | Рассмотрим произвольный путь <tex>P = v \leadsto w</tex>. Пусть <tex>G_1 = G/P</tex>. Возможны 2 случая:
| |
| − | | |
| − | # Если <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 \leadsto v \in 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 \leadsto v</tex> <tex>\Rightarrow</tex> <tex>P+Q</tex> эйлеров цикл в графе <tex>G</tex>.
| |
| | }} | | }} |
| − | | + | '''Источники:''' <br> |
| − | == Строение ==
| + | Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр. |
| − | [[Файл:ATGexample.jpg|right|300px]]
| |
| − | Опираясь на теорему опишем строение всех графов, произвольно вычерчиваемых из вершины <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>v</tex>, как эйлеров граф, у которого <tex>v</tex> принадлежит всем циклам.
| |
| − | Теперь докажем, почему таким образом можно получить все графы, произвольно вычерчиваемые из вершины <tex>v</tex>. Пусть какой-то такой граф нельзя получить методом описанным выше. Тогда уберем все ребра из вершины <tex>v</tex> и посмотрим на граф, который остался. Он не является лесом, иначе мы могли бы получить этот граф нашим методом. Но если он не является лесом, то в нем есть хотя бы один цикл, который не содержит <tex>v</tex>. А по теореме о произвольно вычерчиваемымых из вершины графах такого быть не может. Следовательно наше предположение ошибочно.
| |
| − | | |
| − | ==См. также==
| |
| − | * [[Покрытие рёбер графа путями]]
| |
| − | * [[Алгоритм построения Эйлерова цикла]]
| |
| − | | |
| − | ==Источники информации==
| |
| − | * Асанов М., Баранский В., Расин В. ''Дискретная математика: Графы, матроиды, алгоритмы.'', Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. ISBN 5-93972-076-5
| |
| − | | |
| − | [[Категория: Алгоритмы и структуры данных]]
| |
| − | [[Категория: Обходы графов]]
| |
| − | [[Категория: Эйлеровы графы]]
| |
