Периодический граф (геометрия) - Periodic graph (geometry)

Евклидово граф (граф вкладывается в некотором евклидове пространства ) является периодическим , если существует базис этого евклидова пространства, соответствующие переводы индуцируют симметрии этого графа (т.е., применение любого такого перевода на графику , встроенной в евклидове пространства листьев графа без изменений). Эквивалентно периодический евклидов граф - это периодическая реализация абелевого накрывающего графа над конечным графом. Евклидов граф равномерно дискретен, если между любыми двумя вершинами существует минимальное расстояние. Периодические графы тесно связаны с мозаикой пространства (или сотами) и геометрией их групп симметрии , следовательно, с геометрической теорией групп , а также с дискретной геометрией, теорией многогранников и подобными областями.

Большая часть усилий в периодических графах мотивированы приложениями к естественной науке и технике, в частности трехмерных кристаллических сеток для инженерии кристаллов , предсказания кристаллического (конструкция) , и моделирование поведения кристалла. Периодические графы также изучались при моделировании схем очень большой интеграции (СБИС) .

Базовая формулировка

Евклидова графа называется пара ( V ,  E ), где V представляет собой набор точек (иногда называемых вершинами или узлами) , а Е представляет собой множество ребер (иногда называемые облигации), где каждое ребро соединяет две вершины. В то время как ребро, соединяющее две вершины u и v , обычно интерпретируется как множество { u , v }, ребро иногда интерпретируется как отрезок прямой, соединяющий u и v, так что результирующая структура является комплексом CW . В многогранной и химической литературе существует тенденция называть геометрические графы сетками (в отличие от многогранных сетей ), а номенклатура в химической литературе отличается от номенклатуры теории графов. Большая часть литературы посвящена периодическим графам, которые равномерно дискретны в том смысле, что существует такое e > 0, что для любых двух различных вершин их расстояние между ними равно | u - v | > е .

С математической точки зрения евклидов периодический граф - это реализация бесконечного абелевого накрывающего графа над конечным графом.

Получение периодичности

Идентификация и классификация кристаллографических пространственных групп заняли большую часть девятнадцатого века, а подтверждение полноты списка завершилось теоремами Евграфа Федорова и Артура Шенфлиса . Проблема была обобщена в восемнадцатой проблеме Дэвида Гильберта , а теорема Федорова – Шенфлиса была обобщена на более высокие измерения Людвигом Бибербахом .

Теорема Федорова – Шенфлиса утверждает следующее. Предположим, что дан евклидов граф в трехмерном пространстве такой, что верно следующее:

1. Он равномерно дискретен в том смысле, что существует такое e > 0, что для любых двух различных вершин их расстояние между ними равно | u - v | > е .
2. Он заполняет пространство в том смысле, что для любой плоскости в 3-пространстве существуют вершины графа по обе стороны от плоскости.
3. Каждая вершина имеет конечную степень или валентность .
4. Под группой симметрии геометрического графа имеется конечное число орбит вершин.

Тогда евклидов граф является периодическим в том смысле, что векторы трансляций в его группе симметрии охватывают лежащее в основе евклидово пространство, а его группа симметрии является кристаллографической пространственной группой .

Интерпретация в науке и технике состоит в том, что, поскольку евклидов граф, представляющий материал, распространяющийся в пространстве, должен удовлетворять условиям (1), (2) и (3), некристаллические вещества от квазикристаллов до стекол должны нарушать (4). Однако за последнюю четверть века было обнаружено, что квазикристаллы обладают достаточно многими общими химическими и физическими свойствами с кристаллами, поэтому существует тенденция классифицировать квазикристаллы как «кристаллы» и соответствующим образом корректировать определение «кристалл».

Математика и вычисления

Большая часть теоретических исследований периодических графов сосредоточена на проблемах их генерации и классификации.

Проблемы классификации

Большая часть работы по проблемам классификации была сосредоточена на трех измерениях, в частности, на классификации кристаллических сетей , то есть периодических графов, которые могли бы служить в качестве описаний или схем размещения атомов или молекулярных объектов со связями, обозначенными краями, в кристалле. . Одним из наиболее популярных критериев классификации является изоморфизм графов, не путать с кристаллографическим изоморфизмом . Два периодических графа часто называют топологически эквивалентными, если они изоморфны, хотя и не обязательно гомотопны . Даже при том , что проблема изоморфизма графов является многочлен времени приводимого к хрустальной чистой топологической эквивалентности (создание топологической эквивалентности кандидата за «вычислительно неразрешимыми» в том смысле , что не за полиномиальное время вычислимым ), кристалл чистый , как правило , рассматриваются как роман , если и только если топологически эквивалентная сеть неизвестна. Это привлекло внимание к топологическим инвариантам.

