| Математические заметки |
|
|
|
|
|
Сложность распознавания мультидистанционных графов в Г. М. Соколов
Англоязычная версия:
Mathematical Notes, 2024, Volume 115, Issue 5, Pages DOI: https://doi.org/10.1134/S000143462405016X 
Реферативные базы данных:
  1. Введение1. История и мотивировка задачиОдним из классических объектов изучения комбинаторной геометрии являются дистанционные графы. Граф называется дистанционным в $\mathbb{R}^d$, если его вершины можно так отобразить в точки $\mathbb{R}^d$, что расстояние между образами любых двух соединенных ребром вершин будет равно $1$. Дистанционные графы тесно связаны с классической проблемой определения хроматического числа пространства (см., например, книгу [1], часть 2): из теоремы Эрдеша-де-Брейна [2] следует, что хроматическое число $\mathbb{R}^d$ равно максимуму из хроматических чисел конечных дистанционных графов в $\mathbb{R}^d$. Можно рассматривать различные варианты определения дистанционных графов: можно требовать или не требовать то, что отображение вершин графа в точки $\mathbb{R}^d$ является инъективным, и то, что несмежным вершинам сопоставлены точки на расстоянии, отличном от $1$. Вслед за работой [3] мы будем называть отображение множества вершин графа в $\mathbb{R}^d$ вложением, если соединенные ребром вершины отображаются в точки на расстоянии $1$; будем называть вложение инъективным, если разные вершины графа переходят в разные точки, и строгим, если вершины, не соединенные ребром, переходят в точки, лежащие на расстоянии отличном от $1$. Граф будем называть (строго) (инъективно) вложимым в $\mathbb{R}^d$, если существует его вложение соответствующего типа. Одной из естественных задач, связанных с дистанционными графами, является определение сложности распознавания вложимых в $\mathbb{R}^d$ графов, а именно определение для различных видов вложимости и значений параметра $d$, является ли эта задача полиномиально разрешимой или $\mathrm{NP}$-трудной. Легко проверить, что для $d=1$ задача решается за полиномиальное время для любого типа вложимости. В [4] доказано, что при $d=2$ задача является $\mathrm{NP}$-трудной для любого вида вложимости. Наконец, в [3] доказано, что при $d \geqslant 3$ задача является $\mathrm{NP}$-трудной для любого типа вложимости. Таким образом, задача определения сложности распознавания графов, вложимых в $\mathbb{R}^d$ с единичными расстояниями, решена для всех $d$ и всех типов вложимости. Однако эта задача допускает естественное обобщение: вместо обычных дистанционных графов можно рассматривать мультидистанционные графы. Граф называется мультидистанционным в $\mathbb{R}^d$ с множеством расстояний $A$, если его вершины можно так отобразить в точки $\mathbb{R}^d$, что расстояние между образами любых двух соединенных ребром вершин будет лежать в множестве $A$. Аналогично обычным дистанционным графам, можно рассматривать строгую/нестрогую и инъективную/неинъективную $A$-вложимость в $\mathbb{R}^d$. Сложность распознавания $A$-вложимых в $\mathbb{R}^d$ графов изучена лишь для нескольких частных случаев $A$ и $d$. Для случая $d=1$ в [5] для каждого типа вложения описывается классификация всех конечных множеств $A$ на те, для которых задача распознавания $A$-вложимых в $\mathbb{R}$ множеств является полинамиально разрешимой, и те, для которых эта задача является $\mathrm{NP}$-трудной. Случай $A=(0, 1]$ изучался в [6], [7], доказано, что задача разпознавания строго инъективно $(0, 1]$-вложимых в $\mathbb{R}^d$ графов является полиномиально разрешимой для $d=1$ и $\mathrm{NP}$-трудной для $d=2$. Мы предлагаем метод сведения задачи распознавания инъективно вложимых графов с одним разрешенным расстоянием к задаче распознавания инъективно $A$-вложимых графов для некоторых множеств $A$. При $d \geqslant 3$ этот метод позволяет доказать, что для любого конечного множества $A$, любые два элемента которого отличаются хотя бы в два раза, задача распознавания нестрого инъективно $A$-вложимых графов является $\mathrm{NP}$-трудной и почти для всех таких $A$ задача распознавания строго инъективно $A$-вложимых графов является $\mathrm{NP}$-трудной. Кажется вероятным, что в дальнейшем этот метод может быть применен для доказательства $\mathrm{NP}$-трудности задачи распознавания инъективно $A$-вложимых графов и для других классов множеств $A$, так как позволяет сводить доказательство $\mathrm{NP}$-трудности этой задачи к чисто геометрической (не связанной с вычислительной сложностью) задаче. В оставшейся части введения мы приведем основные определения и сформулируем доказанные в [3] результаты в том виде, в котором нам будет удобно их использовать. Во втором разделе этой статьи описывается общий метод сведения распознавания инъективно вложимых графов с одним разрешенным расстоянием к распознаванию инъективно $A$-вложимых графов. В третьем разделе статьи этот метод применяется для доказательства $\mathrm{NP}$-трудности задачи распознавания инъективно $A$-вложимых графов для некоторых классов множеств $A$. 2. Основные определения и ранее известные результатыОпределение 1. Пусть $G=(V, E)$ – граф с множеством вершин $V$ и множеством ребер $E$ и $A$ – произвольное множество положительных чисел. Инъективная функция $\varphi\colon V \to \mathbb{R}^d$ называется инъективным $A$-вложением $G$ в $\mathbb{R}^d$, если она переводит любые две соединенные ребром вершины в точки, расстояние между которыми лежит в $A$. Вложение называется строгим, если любые две не соединенные ребром вершины переводятся в точки, расстояние между которыми не лежит в $A$. Граф называется (строго) инъективно $A$-вложимым в $\mathbb{R}^d$, если для него существует (строгое) инъективное вложение в $\mathbb{R}^d$. Обозначение 1. Как и в [3], обозначим задачу распознавания (строго) инъективно $\{1\}$-вложимых в $\mathbb{R}^d$ графов как $\mathbb{R}^d$-UNIT-DIST-(STRICT)-INJ-EMB; задачу распознавания (строго) инъективно $A$-вложимых в $\mathbb{R}^d$ графов обозначим как $\mathbb{R}^d$-$A$-(STRICT)-INJ-EMB. Заметим, что задача $\mathbb{R}^d$-UNIT-DIST-(STRICT)-INJ-EMB эквивалентна задаче $\mathbb{R}^d$-$\{a\}$-(STRICT)-INJ-EMB для любого положительного $a$, так как $\{1\}$-вложение можно превратить в $\{a\}$-вложение, а $\{a\}$-вложение – в $\{1\}$-вложение с помощью гомотетии. Теорема $1$ из [3] утверждает, что задачи $\mathbb{R}^d$-UNIT-DIST-INJ-EMB и $\mathbb{R}^d$-UNIT-DIST-STRICT-INJ-EMB являются $\mathrm{NP}$-трудными при любом $d > 2$. Для работы со строгими вложениями нам потребуется не сама эта теорема, а используемая для ее доказательства конструкция и ее свойства, сформулированные в [3] в теореме $4$. Введем еще одно определение из [3] (обобщив его для $A$-вложений) и приведем замкнутую формулировку теоремы $4$ из [3] (ее оригинальная формулировка ссылается на ранее описанные в статье построения). Определение 2. Строгое инъективное $A$-вложение называется некритическим, если ни для каких трех вершин их образы не лежат на одной прямой. Теорема 1 [3; теорема 4]. Для любого $d > 2$ по любому графу $G$ можно за полиномиальное время построить такой граф $H$, что если для $G$ есть правильная раскраска в $3$ цвета, то для $H$ есть некритическое $\{1\}$-вложение в $\mathbb{R}^d$, а если для $G$ нет правильной раскраски в $3$ цвета, то для $H$ нет никакого $\{1\}$-вложения в $\mathbb{R}^d$. 3. План работы и формулировка основных результатовВ разделе 2 описывается общий подход к доказательству $\mathrm{NP}$-трудности распознавания инъективно $A$-вложимых в $\mathbb{R}^d$ графов с помощью построения стержней. В разделе 3 доказывается существование стержней для некоторого класса множеств $A$. Итоговым результатом работы являются следующие теоремы. Теорема 2. Если $d \geqslant 3$ и $A$ – конечное множество положительных чисел, в котором любые два элемента отличаются хотя бы в два раза, то задача распознавания инъективно $A$-вложимых в $\mathbb{R}^d$ графов является $\mathrm{NP}$-трудной. Теорема 3. Существует такое не более чем счетное множество $M$, что если $d \geqslant 3$ и $A$ – конечное множество положительных чисел, в котором любые два элемента отличаются хотя бы в два раза, с максимальным элементом $a$, причем $aM \cap A=\varnothing$, то задача распознавания строго инъективно $A$-вложимых в $\mathbb{R}^d$ графов является $\mathrm{NP}$-трудной. 2. $(u, v, a)$-стержни и их свойства1. Нестрогие вложенияОпределение 3. Пусть $A$ – множество положительных чисел, $a$ – положительное число. Граф $H$ с выделенными вершинами $u$ и $v$ называется (строгим) $(u, v, a)$-стержнем в $\mathbb{R}^d$ относительно множества расстояний $A$, если выполнены следующие условия: Обозначение 2. Пусть $G$ – граф, $H$ – граф с выделенными вершинами $u$ и $v$. Обозначим через $f_H(G)$ граф, построенный следующим образом: в графе $G$ каждое ребро заменили на копию $H$, отождествив один конец ребра с $u$, а второй с $v$. Обозначение 3. Для графа $G$ будем обозначать множество его вершин $V(G)$, а множество ребер – $E(G)$. Лемма 1. Пусть $G$ – граф, $H$ – $(u, v, a)$-стержень в $\mathbb{R}^d$ относительно множества положительных чисел $A$. Пусть $G'=f_H(G)$. Тогда: Доказательство. 1. Из второго пункта в определении стержня следует, что сужение на вершины $G$ инъективного $A$-вложения $G'$ является инъективным $\{a\}$-вложением $G$.
