Изменения

== Разбор случаев взаимного положения вершин ''a, b, c, d, u1, u2, v1, v2'' ==Рассмотрим 2 случая* Пусть пара вершин <tex>\ v_1 </tex> и <tex>\ v_2 </tex> <b> является </b> <tex>(a, b)</tex> {{---}} разделяющей.<br>[[Файл*:Case_1Тогда, в частности, <tex>v_2 \ne a</tex> и <tex> v_1 \ne b</tex>.png|thumb|right|*: В этом случае граф <tex>G</tex> содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex> {{---}} цепь) (рис. 7.1]]).

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>[[Файл:Case_1. В этом случае граф <tex>G</tex> содержит подграф, гомеоморфный <tex>\ K_{3,3} </tex> (отметим, что в <tex> In </tex> существует простая <tex>(v_1, v_2)</tex> {{---}} цепь) (png|270px|рис. 7.1).]]

2. * Пусть пара вершин <tex>v_1</tex> и <tex>v_2</tex> <b> не является </b> <tex>(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. *# <b>Пусть <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> (рис. 7.2). <br></b> 2.1.1 *## Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>*##: Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.3).<br> 2*##: [[Файл:Сase_2.1.21. Пусть <png|200px|рис. 7.3]]*## Пусть <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>. *##:В этом случае в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.4).<br> 2*##:[[Файл:Сase_2.1.32. Пусть png|200px|рис. 7.4]]*## Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>*##:Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.5).<br> <center><gallery style="text-align*##:center; font-size:90%" >[[Файл:Сase_2.1.3.png|200px|рис. 7.25]]Файл*#:Сase_2.1.1.png|рис. 7.3<br>Файл*#:Сase_2.1.Теперь рассмотрим случаи (2.png|рис. 7.4Файл:Сase_2.1.и 3.png|рис. 7.5</gallery></center> Теперь рассмотрим случаи, когда ), когда хотя бы одна из вершин <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. *# <b> Пусть <tex>v_2 \ne a</tex>.<br> </b> 2.2.1. *##: Пусть <tex>u_2</tex> лежит на <tex>C(d, a)</tex>.<br>*##: Тогда в графе <tex>G</tex> есть пограф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.6).<br> 2.*##:[[Файл:Сase_2.2.21.png|200px|рис. 7. 6]]*## Пусть <tex>u_2 = d</tex>.<br>*##:Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.7).<br> *##:[[Файл:Сase_2.2.2.3png|220px|рис. 7. 7]]*## Пусть <tex>u_2</tex> лежит на <tex>C(b, d)</tex>.<br>*##:Тогда в графе <tex>G</tex> имеется подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.8). <br> <center><gallery style="text-align*##:center; font-size:90%" >[[Файл:Сase_2.2.13.png|200px|рис. 7.68]]Файл*#:Сase_2.2.2.png|рис. 7.7<br>Файл*#:Сase_2.2.3.png|рис. 7.8<br>*# </galleryb></center> 2.3. Пусть <tex>v_2 = a</tex> (рис. 7.9).<br>Рассмотрим теперь пару вершин <tex>u_1<</tex> и <tex>u_2</texb>*#:[[Файл:Сase_2.3(a).png|200px|рис. 7. Будем считать, что 9]]*#:Рассмотрим теперь пару вершин <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> (рис. 7.10).*#:[[Файл:Сase_2.3(b).png|200px|рис. 7.10]]*#:Заметим, что <tex>P_1</tex> и <tex>P_2</tex> имеют общую точку.<br> 2.3.1. *#: <br>*## Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют более одной общей точки.<br>*##: Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_{3,3}</tex> (рис. 7.11).<br> 2*##: [[Файл:Сase_2.3.21. Пусть цепи png|200px|рис. 7.11]]*## Пусть цепи <tex>P_1</tex> и <tex>P_2</tex> имеют точно одну общую точку <tex>w</tex>.<br>*##: Тогда в графе <tex>G</tex> есть подграф, гомеоморфный <tex>K_5</tex> (рис. 7.12).<br> <center><gallery style="text-align*##:center; font-size:90%" >[[Файл:Сase_2.3(a).png|рис. 7.9Файл:Сase_2.3(b).png|рис. 7.10Файл:Сase_2.3.12.png|рис. 7.11Файл:Сase_2.3.2.png200px|рис. 7.12</gallery></center>]]