Граф Эрдёша — Диофанта — это множество точек на плоскости с целочисленными координатами, попарные расстояния между которыми являются целыми числами, причём это множество нельзя расширить добавлением других точек. Эквивалентно это множество можно описать как полный граф с вершинами на целочисленной решётке , такой что расстояния между любыми двумя вершинами целочисленны, а для всякой другой точки решётки расстояние хотя бы до одной вершины графа не является целым.
Графы Эрдёша — Диофанта названы в честь Пала Эрдёша и Диофанта Александрийского. Графы образуют подмножество класса диофантовых фигур —полных графов на диофантовой плоскости, у которых все рёбра имеют целочисленную длину. Графы Эрдёша — Диофанта — это в точности те диофантовы фигуры, которые невозможно расширить. Существование графов Эрдёша — Диофанта следует из теоремы Эрдёша — Эннинга, согласно которой бесконечные диофантовы фигуры должны быть коллинеарны на диофантовой плоскости. Следовательно, любой процесс расширения неколлинеарной диофантовой фигуры путём добавления вершин в конце концов приводит к фигуре, которую уже расширить нельзя.
Примеры Любое множество из нуля точек или из одной точки тривиально расширяемо, а любое диофантово множество из двух точек можно расширить точками, лежащими на той же прямой. Таким образом, всякое диофантово множество, содержащее менее трёх точек, допускает расширение, а значит, графов Эрдёша — Диофанта с менее чем тремя вершинами не существует.
С помощью компьютерного поиска Конер и Курц показали, что графы Эрдёша — Диофанта с тремя вершинами существуют. Наименьший треугольник Эрдёша — Диофанта имеет стороны 2066, 1803 и 505. Следующий по величине треугольник Эрдёша — Диофанта имеет стороны 2549, 2307 и 1492. В обоих случаях сумма длин трёх сторон чётна. Бранчева доказала, что это свойство выполняется для всех треугольников Эрдёша — Диофанта, полная длина любого замкнутого пути в графе Эрдёша — Диофанта всегда чётна.
Примером графа Эрдёша — Диофанта с четырьмя вершинами является полный граф, образованный вершинами прямоугольника со сторонами 4 и 3.
Примечания
Литература
Категория:Пал Эрдёш Категория:Алгебраическая геометрия Категория:Комбинаторная геометрия Категория:Геометрические графы Категория:Арифметические проблемы планиметрии Категория:Графы, имеющие собственные названия