Задача 5. Базисные вложения графов.

Вводные задачи

Определение 1.1. Обозначим через R² плоскость с фиксированной прямоугольной системой координат. Пусть K - подмножество R². Вложение K c R² называется базисным (обозначается K c_b R²), если для каждой непрерывной функции f:K -> R существуют непрерывные функции g,h: R -> R такие, что f(x,y)=g(x)+h(y) для каждой точки (x,y)c K.

Через [a,b] мы обозначим отрезок, соединяющий точки a и b.

Пример 1.2. Отрезок [(0,0),(0,1)] базисно вложен в R².

Пример 1.3. Множество {(0,0),(0,1),(1,0),(1,1)} не базисно вложено в R².

Задача 1.4. Крест K=[(0,-1),(0,1)]\cup[(-1,0),(1,0)] базисно вложен в R².

Обозначим через p_x и p_y проекции на координатные оси x и y соответственно. Упорядоченный набор a₁,...,a_n} c R² называется массивом, если для каждого i выполнено a_i не равно a_i+1, при этом p_x (a_i )=p_x (a_i+1) для четных i и p_y (a_i )=p_y (a_i+1) для нечетных i. При этом не обязательно все точки массива должны быть различны.

Задача 1.5. Если A={a₁,...,a_n} массив, такой что a₁=a_n, то A не базисно вложено в R².

Задача 1.6.^* Крест K=[(-1,-2),(1,2)]U[(-1,1),(1,-1)] не базисно вложен в R².

Отображение графа K в плоскость R² называется вложением, если оно отображает вершины графа K в различные точки R² и ребра графа K в непересекающиеся ломаные линии, соединяющие эти точки.

Главная задача этого параграфа состоит в том, чтобы описать графы, для которых существует вложение в плоскость, являющееся базисным. Заметим, что существует разница между словами "базисно вложимый" и "базисно вложенный". Из задач 1.4 и 1.6 видно, что мы можем вложить граф двумя разными способами, и в одном случае вложение будет базисным, а в другом нет. В дальнейшем мы будем использовать другое, геометрическое определение базисного вложения - см. теорему 1.7 ниже. Его равносильность первоначальному функциональному определению доказал израильский математик Штернфельд. Задачи 1.5 и 1.6 иллюстрируют эту равносильность. Мы, однако, не знаем элементарного доказательства этого факта (будьте осторожны при решении задачи 1.9.б!). Итак, мы будем использовать геометрическое определение базисного вложения без доказательства его равносильности функциональному.

Дадим несколько определений. Пусть Z - подмножество R². Для каждой точки zc Z нарисуем две прямые, проходящие через z параллельно координатным осям. Если хотя бы одна из этих прямых пересекает Z только в точке z, покрасим z в белый цвет. Обозначим через E(Z) множество всех точек Z, не являющихся белыми. Пусть E²(Z)=E(E(Z)), E³(Z)=E(E(E(Z))) и т. д.

Теорема 1.7. Вложение K c R² базисно тогда и только тогда, когда выполнено одно из следующих двух эквивалентных условий:

а) для некоторого натурального n не существует массива из n точек в K;

б) для некоторого натурального n, Eⁿ(K)=f.

Задача 1.8.

а) Решите задачи 1.2-1.6 с определением базисного вложения из 1.7.а;

б) Решите задачи 1.2-1.6 с определением базисного вложения из 1.7.б.

Задача 1.9.

а) Докажите, что условия 1.7.а и 1.7.б равносильны;

б)^* Докажите теорему 1.7 для кусочно-линейного подмножества K плоскости R² (т. е. подмножества, являющегося объединением конечного числа отрезков).

Задача 1.10. Граница любого многоугольника на плоскости (не обязательно выпуклого) не базисно вложена в плоскость.

Основные задачи. Плоский случай

Задача 2.1. Окружность S (см. рис.1) не является базисно вложимой в R².

Задача 2.2. а) Если T₅ c_b R², то некоторый крест T₄ c T₅ с центром d базисно вложен в одну из полуплоскостей [0,+oo)*R, (-oo,0]*R, R*[0,+oo), R*(-oo,0] так, что d=(0,0);

б) Если крест T₄ базисно вложим в полуплоскость [0,+oo)*R так, что d=(0,0), то некоторый триод T₃ c T₄ базисно вложим в один из квадрантов [0,+oo)*[0,+oo), [0,+oo)*(-oo,0] так, что d=(0,0);

в) Если триод T₃ базисно вложим в квадрант [0,+oo)*[0,+oo) так, что d=(0,0), то некоторый диод T₂ c T₃ базисно вложим в один из лучей [0,+oo)*0, 0*[0,+oo) так, что d=(0,0);

г) Пентод T₅ не является базисно вложимым в R².

Задача 2.3. Если T₄ c_b R², то одна из ветвей T₄ содержит прямолинейный отрезок с концом в d, параллельный одной из координатных осей;

Подсказка: задача 2.3 может быть решена аналогично задаче 2.2. Базисная невложимость креста C (см. рис.1) в плоскость R² доказывается, используя задачу 2.3 и следующие соображения.

Определение 2.4. Пусть K c R² и отрезок I=[(a,c),(b,c)] c K параллелен оси x. Горизонтальное схлопывание, порождаемое отрезком I - это отображение q:R² -> R², определенное формулой

	(x,y),	если x < a
q(x,y)=	(a,y),	если a< x< b
	(x-(b-a),y),	если x>b

Задача 2.5. Пусть K - конечный граф, K c_b R² и I,q те же, что и в определении 2.4. Тогда

а) q|_K\I - это инъекция;

б) q(K) c_b R².

Задача 2.6. Решите задачу 2.5.б с первоначальным (функциональным) определением базисного вложения.

