Эрдеш-диофантов график представляет собой объект в математической теме диофантовых уравнений , состоящих из множества целых точек на целочисленных расстояниях в плоскости , которая не может быть расширена с помощью каких - либо дополнительных пунктов. Эквивалентно его можно описать как полный граф с вершинами, расположенными на целочисленной квадратной сетке. такие, что все взаимные расстояния между вершинами являются целыми числами, в то время как все остальные точки сетки имеют нецелое расстояние по крайней мере до одной вершины.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/6/64/5-point_Erd%C5%91s-Diophantine_graph.svg/220px-5-point_Erd%C5%91s-Diophantine_graph.svg.png)
Графы Эрдеша-Диофантова названы в честь Пола Эрдеша и Диофанта Александрийского . Они образуют подмножество множества диофантовых фигур , которые определяются как полные графы на диофантовой плоскости, для которых длины всех ребер являются целыми числами ( графы единичных расстояний ). Таким образом, графы Эрдеша – Диофантовы - это в точности диофантовы фигуры, которые не могут быть расширены. Существование графов Эрдеша – Диофантова следует из теоремы Эрдеша – Эннинга , согласно которой бесконечные диофантовы фигуры должны быть коллинеарны на диофантовой плоскости. Следовательно, любой процесс расширения неколлинеарной диофантовой фигуры путем добавления вершин должен в конечном итоге привести к фигуре, которая больше не может быть расширена.
Примеры
Любое множество из нуля или одной точки можно тривиально расширить, а любое диофантово множество из двух точек можно расширить на большее количество точек на той же прямой. Следовательно, все диофантовы множества с менее чем тремя узлами могут быть расширены, поэтому графы Эрдеша – диофантова с менее чем тремя узлами не могут существовать.
Путем численного поиска Kohnert & Kurz (2007) показали, что трехузловые графы Эрдеша – диофантова действительно существуют. Наименьший треугольник Эрдеша-Диофантова характеризуется длинами ребер 2066, 1803 и 505. Следующий больший треугольник Эрдеша-Диофантова имеет ребра 2549, 2307 и 1492. В обоих случаях сумма трех длин ребер четна. Бранчева доказала, что это свойство выполняется для всех треугольников Эрдеша – диофантова. В более общем смысле, общая длина любого замкнутого пути в графе Эрдеша – Диофантова всегда четна.
Примером четырехузлового графа Эрдеша – Диофантова является полный граф, образованный четырьмя узлами, расположенными в вершинах прямоугольника со сторонами 4 и 3.
Рекомендации
- Конерт, Аксель; Курц, Саша (2007), «Заметка о диофантовых графах Эрдеша и диофантовых коврах», Mathematica Balkanica , New Series, 21 (1-2): 1-5, arXiv : math / 0511705 , MR 2350714
- Димиев, Станчо; Марков, Красимир (2002), "Целые числа Гаусса и диофантовы фигуры", Математика и математическое образование , 31 : 88–95, arXiv : math / 0203061