Диаметры дистанционных графов в псевдоевклидовых пространствах

В этой работе мы изучаем обобщение дистанционных графов на. случай псевдоевкли-дова пространства R^r,s ил и Q^r,s со скалярным произведением, порожденным квадратичной формой I _T,_s (x ₁ , ..., x_r+s) = x1 + ... + x² — x²₊₁ — ... — x^ +g. А именно, изучаем граф G ( V,I _t , _s ) = ( V,E ),t_№

V G{R^r+s, Q^r+s};   E = {(x , у) е V² |   I_T> — у) = 1}.

Подобные графы подробно изучались в случае обычного евклидова, пространства, где s = 0. Более подробно про классические дистанционные графы в R^s можно найти в [1]. Про дистанционные графы в Q^r можно найти в [2,3].

В этой работе мы докажем, что значения диаметров G(R², Ii , i) и G(Q², Ii , i ) равны 3 и 4 соответственно, а диаметры G ( R^{t + s} , I _TiS ) и G(Q^r+s, I _TiS ) не превосходят 5 для произвольных т, s = 0.

Эти результаты показывают принципиальное различие случаев s = 0 и s = 0, поскольку для всех т, s = 0 графы G(R^r+s, I _T,s ) и G(Q^r+s, I _Tg связные и с очень маленьким диаметром.

В евклидовом случае для т > 2 диаметры графов G(R^r, I _r ) и G(Q^r, I _r ) бесконечны, кроме графов G(Q,I _T ), т < 4, которые несвязные.

Стоит отметить, что термин «дистанционный» не очень применим к изучаемым графам, поскольку квадратичная форма I _T,_S не является положительно определенной и следовательно, не порождает метрику.

• 2.    Случай (г, s) = (1,1)

Заметим, что форму І і,і (х,у) = х² — у² можно линейной заменой координат привести к форме R(х,y) = уу, и рассматриваемый граф у нас от этого не поменяется. Тогда вектор между любыми двумя соседними точками этого графа имеет вид (х, X), х = 0.

Теорема 1. Диаметр (G(R²,R)') равен 3.

Доказательство. Достаточно показать, что из точки 0 = (0, 0) можно добраться до любой точки (х,у) путем, состоящим из не более чем трех ребер, а также, что существуют две точки, между которыми не существует пути длины не больше 2.

Разберем несколько случаев.

• 1)    х = 0, у = 0.

Тогда возьмем а = 2^ ,b = 2^, с = -3. Несложно видеть, что а + b + с = 0, 1 + X +| = у.

• 2)    х = 0, у = 0.

Аналогично, возьмем а = 3х, b = 3х, с = — 3х.

• 3)    х = 0, у = 0. Для определенности пусть х > 0.

Необходимо подобрать а, b, с такие, что х = а + b + сиу = X + X + К

Предположим, что такие а, b, с нашлись. Введем величину р = аЬс. Тогда аЬ + Ьс + са = у • р. Построим многочлен

F (t) = (t — а)(t — b)(t — с) = t³ — (а + b + с)і + (аЬ + Ьс + са)і — аЬс = t³ — хі² + урі — р.

Докажем, что для любых х,у найдется такое р, что F (t) имеет три вещественных ненулевых корня. Тогда, развернув рассуждения в обратную сторону, мы найдем наш искомый путь.

Предположим, что х >  0. Рассмотрим точку хо = 2. Тогда

F (х) = (х )³—* (х )²+ р (ху—1) = — 8 ^+ р (ху—1).

Подберем достаточно маленькое отрицательное р так, чтобы F (хо) < 0, так можно сделать, поскольку — 8х³< 0.

Заметим, что F (0) = —р >  0, F (хо) < 0, и у многочлена F (t) старшая степень равна

• 1,    откуда следует, что у него три ненулевых корня.

Приведенные рассуждения можно повторить в случае х < 0, только р нужно брать положительным.

Опишем локусы точек на расстоянии 1, 2 и 3 от начала координат.

• •    На расстоянии 1 находятся точки вида (х, 1/х), х = 0.

• •    Если точка (х, у) находится на расстоянии 2, то х = а + b, у = X + X = щ ^и аЬ = ^

Тогда должно выполняться свойство х² = (а + b)² >  4аЬ =

Таким образом, на расстоянии 2 находятся точки (х, у), для которых ху <  0 или ху > 4.

• •    На расстоянии 3 находятся точки (х, у), для которых ху Е [0, 4).

Предложение 1. Кликовое число (G(R2,R)) равно 2.

Доказательство. Предположим противное, тогда существуют ненулевые а,b,с такие, что а + b + с = 0 11 і + | + | = 0.

Отсюда возникает уравнение ^ + | = ^Д, которое не имеет вещественных решений.

Теорема 2. Диаметр (G(Q², R)) равен 4.

Доказательство. Построим путь длины не больше 4 между точками (0, 0) и (ж, у).

Если жу = 1, то можно построить путь длины 1.

Без ограничения общности предположим, что у = 0. Тогда рассмотрим числа а = -У

, b = 2 А - Д с = 2 А - Д a = -1 (ж - Д

3 у         3       у           3 у)

Несложно видеть, что а + b + с + d = ж и ^ + | + | + ^ = у.

Осталось проверить, что диаметр нашего графа равен 4. Для этого покажем, что от точки (0, 0) до точки (1, —1) нельзя добраться за 3 ребра. Предположим противное, тогда существуют а, b, с G Q \ {0} такие, что а + b + с = 1 и ^ + ^ + | = —1.