Задача 2.7. Граф C (см. рис.1) не является базисно вложимым в R².

Пусть U₁ - триод, и граф U_n+1 получается из U_n разветвлением каждого висячего ребра. Обозначим через R_n граф, получаемый из U_n приклеиванием одного нового висячего ребра к каждой невисячей вершине U_n (рис. 2) (Этот и последующие рисунки приведены в конце условий пятой задачи.).

Задача 2.8. Если конечный граф K не содержит ни одного из графов, изображенных на рис.1, то K содержится в R_n для некоторого натурального n.

По задаче 1.4 R₁ базисно вложим в R².

Задача 2.9. а) R₂ базисно вложим в R²;

б) R_n базисно вложим в R² для каждого натурального n.

Основные задачи. Обобщения.

Декартовым произведением X*Yдвух множеств X и Y называется множество всех пар (a,b) таких, что ac X и bc Y. Если X и Y графы, то мы можем представлять себе произведение X*Y как двумерный объект (в некоторых случаях можно считать, что этот объект расположен в трехмерном пространстве). Например, T₃*I является "книжкой с тремя страницами", S*I - цилиндром, S*S - тором. Определим отображения p_x :X*Y -> X и p_y :X*Y -> Y формулами p_x (a,b)=a и p_y (a,b)=b, соответственно.

Примечание Web-мастера: обычно декартово произведение обозначается крестиком (x), здесь же оно обозначено звёздочкой (*), так как использование соответствующего символа шрифта "Symbol" в кодировке КОИ-8 вызывает некоторые проблемы, а использование буквы "x" может привести к путанице. По этой же причине бесконечность изобажается как oo, а также использовано ещё несколько подобных трюков (надеемся, что их интерпретация не вызовет у Вас проблем).

Каждое из определений базисного вложения может быть обобщено на произвольное декартово произведение A*B. Эквивалентность этих определений также была доказана Штернфельдом. Мы приводим здесь обобщение только геометрического определения.

Определение 3.1. Пусть Z - подмножество произведения A*B. Для каждой точки (a,b)cZ рассмотрим два подмножества a*B и A*b произведения A*B (аналогичных прямым из определения E для плоскости). Если одно из этих множеств пересекает Z только в точке (a,b), то покрасим (a,b) в белый цвет. Пусть E(Z) - множество всех не белых точек из Z. Пусть E²(Z)=E(E(Z)), E³(Z)=E(E(E(Z))) и т. д. Вложение K c A*B называется базисным, если Eⁿ(K)=f для некоторого n.

Задача 3.2. а)Докажите, что подмножество d*S является базисно вложенным в T₂*S;

б) Докажите, что T₅ является базисно вложимым в T₃*R.

Хотя следующая задача пока не решена, мы думаем, что она простая.

Задача 3.3.^* а) Конечный граф K базисно вложим в цилиндр R*S тогда и только тогда, когда K не содержит подграфов, изображенных на рис. 3.

б) Конечный граф K базисно вложим в тор S*S тогда и только тогда, когда K не содержит подграфов, изображенных на рис. 4.

Задача 3.4.

а) S не является базисно вложимой в T₂*T₃.

б) S не является базисно вложимой в T_m*T_n.

Следующая задача аналогична задаче 2.2.

Задача 3.5. а) Граф T₆ с рис. 5.б не является базисно вложимым в R*T₃;

б) Граф T₅|_|T₅ с рис. 5.д не является базисно вложимым в R*T₃.

Задача 3.6. Если T₅ базисно вложен в R*T₃ так что d лежит в произведении R на центр триода T₃, то существует дуга A в T₅, содержащая d и такая, что либо p_xA, либо p_yA является точкой.

Задача 3.7. Граф C₅ с рис. 5.в не является базисно вложимым в R*T₃.

Подсказка Для решения задачи 3.7 полезны обобщения понятия схлопывания и задачи 2.5.

Определим графы W_n (см. рис. 6). Пусть U₁=T₃, A - висячее ребро графа U₁, a - висячая вершина ребра A. Граф U_n+1 получается из U_n разветвлением каждого висячего ребра, кроме A. Пусть V_n - граф, полученный приклеиванием одного нового висячего ребра к каждой не висячей вершине графа U_n. Вершина a называется корнем графа V_n. Пусть W_n - букет четырех копий V_n и дуги, такой, что корни графов V_n приклеиваются к одной из вершин дуги.

Задача 3.8. Если конечный граф K не содержит ни одного из графов на рис. 5, то K содержится в W_n для некоторого n.

Задача 3.9. Граф W_n базисно вложим в R*T₃ для любого натурального n.

Задача 3.10. Конечный граф K является базисно вложимым в R*T₃ тогда и только тогда, когда выполнено любое из двух следующих эквивалентных условий:

а) K не содержит ни одного из графов на рис. 5;

б) K содержится в W_n для некоторого n.

Назовем вершину (т. е. либо конец висячего ребра, либо точку ветвления) конечного графа K ужасной, если ее степень больше четырех.
Назовем вершину конечного графа K страшной, если ее степень равна четырем, и она не является концом ни одного висячего ребра. Дефектом K называется сумма d(K)=(deg A₁-2)+... +(deg A_k-2), где A₁, ..., A_k - все страшные и ужасные вершины графа K.

Задача 3.11.^* Конечное дерево K является базисно вложимым в R*T_n тогда и только тогда, когда либо d(K)< n, либо d(K)=n и K содержит ужасную вершину, имеющую висячее ребро.

Задача 3.12.^** Для конечного графа K

а) Существует лишь конечное число "запрещенных" подграфов для базисной вложимости в T_m*T_n.

б) Существует алгоритм проверки базисной вложимости K в T_m*T_n.
...