Я задавал этот вопрос несколько недель назад в mathoverflow , но не получил ответа.
Здесь под 3D-сеткой с длиной стороны я имею в виду граф G = ( V , E ) с V = { 1 , … , k } 3 и E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | а - х | + | б - у | + | с , т. Е. Узлы размещаются в трехмерных целочисленных координатах между 1 и k , и узел соединяется не более чем с 6 другими узлами, которые отличаются точно одной координатой на одну.
Как называется этот график? Я буду использовать 3D-сетку, но, возможно, другие люди привыкли к 3D-сетке или 3D-решетке.
Какова ширина или траектория этого графика? Это уже где-то опубликовано?
Я уже знаю , что , то есть это действительно меньше , чем к 2 . Для меня это говорит о том, что стандартные аргументы, показывающие, что 2D-сетка k × k имеет ширину дерева и ширину пути k , не будут легко обобщаться.
Чтобы увидеть это, рассмотрим разложение пути, которое «охватывает» сетку, используя в основном наборы узлов вида . Соблюдайте | S c | ≤ ( 3 / 4 ) к 2 + O ( K ) , S 3 / 2 к быть самым большим таким набором. Наборы между S c и создаются путем перемещения по линии и требуют O ( k ) дополнительных узлов, чтобы быть разделителями. Точнее, использовать множества S c , d = { ( x , y , z ) ∣ ( x + y + z = c ∧ x ≤ d ) ∨ ( x + y + z = c ∧ x ≥ d ) }как разложение пробега .
У меня также есть идея для доказательства, которое показывает , но оно еще не закончено.
Ответы:
Ширина пути может быть определена как следствие некоторых известных результатов. FitzGerald [2] показал, что полоса пропускания P 3 k составляет ⌊ 3P3k P3k ⌊34k2+12k⌋ P3k ⌊34k2+12k⌋
К вашему сведению: я только что отправил англоязычную версию нашей статьи в arXiv.
источник
Путь прохождения трехмерных сеток был изучен Рёхей Суда , Йотой Отачи и Коичи Ямазаки в статье « Путь прохождения трехмерных сеток» , IEICE Tech. Отчет, 2009.
В реферате статьи утверждается, что
Однако точная граница не указана в аннотации, и в настоящее время я не могу получить доступ к полной статье. Возможно, вы можете связаться с авторами в частном порядке и опубликовать ответ на этот вопрос самостоятельно, если авторы готовы поделиться результатом.
источник