Гипотеза Гилберта–Поллака

Нерешенная проблема в теории графов

В математике гипотеза Гилберта–Поллака — недоказанная гипотеза об отношении длин деревьев Штейнера и евклидовых минимальных остовных деревьев для одних и тех же множеств точек на евклидовой плоскости . Она была предложена Эдгаром Гилбертом и Генри О. Поллаком в 1968 году. ^[1]

Заявление

Нерешенная проблема в информатике :

Равно ли отношение Штейнера евклидовой плоскости ?

2/{\sqrt {3}}

(еще нерешенные проблемы в информатике)

Для набора точек на плоскости кратчайшая сеть отрезков линий, соединяющая точки, имеющая только заданные точки в качестве конечных точек, является минимальным евклидовым остовным деревом набора. Может оказаться возможным построить более короткую сеть, используя дополнительные конечные точки, отсутствующие в заданном наборе точек. Эти дополнительные точки называются точками Штейнера, а кратчайшая сеть, которая может быть построена с их использованием, называется минимальным деревом Штейнера . Отношение Штейнера является супремумом по всем наборам точек отношения длин минимального евклидового остовного дерева к минимальному дереву Штейнера. Поскольку минимальное дерево Штейнера короче, это отношение всегда больше единицы. ^[2]

Примеры с точками, расположенными вдоль окружности единичного круга, где расположение из трех точек показывает наиболее оптимальное известное соотношение $2/{\sqrt {3}}\approx 1.155$

{\displaystyle 2/{\sqrt {3}}\approx 1.155} — Примеры с точками, расположенными вдоль окружности единичного круга, где расположение из трех точек показывает наиболее оптимальное известное соотношение $2/{\sqrt {3}}\approx 1.155$

Нижняя граница отношения Штейнера определяется тремя точками в вершинах равностороннего треугольника с единичной длиной стороны. Для этих трех точек минимальное евклидово остовное дерево использует два ребра треугольника с общей длиной два. Минимальное дерево Штейнера соединяет все три точки с точкой Штейнера в центре треугольника с меньшей общей длиной . Из-за этого примера отношение Штейнера должно быть не менее . ^[2] ${\sqrt {3}}$ ${\textstyle 2/{\sqrt {3}}\приблизительно 1,155}$

Гипотеза Гилберта-Поллака утверждает, что этот пример является наихудшим случаем для отношения Штейнера, и что это отношение равно . То есть, для каждого конечного множества точек на евклидовой плоскости минимальное евклидово остовное дерево не может быть длиннее, чем умноженная на длину минимального дерева Штейнера. ^[2] $2/{\sqrt {3}}$ $2/{\sqrt {3}}$

Попытка доказательства

Гипотеза известна своим доказательством Дин-Чжу Ду и Фрэнка Кван-Мин Хванга ^[3]^[2], которое, как позже выяснилось, имело серьезный пробел. ^[4]^[5]

Основываясь на ошибочном результате Ду и Хванга, Дж. Хайам Рубинштейн и Цзя Ф. Вэн пришли к выводу, что соотношение Штейнера справедливо также для двумерной сферы постоянной кривизны ^[6] , но из-за пробела в базовом результате Ду и Хванга результат Рубинштейна и Вэнга теперь также считается не доказанным. ^[7] $2/{\sqrt {3}}$

Ссылки

^ Гилберт, EN; Поллак, HO (январь 1968). «Минимальные деревья Штейнера». Журнал SIAM по прикладной математике . 16 (1): 1– 29. doi :10.1137/0116001. ISSN 0036-1399. S2CID 123196263.
^ abcd Du, DZ; Hwang, FK (1992-06-01). «Доказательство гипотезы Гилберта-Поллака о соотношении Штейнера». Algorithmica . 7 (1): 121– 135. doi :10.1007/BF01758755. ISSN 0178-4617. S2CID 36038781.
^ Du, DZ; Hwang, FK (1990-12-01). «Гипотеза Гилберта и Поллака о соотношении Штейнера верна». Труды Национальной академии наук . 87 (23): 9464– 9466. Bibcode :1990PNAS...87.9464D. doi :10.1073/PNAS.87.23.9464. ISSN 0027-8424. PMC 55186 . PMID 11607122. S2CID 9811160.
^ Иванов, АО; Тужилин, АА (2011-03-26). "Гипотеза Гилберта–Поллака о соотношении Штейнера все еще открыта". Algorithmica . 62 ( 1– 2): 630– 632. doi :10.1007/s00453-011-9508-3. S2CID 7486839.
^ Тужилин А., А.; Иванов О., А (2014-02-25). "Характерная область Ду–Хван: Уловка-22". arXiv : 1402.6079 [math.MG].
^ Рубинштейн, Дж.; Вэн, Дж. (1997-03-01). «Теоремы сжатия и соотношения Штейнера на сферах». Журнал комбинаторной оптимизации . 1 : 67– 78. doi :10.1023/A:1009711003807. ISSN 1382-6905. S2CID 35145869.
^ Иннами, Н.; Ким, Б.Х.; Машико, Ю.; Сиохама, К. (15 ноября 1990 г.). «Гипотеза Гилберта-Поллака о соотношении Штейнера все еще может быть открытой». Алгоритмика . 57 (4): 869–872 . doi : 10.1007/s00453-008-9254-3. ISSN 0178-4617. S2CID 30809157.

[1] Гилберт, EN; Поллак, HO (январь 1968). «Минимальные деревья Штейнера». Журнал SIAM по прикладной математике . 16 (1): 1– 29. doi :10.1137/0116001. ISSN 0036-1399. S2CID 123196263.

[AutoZ2-3-2] Du, DZ; Hwang, FK (1992-06-01). «Доказательство гипотезы Гилберта-Поллака о соотношении Штейнера». Algorithmica . 7 (1): 121– 135. doi :10.1007/BF01758755. ISSN 0178-4617. S2CID 36038781.

[3] Du, DZ; Hwang, FK (1990-12-01). «Гипотеза Гилберта и Поллака о соотношении Штейнера верна». Труды Национальной академии наук . 87 (23): 9464– 9466. Bibcode :1990PNAS...87.9464D. doi :10.1073/PNAS.87.23.9464. ISSN 0027-8424. PMC 55186 . PMID 11607122. S2CID 9811160.

[4] Иванов, АО; Тужилин, АА (2011-03-26). "Гипотеза Гилберта–Поллака о соотношении Штейнера все еще открыта". Algorithmica . 62 ( 1– 2): 630– 632. doi :10.1007/s00453-011-9508-3. S2CID 7486839.

[5] Тужилин А., А.; Иванов О., А (2014-02-25). "Характерная область Ду–Хван: Уловка-22". arXiv : 1402.6079 [math.MG].

[6] Рубинштейн, Дж.; Вэн, Дж. (1997-03-01). «Теоремы сжатия и соотношения Штейнера на сферах». Журнал комбинаторной оптимизации . 1 : 67– 78. doi :10.1023/A:1009711003807. ISSN 1382-6905. S2CID 35145869.

[7] Иннами, Н.; Ким, Б.Х.; Машико, Ю.; Сиохама, К. (15 ноября 1990 г.). «Гипотеза Гилберта-Поллака о соотношении Штейнера все еще может быть открытой». Алгоритмика . 57 (4): 869–872 . doi : 10.1007/s00453-008-9254-3. ISSN 0178-4617. S2CID 30809157.