Теорема Понтрягина-Куратовского — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(g)
Строка 5: Строка 5:
  
 
1. Пусть пара вершин <tex>\ v_1  </tex> и <tex>\ v_2  </tex> является <tex>(a, b)</tex>-разделяющей. <br>
 
1. Пусть пара вершин <tex>\ v_1  </tex> и <tex>\ v_2  </tex> является <tex>(a, b)</tex>-разделяющей. <br>
Тогда, в частности, <tex>v_2 \ne a</tex>  и  <tex> v_1 \ne b</tex>. В этом случае граф G содержит подграф, гомеоморфный <tex>\ K_{3,3}  </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex>-цепь)(рис.1).
+
Тогда, в частности, <tex>v_2 \ne a</tex>  и  <tex> v_1 \ne b</tex>. В этом случае граф G содержит подграф, гомеоморфный <tex>\ K_{3,3}  </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex>-цепь)(рис. 1).
  
 
----
 
----
2. Пусть пара вершин <tex>v1</tex> и <tex>v2</tex> не является <tex>(a, b)</tex>-разделяющей. <br>
+
2. Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> не является <tex>(a, b)</tex>-разделяющей. <br>
Тогда <tex>v1, v2</tex> лежат на <tex>C[a, b]</tex> или на <tex>C[b, a]</tex>. Без ограничения общности будет считать, что <tex>v1</tex> и <tex>v2</tex> лежат на <tex>C[a, b]</tex>.<br>
+
Тогда <tex>v_1, v_2</tex> лежат на <tex>C[a, b]</tex> или на <tex>C[b, a]</tex>. Без ограничения общности будет считать, что <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C[a, b]</tex>.<br><br>
  
2.1. Пусть <tex>v1</tex> и <tex>v2</tex> лежать на <tex>C(a, b)</tex>
+
2.1. Пусть <tex>v_1</tex> и <tex>v_2</tex> лежат на <tex>C(a, b)</tex>, т.е. <tex>v_1 \ne b</tex> и <tex>v_2 \ne a</tex>(рис. 2). <br><br>
 +
 
 +
2.1.1 Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>
 +
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 3).<br><br>
 +
 
 +
2.1.2. Пусть <tex>u_2 = d</tex>.<br>
 +
Тогда во внешней части <tex>In</tex> имеется вершина <tex>w</tex> и три простые цепи от <tex>w</tex> соответственно до <tex>d, v_1, v_2</tex>, которые в качестве общей точки имеют только точку <tex>w</tex>. В этом случае в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 4).<br><br>
 +
 
 +
2.1.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
 +
Тогда в графе G есть подграф, гомеоморфный <tex>K{3,3}</tex>(рис. 5).<br><br>
 +
 
 +
Теперь рассмотрим случаи, когда хотя бы одна из вершин <tex>v_1</tex> и <tex>v_2</tex> не лежит на <tex>С(a, b)</tex>. Без ограничения общности будем считать, что это вершина <tex>v_1</tex>, т.е <tex>v_1 = b</tex>(поскольку  <tex>v_1</tex> лежит на <tex>C[a, b]</tex>).<br><br>
 +
 
 +
2.2. Пусть <tex>v_2 \ne a</tex>.<br><br>
 +
 
 +
2.2.1. Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>
 +
Тогда в графе G есть пограф, гомеоморфный <tex>K_{3,3}</tex>(рис. 6).<br><br>
 +
 
 +
2.2.2. Пусть <tex>u_2 = d</tex>.<br>
 +
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 7).<br><br>
 +
 
 +
2.2.3. Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>
 +
Тогда в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 8). <br><br>
 +
 
 +
2.3. Пусть <tex>v_2 = a</tex>(рис. 9).<br>
 +
Рассмотрим теперь пару вершин <tex>u_1</tex> и <tex>u_2</tex>. Будем считать, что <tex>u_1 = c</tex> и <tex>u_2 = d</tex>, поскольку все другие случаи расположения вершин <tex>u_1</tex> и <tex>u_2</tex> так же, как были рассмотрены все случаи расположения <tex>v_1</tex> и <tex>v_2</tex>. Пусть <tex>P_1</tex> и <tex>P_2</tex> -- соответственно кратчайшие простые <tex>(a, b)</tex>-цепь и <tex>(c, d)</tex>-цепь по внутренней части <tex>In</tex>(рис. 10). Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку.<br><br>
 +
 
 +
2.3.1. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки.<br>
 +
Тогда в графе G есть подграф, гомеоморфный <tex>K_{3,3}</tex>(рис. 11).<br><br>
 +
 
 +
2.3.2. Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>.<br>
 +