1 + 1+

а b 1 — а — b

Отсюда следует, что а,b = 0, а + b = 1 и а — а + b — а b — b — аb — 0.

Рассмотрим соответствующую этому уравнению эллиптическую кривую ас² — а² с + Ьс² — а²b — Ь²с — аб² = 0 игщ QP². она эквивашчипа кривой у² = ж³ + ж² — ж и имеет ярлык Кремоны 20а2. Известно, что на этой кривой только б рациональных точек:

(—1:1: 0), (0:1:1), (0:1:0), (0:0: 1), (1:0:0), (1:0: 1).

Заметим, что никакая из этих точек не дает решения уравнения 1. Больше информации про эту кривую можно найти на странице [4].

3.    Произвольные r,s = 0

Пусть для определенности k = г — s > 0. Тогда можем заменить I_T,₈ на

R_s,_k (жі,... ,ж8,уі, ... ,у₈, 2і,... ,z_k ) = жіуі... +ж₈у₈ + 22 + ... + 2².

Теорема 3. Диаметр (G(R^r+⁸, R₈,_k )) не болите 3.

Для начала нам понадобится следующая лемма.

Лемма 1. Для любых (p,q) = (0, 0) и а существуют р и q* такие, что

(р — p*)(q — q*) = а и p'q' < 0.

Доказательство. Рассмотрим величину с = 0 и рассмотрим р* = р—с и q* = q — ^. Тогда первое соотношение заведомо выполняется, и надо подобрать такое с, чтобы выполнялось неравенство

(Р — с)(q — ^а) < 0. с

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

• 2)    q = о, р = о.

Если мы возьмем достаточно маленькое по модулю с, то sgn(p—с) = sgn(p). И возьмем с такого знака, чтобы —sgn(p) • sgn(a) • sgn(c) = — 1.

Доказательство теоремы 3. Построим путь длины не более 3 из 0 в точку

Р = (pi, ...,p _s ,q i ,...,q _s ,r i ,..., r _k ).

k

Рассмотрим А = 1 — Д^ г².

i=i

Применяя лемму 1, подберем числа pi,qi,... , Ps, q‘ такие, что для всех 1 <  г <  s выполнены следующие два соотношения:

• •    ⁽ р г - piXqt - q i ) = 4;

• •    piqi < ⁰

Заметим, что точки

^Р — ^(р1, . . . , ^ps, ^q 1 , . . . , ^q s , ^ri, . . . , ^rk)     И ^р — ^(р1, . . . , ^p_s, ^q i , . . . , ^q _s , ⁰, .. . , ⁰⁾

связаны ребром, поскольку

^(р1 ^{— p} 1 ^{)( q} 1 ^{— q}D + . . . ^{+ (p}s ^{— p} s ^{)( q} s ^{— q}s) ^{+ г}2 ⁺ . . . ^{+ г}2 = ^s •    ^{+ (1 — А)} = ¹

S

Теперь построим путь из Р ‘ до 0 длины 2.

Поскольку spiqi < 0, в силу замечания после теоремы 1 найдутся такие числа х г и y t, что х ⁺ y t = pt^P ⁺ , = ^sqi.

Рассмотрим два вектора

Несложно видеть, что R _s,k (X) = R _s,k (Y) = 1 и X + Y = Р ' .

Путь из вершин 0, X, Р‘,Р является путем длины 3 в графе G(Rⁿ, R _s,k )•

Пусть для определенности г >  s, k = г — s > 0. И тогда аналогично предыдущему разделу можем заменить I _T,_S на

R_s,k (хі,... ,x_s,yi,..., y_s, z i , ...,Z k ) = Х і у і ... +x _s y _s + z 1 + ... + z k .

Теорема 4. Диаметр (G(Q^r+s, R_s,k )) не больше 5.

Доказательство. Построим путь длины не более 5 из 0 в точку

Р = (pi,... ,p _s ,q i , ...,q _s ,r i ,.. .,r k ).

Подберем рациональные xi, yi,..., xs, ys так, что xiyi + ... + xsys + Г2 + ... + rk = 1.

Остается дойти до точки

^Р' = ⁽pi,... ^,Ps^,qi,...,qs) := ⁽pi ^—x i ^,...^,P s - ^x s , qi ^— yi^,...^,q_s^— y _s , ⁰,..., ⁰⁾

за 4 ребра.

Для каждого p t, q t по теореме 2 подберем 4 числа а, г ,Ь г ,С г ,сЦ такие, что a t + b i + c t + d t = p t - X i и   + + + ^ = s(q t - y t ) для формы s • xy.

Тогда можно рассмотреть ребра

(а1 ’ . . . , а S’         , . . . ,         ’ 0’ . . . ’ 0) ’ sai      sas

(bi,..., bs, sb”’... ’ sb"’ 0’""" ’0)’

(ci,...,cs,     ’...’     ’ 0’...’ 0)’

SC 1       sc _s

^{( d} 1 ’ . . . ’ ^d S ’ d ’ . . . ’ d ’ ⁰’ . . . ’ ⁰⁾.

Эта последовательность ребер дает путь из точки 0 до точки Р ‘.

4.    Заключение

В этой работе рассмотрен аналог дистанционного графа на случай псевдоевклидова пространства для случаев вещественного и рационального пространств. Показано, что эти графы сильно отличаются от стандартного определения дистанционного графа евклидова пространства. Диаметры этих графов вычислены для превдоевклидова пространства типа (1, 1), для произвольного типа (Т’ s) дана оценка сверху.