Изменения

Перейти к: навигация, поиск

Теорема Хватала

2057 байт добавлено, 05:39, 20 ноября 2011
Нет описания правки
{{Определение
|definition=
Пусть [[Основные_определения_теории_графов|неориентированный граф]] <tex> G </tex> имеет <tex> n </tex> вершин: <tex> v_1, v_2, \ldots, v_n </tex>. Пусть <tex> d_i = \deg v_i \mbox{ } (i = \overline{1, n}) </tex> и вершины графа упорядочены таким образом, что <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex>. Последовательность <tex> d_1, d_2, \ldots, d_n </tex> называют '''последовательностью степеней''' графа <tex> G </tex>.
}}
 
{{Лемма
|about=
О добавлении ребра в граф
|statement=
Пусть [[Основные_определения_теории_графов|неориентированный граф]] <tex> G' </tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.
|proof=
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место, то исходная последовательность будет мажорироваться полученной.
При добавлении в граф ребра <tex> e = uv, \mbox{ } (u \neq v) </tex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.
}}
 
{{Теорема
|about=
}}
Приведем доказательство от противного. <br> Пусть теорема Хватала не верна, тогда существует граф с числом вершин <tex> n \geq 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.
Будем добавлять в него [[Основные определения теории графов|рёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).
Важно то, что добавление рёбер не нарушает По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.Очевидно, что граф <tex>\ K_n </tex> гамильтонов для при <tex>\ k \ge geq 3 </tex>.Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex>\ K_n </tex>. Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex> с условием: , такие что <tex> \deg u + \deg v </tex> — максимально.Будем считать, что <tex>\deg u \le leq \deg v </tex>.Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e</tex>.Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа <tex> G + e</tex>: в нём обязательно присутствует ребро <tex> e </tex>. <br>Отбрасывая ребро <tex> e </tex>, получим гамильтонову (<tex>u</tex>, <tex>v</tex>)-цепь в графе <tex> G </tex>: <tex> u = u_1 - u_2 - ... - u_n = v </tex>. <br>
Пусть <tex>\ S = \{i|e_i = u_1 u_{i+1} \in E(G)\} </tex>. <br>
Пусть <tex>\ T = \{i|f_i = u_i u_n \in E(G)\} </tex>. <br>
Анонимный участник

Навигация