Один инвариант - это массив минимальных циклов (часто называемых кольцами в химической литературе), расположенных вокруг общих вершин и представленных в символе Шлафли . Циклы кристаллической сети связаны с другим инвариантом, инвариантом координационной последовательности (или карты оболочки в топологии), который определяется следующим образом. Во-первых, последовательность расстояний от вершины v в графе - это последовательность n ₁ , n ₂ , n ₃ , ..., где n _i - количество вершин на расстоянии i от v . Координационная последовательность - это последовательность s ₁ , s ₂ , s ₃ , ..., где s _i - средневзвешенное значение i -ых элементов последовательностей расстояний вершин (орбит) кристаллических сетей, где веса - это асимптотические пропорции вершин каждой орбиты. Совокупные суммы координационной последовательности обозначают топологическую плотность , а сумма первых десяти членов (плюс 1 для нулевого члена) - часто обозначаемая TD10 - является стандартным поисковым термином в базах данных кристаллической сети. См. Математический аспект топологической плотности, который тесно связан со свойством больших отклонений простых случайных блужданий.

Другой инвариант возникает из связи между мозаиками и евклидовыми графами. Если мы рассматриваем тесселяцию как совокупность (возможно многогранных) твердых областей, (возможно, многоугольных) граней, (возможно линейных) кривых и вершин, то есть как CW-комплекс, то кривые и вершины образуют евклидов граф ( или 1-скелет ) мозаики. (Кроме того, граф смежности плиток индуцирует другой евклидов граф.) Если в тесселяции конечное число прототипов , а тесселяция периодическая, то результирующий евклидов граф будет периодическим. Если двигаться в обратном направлении, прототипы мозаики, 1-скелет которой (топологически эквивалентен) заданному периодическому графу, имеют другой инвариант, и именно этот инвариант вычисляется компьютерной программой TOPOS.

Создание периодических графиков

Существует несколько существующих алгоритмов периодического перечисления графов, включая модификацию существующих сетей для создания новых, но, по-видимому, существует два основных класса счетчиков.

Одним из основных систематических кристаллических чистых алгоритмов перечисления сохранилось основано на представлении мозаик путем обобщения символа Шлефл по Б. Делоном и Andreas платья, с помощью которой любой тесселяция (любой размерности) , может быть представлена с помощью конечной структуры, которую мы может называться символом Дресс-Делейни . Любой эффективный счетчик символов Дресс-Делани может эффективно перечислить те периодические сети, которые соответствуют мозаике. Счетчик трехмерных символов Дресс-Делани работы Delgado-Friedrichs et al. предсказал несколько новых кристаллических сетей, которые позже были синтезированы. Между тем, двумерный счетчик Дресс-Делани, генерирующий сетку двумерного гиперболического пространства , которое хирургическим путем рассекается и обертывается вокруг трехпериодической минимальной поверхности, такой как Гироид , Алмаз или Примитив , создал множество новых кристаллических сетей.

Другой существующий счетчик в настоящее время сосредоточен на создании правдоподобных кристаллических сетей цеолитов . Расширение группы симметрии на 3-пространство позволяет охарактеризовать фундаментальную область (или область) 3-пространства, пересечение которой с сетью индуцирует подграф, который в общем положении будет иметь по одной вершине из каждой орбиты вершин. Этот подграф может быть или не быть связным, и если вершина лежит на оси вращения или какой-либо другой фиксированной точке некоторой симметрии сети, вершина обязательно может лежать на границе любой фундаментальной области. В этом случае сеть может быть сгенерирована путем применения группы симметрии к подграфу в фундаментальной области. Были разработаны другие программы, которые аналогичным образом генерируют копии исходного фрагмента и склеивают их в периодический граф.

Смотрите также

• Периодические графики как модели кристаллов для дизайна.

Рекомендации

дальнейшее чтение

• Конвей, JH ; Burgiel, H .; Гудман-Штраус, К. (2008), Симметрии вещей , А.К. Питерс
• Kotani, M .; Сунада, Т. (2000), "Отображения Альбанезе и внедиагональная долгая асимптотика теплового ядра", Comm. Математика. Phys. , 209 (3): 633-670, Bibcode : 2000CMaPh.209..633K , DOI : 10.1007 / s002200050033
• Kotani, M .; Сунада, Т. (2003), "Спектральная геометрия кристаллических решеток", Contemporary Math. , Современная математика, 338 : 271-305, DOI : 10,1090 / conm / 338/06077 , ISBN 9780821833834

• Kazami, T .; Учияма, К. (2008), "Случайные блуждания на периодических графов", Труды Американского математического общества , 360 (11): 6065-6087, DOI : 10,1090 / S0002-9947-08-04451-6 .