2. Рассмотрим инъективное $\{a\}$-вложение $\varphi$ графа $G$ в $\mathbb{R}^d$ и построим по нему инъективное $A$-вложение графа $G'$. Упорядочим произвольным образом ребра $G$; пусть $\{e_1, \dots, e_m\}$ – получившееся упорядочивание; обозначим через $H_i$ копию графа $H$, на которую ребро $e_i$ заменяется при построении $G'$. Будем заменять ребра $G$ на копии $H$ по очереди и достраивать вложение $\varphi$ для $H_i \setminus \{u, v\}$ так, что после каждого шага вложение будет оставаться инъективным. Построим для каждого $i \in \{0, \dots, m\}$ вложение $\varphi_i$ – инъективное продолжение $\varphi$ на $V(G) \cup V(H_1) \cup \dots \cup V(H_i)$ такое, что для любого $j \leqslant i$ сужение $\varphi_i$ на $V(H_j)$ является $A$-вложением $H_j$. Положим $\varphi_0=\varphi$. Построим $\varphi_{i+1}$ как продолжение $\varphi$. Пусть $a$, $b$ – концы ребра $e_{i+1}$. Рассмотрим произвольное инъективное вложение $\varphi'$ стержня $H_{i+1}$ в $\mathbb{R}^d$, при котором $\varphi'(u)=\varphi(a), \varphi'(v)=\varphi(b)$. Пусть $S$ – бесконечное семейство поворотов вокруг прямой $\varphi(a)\varphi(b)$ такое, что для любых $\psi_1$, $\psi_2$ из $S$ и для любой точки $x$, не лежащей на прямой $\varphi(a)\varphi(b)$, выполнено $\psi_1(x) \neq \psi_2(x)$ (легко проверить, что при $d > 2$ такое бесконечное семейство существует). Пусть $\varphi_{\psi}$ – такое отображение $V(G) \cup V(H_1) \cup \dots \cup V(H_{i+1}) \to \mathbb{R}^d$, что $\varphi_{\psi}(w)=\varphi_i(w)$ при $w \in V(G) \cup V(H_1) \cup \dots \cup V(H_i)$ и $\varphi_{\psi}(w)=\psi(\varphi'(w))$ при $w \in V(H_{i+1})$ (определение согласованно в пересечении $V(G) \cup V(H_1) \cup \dots \cup V(H_i)$ и $V(H_{i+1})$, так как $\varphi_i(a)= \varphi'(u)=\psi(\varphi'(u))$ и $\varphi_i(b)=\varphi'(v)=\psi(\varphi'(v))$). Для любого $\psi \in S$ отображение $\varphi_{\psi}$ будет удовлетворять всем требованием к $\varphi_{i+1}$, кроме инъективности. Из инъективности $\varphi_i$ и $\varphi'$ следует, что для любого $\psi \in S$ для любых $w_1, w_2 \in V(G) \cup V(H_1) \cup \dots \cup V(H_i)$ выполнено $\varphi_{\psi}(w_1) \neq \varphi_{\psi}(w_2)$ и для любых $w_1, w_2 \in V(H_{i+1})$ выполнено $\varphi_{\psi}(w_1) \neq \varphi_{\psi}(w_2)$, поэтому инъективность будет следовать из того, что для любых $w_1 \in V(G) \cup V(H_1) \cup \dots \cup V(H_i) \setminus \{a, b\}$ и $w_2 \in V(H_{i+1}) \setminus \{u, v\}$ выполнено $\varphi_{\psi}(w_1) \neq \varphi_{\psi}(w_2)$. Для фиксированных $w_1 \in V(G) \cup V(H_1) \cup \dots \cup V(H_i) \setminus \{a, b\}$ и $w_2 \in V(H_{i+1}) \setminus \{u, v\}$ значение $\varphi_{\psi}(w_1)$ не зависит от $\psi$, а значения $\varphi_{\psi}(w_2)$ различны для всех $\psi$, поэтому равенство $\varphi_{\psi}(w_1)=\varphi_{\psi}(w_2)$ выполнено не более, чем при одном $\psi$. Множество таких пар $w_1, w_2$ конечно, а $S$ бесконечно, поэтому найдется такое $\psi \in S$, что $\varphi_{\psi}$ инъективно, для этого $\psi$ положим $\varphi_{i+1}=\varphi_{\psi}$. Выполнив эту процедуру для всех ребер, получим $\varphi_m$ – инъективную функцию $G' \to \mathbb{R}^d$, сужение которой на любой $H_i$ является $A$-вложением. Любое ребро $G'$ является ребром некоторого $H_i$, поэтому $\varphi_m$ – инъективное $A$-вложение $G'$ в $\mathbb{R}^d$. Теорема 4. Пусть $A$ – некоторое множество положительных чисел, $d > 2$. Если для некоторого $a$ существует $(u, v, a)$-стержень в $\mathbb{R}^d$ относительно $A$, то задача распознавания инъективно $A$-вложимых в $\mathbb{R}^d$ графов является $\mathrm{NP}$-трудной. Доказательство. Можно построить $f_H(G)$ по $G$ за полиномиальное (по размеру $G$) время, и по лемме 1 это построение является сведением задачи $\mathbb{R}^d$-$\{a\}$-INJ-EMB (а значит, и $\mathbb{R}^d$-UNIT-DIST-INJ-EMB) к задаче $\mathbb{R}^d$-$A$-INJ-EMB. По теореме $1$ из [3] задача $\mathbb{R}^d$-UNIT-DIST-INJ-EMB является $\mathrm{NP}$-трудной, поэтому и задача $\mathbb{R}^d$-$A$-INJ-EMB является $\mathrm{NP}$-трудной. 2. Строгие вложенияАналог теоремы 4 для строгого вложения получается более слабым, а доказательство – немного более сложным. Формально мы будем сводить к распознаванию строго инъективно $A$-вложимых графов задачу раскраски графа в три цвета, используя в качестве одного из шагов сведения конструкцию из [3]. Это вызвано тем, что для того, чтобы построение вложения $G'$ по вложению $G$, аналогичное использованному в теореме 4, сработало, исходное вложение $G$ должно быть некритическим и никакие не соединенные ребром вершины не должны в нем лежать на расстоянии из $A$ друг от друга. Лемма 2. Пусть $G$ – граф, $H$ – строгий $(u, v, a)$-стержень в $\mathbb{R}^d$ относительно множества положительных чисел $A$. Пусть $G'=f_H(G)$. Тогда: Доказательство. 1. Из второго пункта в определении стержня следует, что сужение на вершины инъективного $A$-вложения $G'$ является инъективным $\{a\}$-вложением $G$.
2. В доказательстве второго пункта теоремы 4 потребуем, чтобы вложение $\varphi_i$ являлось некритическим. В остальном доказательство повторяет доказательство теоремы 4, за исключением того, что для того, чтобы вложение $\varphi_0$ было строгим, потребуется воспользоваться тем, что образы никаких двух вершин в исходном вложении не лежат на расстоянии из $A \setminus \{a\}$ друг от друга, и того, что проверка существования такого $\psi$, что вложение $\varphi_{\psi}$ является строгим и инъективным, потребует больше технических деталей. Мы опустим эту проверку, так как она полностью совпадает с аналогичной проверкой в доказательстве леммы $1$ из [3]. Лемма 3. Если существует какой-то (возможно нестрогий) $(u, v, a)$-стержень в $\mathbb{R}^d$ относительно $A$, то существует и строгий $(u, v, a)$-стержень в $\mathbb{R}^d$ относительно $A$. Доказательство. Пусть $H$ – $(u, v, a)$-стержень в $\mathbb{R}^d$ относительно $A$. Пусть $\varphi$ – вложение из первого пункта определения стержня. Пусть $H'$ – граф, полученный из $H$ добавлением ребер $(x, y)$ для всех таких $x, y \in V(H)$, что расстояние между $\varphi(x)$ и $\varphi(y)$ лежит в $A$. Тогда $H'$ является строгим $(u, v, a)$-стержнем в $\mathbb{R}^d$ относительно $A$. Действительно, первый пункт определения выполняется для того же вложения $\varphi$, так как любые две вершины с образами на расстоянии из $A$ стали соединены ребром, а любые две вершины с образами не на расстоянии из $A$ остались не соединены ребром; второй пункт определения выполнен, так как он не может перестать выполняться при добавлении ребер. Теорема 5. Существует такое не более чем счетное множество $M$, что для любого $d$ и для любого такого множества положительных чисел $A$, что для некоторого $a \in A$ существует (возможно нестрогий) $(u, v, a)$-стержень в $\mathbb{R}^d$ относительно $A$ и $aM \cap A=\varnothing$, задача распознавания инъективно $A$-вложимых в $\mathbb{R}^d$ графов является $\mathrm{NP}$-трудной. (Через $aM$ обозначено множество $\{ax\mid x \in M\}$). Доказательство. Рассмотрим все графы, которые можно раскрасить в $3$ цвета. Для каждого такого графа $G$ и каждого $d > 3$ обозначим через $h_d(G)$ строящийся по нему граф из теоремы 4 и зафиксируем одно его некритическое $\{1\}$-вложение $\varphi_{G, d}$ в $\mathbb{R}^d$ (хотя бы одно такое вложение существует по теореме 4). Пусть $M$ – множество всех попарных расстояний между образами не соединенных ребром вершин во всех зафиксированных вложениях (очевидно это множество не более чем счетно). Пусть $A$ – некоторое множество положительных чисел, $a \in A$, множество $A$ не пересекается с $aM$ и существует $(u, v, a)$-стержень $H$. По лемме 3 из этого следует, что существует строгий $(u, v, a)$-стержень $H'$. Покажем, что композиция построений из теоремы 4 и из леммы 2 является сведением задачи о $3$-раскрашиваемости графа к задаче распознавания строго инъективно $A$-вложимых графов и, следовательно, эта задача является $\mathrm{NP}$-трудной.
Если граф $G$ является $3$-раскрашиваемым, то по построению $M$ для графа $h_d(G)$ существует такое некритическое $\{1\}$-вложение $\varphi_{G, d}$, что образы любых двух не соединенных ребром вершин лежат на расстоянии из $M$. С помощью гомотетии получим из этого вложения такое некритическое $\{a\}$-вложение, что образы любых двух не соединенных ребром вершин лежат на расстоянии из $aM$. Из условия $aM \cap A=\varnothing$ получаем, что образы никаких двух несоединенных ребром вершин не лежат на расстоянии из $A$, т.е. образы никаких двух вершин не лежат на расстоянии из $A\setminus \{a\}$. По лемме 2 из этого следует, что $f_{H'}(h_d(G))$ является строго инъективно $A$-вложимым. Если $f_{H'}(h_d(G))$ является строго инъективно $A$-вложимым в $\mathbb{R}^d$, то по лемме 2 граф $h_d(G)$ является инъективно $\{a\}$-вложимым в $\mathbb{R}^d$ и по теореме 4 $G$ является $3$-раскрашиваемым. Теоремы 4 и 5 сводят доказательство $\mathrm{NP}$-трудности распознавания $A$-вложимых графов к построению стержня относительно множества расстояний $A$. Заметим, что эта задача является чисто геометрической, т.е. не использует сложность вычислений. В оставшейся части статьи описывается построение стержней для некоторых множеств $A$. 3. Построение стержнейВ этом разделе мы построим стержень в $\mathbb{R}^{d}$ относительно множества $A$ для любого $d \geqslant 2$ и любого множества $A$ такого, что любые два элемента $A$ отличаются хотя бы в два раза. Опишем граф, про который мы будем доказывать, что он является стержнем. Пусть $G(d, n)=(V, E)$, где $V=\{1, \dots, d+2(1+d(n-1))\}$, и $(u, v) \in E$ тогда и только тогда, когда $u \leqslant d$ или $v \leqslant d$. Пусть $B=\{1, \dots, d\}$, $C=V \setminus B$. Тогда $V=B \sqcup C$, причем $|B|=d$, $|C|=2(1+d(n-1))$ и между любыми двумя вершинами из $B$ есть ребро, между любыми двумя вершинами из $C$ нет ребра и между любой вершиной из $B$ и любой вершиной из $C$ есть ребро. Иными словами, $G(d, n)$ разбивается на клику из $d$ вершин и независимое множество из $2(1+d(n-1))$ вершин, причем любая вершина из клики соединена с любой вершиной из независимого множества. Мы будем доказывать, что для любого $d \geqslant 2$ и любого множества $A$ такого, что любые два элемента $A$ отличаются хотя бы в два раза, граф $G(d, |A|)$ является $(u, v, a)$-стержнем в $\mathbb{R}^d$ относительно $A$ для $a=\max A$ и любых различных $u$ и $v$ из $B$ (например, для $u=1$, $v=2$). Проверим, что первый пункт определения стержня выполнен. Лемма 4. Если $|A|=n$, $d \geqslant 2$, то существует инъективное $A$-вложение $G(d, n)$ в $\mathbb{R}^d$ такое, что образы никаких трех вершин не лежат на одной прямой. Доказательство. Пусть Пусть $V(G(d, n))=B \sqcup C$ – разбиение $G(d, n)$ на клику из $d$ вершин и независимое множество из $2(1+d(n-1))$ вершин. Для упрощения описания конструкции вложения будем отождествлять вершины графа с их образами при вложении. Разместим вершины из $B$ в вершинах правильного $(d-1)$-мерного симплекса со стороной $a_n$. Надо проверить, что в $\mathbb{R}^d$ найдутся такие $2(1+d(n- 1))$ точек, что расстояние между ними и любыми вершинами из $B$ будет лежать в $A$, тогда можно разместить в этих точках вершины из $C$ и получить искомое вложение. Найдем по $1+d(n- 1)$ точек в каждом из открытых полупространств, на которые $\mathbb{R}^d$ разбивается $(d-1)$-мерным подпространством, содержащим вершины из $B$. Зафиксируем одно из полупространств. Для каждой точки $x$ из $d$ точек в $B$ рассмотрим множество точек в этом полупространстве, удаленных на $a_n$ от всех остальных точек из $B$. Это множество является полуокружностью с диаметром $2a_n$ и $x$ лежит на одном из ее концов, поэтому для каждого $i \leqslant n$ на ней найдется точка, удаленная от $x$ на $a_i$. Все такие точки удалены от каждой из точек из $B$ на расстояние из $A$. Точки, удаленные от $x$ на $a_n$, совпадают для разных $x$, а все остальные точки различны (так как упорядоченные наборы расстояний от них до точек из $B$ различны). Таким образом, в каждом открытом подпространстве есть по $1+d(n-1)$ различных точек, а во всем пространстве есть $2(1+d(n-1))$ различных точек, расстояние от каждой из которых до каждой из точек в $B$ лежит в $A$. Значит, отобразив в эти точки вершины графа из $C$, получим инъективное $A$-вложение $G(d, n)$ в $\mathbb{R}^d$. Образы всех вершин лежат на границе пересечения $d$ шаров с центрами в вершинах из $B$ и радиусом $a_n$, поэтому никакие три из них не лежат на одной прямой. Для доказательства того, что второй пункт определения стержня выполнен, надо показать, что при любом вложении клики $B$, при котором не все ее ребра будут иметь длину $a_n$, не найдется $2(1+d(n-1))$ различных точек, лежащих на расстоянии из $A$ от образов всех вершин из $B$. Для фиксированного упорядоченного набора расстояний от образов вершин из $B$ существует не более двух точек с таким набором расстояний, поэтому достаточно доказать, что если не любое ребро из $B$ имеет длину $a_n$, то наборов расстояний, для которых существует хотя бы одна такая точка, меньше, чем $1+d(n-1)$. Мы покажем, что в этом случае таких наборов расстояний, что для любых трех вершин выполнено неравенство треугольника, меньше, чем $1+d(n-1)$. Для этого докажем следующую комбинаторную лемму. Определение 4. Раскраска ребер графа в $n$ цветов $\{1, \dots, n\}$ удовлетворяет неравенству треугольника, если в любом треугольнике два максимальных по номеру цвета совпадают. Лемма 5. Пусть $G$ – полный граф на $d+1$ вершине, $H$ – его индуцированный подграф на $d$ вершинах. Тогда любую раскраску ребер $H$ в $n$ цветов можно не более, чем $1+d(n-1)$ способами дополнить до удовлетворяющей неравенству треугольника раскраски ребер $G$, причем равенство достигается только если все ребра $H$ покрашены в цвет $n$. Доказательство. Если раскраска $H$ не удовлетворяет неравенству треугольника, то ее нельзя ни одним способом дополнить до раскраски, удовлетворяющей неравенству треугольника, поэтому далее будем считать, что раскраска $H$ удовлетворяет неравенству треугольника.
Докажем утверждение леммы индукцией по количеству цветов $n$. Для $n=1$ утверждение тривиально: все ребра $H$ всегда покрашены в цвет $n$ и существует только один способ докрасить оставшиеся ребра в единственный цвет. Докажем переход от $n$ к $n+1$. Зафиксируем раскраску ребер $H$. Обозначим $x$ вершину $G$, не лежащую в $H$. Рассмотрим подграф $H$, который получается из $H$ удалением всех ребер цвета $n$, обозначим его $H'$. Заметим, что для любых трех различных вершин $u, v, w \in V(H)$, если $(u, v) \in E(H')$ и $(v, w) \in E(H')$, то и $(u, w) \in E(H')$, т.е. все компоненты связности $H'$ являются кликами. Действительно, если это не так, то в графе $H$ ребро $(u, w)$ покрашено в цвет $n$, а ребра $(u, v)$ и $(v, w)$ – в цвета с меньшим номером, что противоречит тому, что раскраска $H$ удовлетворяет неравенству треугольника. Кроме того, если в удовлетворяющем неравенству треугольника продолжении раскраски какая-то вершина соединена ребром цвета $n$ с вершиной $x$, то и все остальные вершины из той же компоненты связности $H'$ должны быть соединены с $x$ ребром цвета $n$. Действительно, если вершина $u$ соединена с $x$ ребром цвета $n$, а вершина $v$ из той же компоненты связности – ребром другого цвета, то ребро $(u, x)$ – единственное ребро цвета $n$ в треугольнике с вершинами $x, u, v$ и раскраска не удовлетворяет неравенству треугольника. Наконец, если две вершины лежат в разных компонентах связности $H'$, то при любом удовлетворяющем неравенству треугольника продолжении раскраски хотя бы одна из них соединена с вершиной $x$ ребром цвета $n$, так как иначе в треугольнике с вершинами в этих двух вершинах и $x$ ровно одно ребро покрашено в цвет $n$. Итак, в любом удовлетворяющем неравенству треугольника продолжении раскраски либо все вершины соединены с вершиной $x$ ребром цвета $n$, либо есть ровно одна компонента связности $H'$, все вершины которой соединены с $x$ ребрами цветов, меньших, чем $n$, по номеру, а все вершины из остальных компонент связности соединены с $x$ ребром цвета $n$. Пусть $H'$ разбивается на $k$ компонент связности $H_1', \dots, H_k'$, состоящих из $d_1, \dots, d_k$ вершин соответственно. Тогда по предположению индукции ребра, соединяющие $H_i$ и $x$, можно не более, чем $1+d_i(n-2)$ способами раскрасить в цвета из $\{1, \dots, n-1\}$ так, чтобы на них соблюдалось неравенство треугольника, поэтому количество способов продолжить раскраску $H$ до раскраски $G$ не превосходит причем в последнем неравенстве равенство достигается только при $d=k$, т.е. только когда в $H'$ нет ребер, т.е. только когда все ребра $H$ покрашены в цвет $n$.Завершим доказательство того, что граф $G(d, n)$ является стержнем в $\mathbb{R}^d$ относительно $n$-элементных множеств, в которых любые два элемента отличаются хотя бы в два раза. Теорема 6. Пусть $A=\{a_1, \dots, a_n\}$ и для любого $i$ выполнено $2a_i < a_{i+1}$. Тогда граф $G(d, n)$ является $(1, 2, a_n)$-стержнем в $\mathbb{R}^d$ относительно $A$. Доказательство. Пусть $V(G(d, n))=B \sqcup C$ – разбиение $G(d, n)$ на клику из $d$ вершин и независимое множество из $2(1+d(n-1))$ вершин. Первый пункт в определении стержня выполнен по лемме 4. Проверим второй пункт в определении стержня. Рассмотрим произвольное инъективное $A$-вложение $G(d, n)$ в $\mathbb{R}^d$. Построим по этому вложению раскраску ребер $G(d, n)$ в $n$ цветов: покрасим ребро в цвет $i$, если расстояние между образами его концов равно $a_i$. Из неравенства треугольника в $\mathbb{R}^d$ и того, что любые два элемента из $A$ отличаются хотя бы в два раза, следует, что эта раскраска удовлетворяет неравенству треугольника. Значит для каждой вершины $i$ из $C$ задаваемая ей раскраска полного графа на вершинах $B \cup \{i\}$ является продолжением раскраски полного графа на $d$ вершинах до удовлетворяющей неравенству треугольника раскраски полного графа на $d+1$ вершине. Если для каких-то вершин из $C$ эти продолжения совпадают, то для их образов совпадают упорядоченные наборы расстояний от образов вершин из $B$, поэтому каждое продолжение раскраски встречается не более, чем два раза. Значит различных продолжений раскрасок не менее, чем $1+d(n-1)$. По лемме 5 из этого следует, что все ребра между вершинами из $B$ раскрашены в цвет $n$, т.е. расстояние между образами любых двух вершин из $B$ равно $a_n$, в частности расстояние между образами вершин $1$ и $2$ равно $a_n$. Доказательство теорем 2, 3. По теореме 6 для множества $A$ из теорем 2 и 3 существуют $(u, v, a)$-стержни. По теореме 4 из этого следует утверждение теоремы 2, а по теореме 5 – утверждение теоремы 3.
Цитирование в формате AMSBIB
\RBibitem{Sok24} |
|
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|