Тогда в графе G есть подграф, гомеоморфный <tex>K_5</tex>(рис. 12).<br><br>
 +
 
 +
Таким образом, доказано, что в графе G имеется подграф, гомеоморфный <tex>K_{3,3}</tex> или <tex>K_5</tex>, что противоречит нашему первому предположению.<br>

Версия 02:38, 19 октября 2010

Разбор случаев взаимного положения [math]a, b, c, d, u1, u2, v1, v2[/math]

Рассмотрим 2 случая.


1. Пусть пара вершин [math]\ v_1 [/math] и [math]\ v_2 [/math] является [math](a, b)[/math]-разделяющей.
Тогда, в частности, [math]v_2 \ne a[/math] и [math] v_1 \ne b[/math]. В этом случае граф G содержит подграф, гомеоморфный [math]\ K_{3,3} [/math] (отметим, что в [math] In [/math] существует простая [math](v_1, v_2)[/math]-цепь)(рис. 1).


2. Пусть пара вершин [math]v_1[/math] и [math]v_2[/math] не является [math](a, b)[/math]-разделяющей.
Тогда [math]v_1, v_2[/math] лежат на [math]C[a, b][/math] или на [math]C[b, a][/math]. Без ограничения общности будет считать, что [math]v_1[/math] и [math]v_2[/math] лежат на [math]C[a, b][/math].

2.1. Пусть [math]v_1[/math] и [math]v_2[/math] лежат на [math]C(a, b)[/math], т.е. [math]v_1 \ne b[/math] и [math]v_2 \ne a[/math](рис. 2).

2.1.1 Пусть [math]u_2[/math] лежит на [math]C(d, a)[/math].
Тогда в графе G имеется подграф, гомеоморфный [math]K_{3,3}[/math](рис. 3).

2.1.2. Пусть [math]u_2 = d[/math].
Тогда во внешней части [math]In[/math] имеется вершина [math]w[/math] и три простые цепи от [math]w[/math] соответственно до [math]d, v_1, v_2[/math], которые в качестве общей точки имеют только точку [math]w[/math]. В этом случае в графе G имеется подграф, гомеоморфный [math]K_{3,3}[/math](рис. 4).

2.1.3. Пусть [math]u_2[/math] лежит на [math]C(b, d)[/math].
Тогда в графе G есть подграф, гомеоморфный [math]K{3,3}[/math](рис. 5).

Теперь рассмотрим случаи, когда хотя бы одна из вершин [math]v_1[/math] и [math]v_2[/math] не лежит на [math]С(a, b)[/math]. Без ограничения общности будем считать, что это вершина [math]v_1[/math], т.е [math]v_1 = b[/math](поскольку [math]v_1[/math] лежит на [math]C[a, b][/math]).

2.2. Пусть [math]v_2 \ne a[/math].

2.2.1. Пусть [math]u_2[/math] лежит на [math]C(d, a)[/math].
Тогда в графе G есть пограф, гомеоморфный [math]K_{3,3}[/math](рис. 6).

2.2.2. Пусть [math]u_2 = d[/math].
Тогда в графе G имеется подграф, гомеоморфный [math]K_{3,3}[/math](рис. 7).

2.2.3. Пусть [math]u_2[/math] лежит на [math]C(b, d)[/math].
Тогда в графе G имеется подграф, гомеоморфный [math]K_{3,3}[/math](рис. 8).

2.3. Пусть [math]v_2 = a[/math](рис. 9).
Рассмотрим теперь пару вершин [math]u_1[/math] и [math]u_2[/math]. Будем считать, что [math]u_1 = c[/math] и [math]u_2 = d[/math], поскольку все другие случаи расположения вершин [math]u_1[/math] и [math]u_2[/math] так же, как были рассмотрены все случаи расположения [math]v_1[/math] и [math]v_2[/math]. Пусть [math]P_1[/math] и [math]P_2[/math] -- соответственно кратчайшие простые [math](a, b)[/math]-цепь и [math](c, d)[/math]-цепь по внутренней части [math]In[/math](рис. 10). Заметим, что [math]P_1[/math] и [math]P_2[/math] имеют общую точку.

2.3.1. Пусть цепи [math]P_1[/math] и [math]P_2[/math] имеют более одной общей точки.
Тогда в графе G есть подграф, гомеоморфный [math]K_{3,3}[/math](рис. 11).

2.3.2. Пусть цепи [math]P_1[/math] и [math]P_2[/math] имеют точно одну общую точку [math]w[/math].
Тогда в графе G есть подграф, гомеоморфный [math]K_5[/math](рис. 12).

Таким образом, доказано, что в графе G имеется подграф, гомеоморфный [math]K_{3,3}[/math] или [math]K_5[/math], что противоречит нашему первому предположению.