Арифметические графы

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Прикладная математика
117
УДК 519. 17
А. В. Бирюков, П. А. Бирюков АРИФМЕТИЧЕСКИЕ ГРАФЫ
Для любого натурального числа п и любого
множества A натуральных чисел обозначим через S (n, A) граф с вершинами 1, 2, п, в котором вершины x и у смежны, если х+уєА. Граф порядка п будем называть арифметическим, если он изоморфен графу S (n, A) для некоторого множества A. Содержательность этого понятия иллюстрируют следующие примеры.
(1) Для любого п полный граф Кп является арифметическим: он изоморфен графу S (n, A) для А={3,4,…, 2п-1}.
(2) Все простые цепи и простые циклы являются арифметическими графами. Положим Ап={4,п+2, п+4} для всех нечетных п& gt-3 и Ап={5,п+3, п+5} для всех четных п& gt-4. Граф S (n, A) является простой цепью с концевыми вершинами 1 и 2. Добавляя к множеству, А число 3, получаем простой цикл порядка п.
(3) Пусть А={3,5,7,., 2п-1}. Тогда S (n, A) -это полный двудольный граф Кт, т (при п=2т) или Кт, т+1 (при п=2т+1). Можно показать, что полный двудольный граф К^ не является арифметическим при 8& lt-ї-1. В частности, наименьший неарифметический граф — это звезда
Ки.
(4) Напомним, что колесо — граф порядка
п+1. полученный добавлением к простому циклу Сп новой вершины, смежной со всеми вершинами цикла (другими словами, граф изомор-
фен графу п- угольной пирамиды). Легко проверить, что при п =3,4, 5 граф Ж" является арифметическим. С другой стороны, можно показать, что если в арифметическом графе порядка п & gt-2 есть вершина степени п-1, то одна из остальных
вершин имеет степень к& gt-п-3. Следовательно, при п & gt-5 граф Жп не является арифметическим.
(5) Пусть, А = {3,5,7,11,13,15}. Граф S (8,A) изоморфен графу куба. Легко показать, что графы октаэдра и треугольной призмы также являются арифметическими. Примером неарифметического кубического графа является граф Петерсена.
Интересную серию арифметических графов образуют графы S (n, P), где Р — множество всех простых чисел. Все эти графы двудольны, поскольку любые две вершины одинаковой четности несмежны. Связность графа S (n, P) можно доказать по индукции, применяя теорему Чебышева: для любого п & gt-1 интервал (п, 2п) содержит хотя бы одно простое число р. Тогда вершина п графа S (n, P) смежна с вершинойр-п подграфа S (n-1,P). По индуктивному предположению этот подграф связен и, следовательно, граф S (n, P) связен.
На основании проведенных авторами вычислений можно высказать гипотезу: диаметр графа S (n, P) равен 3 для всех п & gt-4. Как легко видеть, эта гипотеза эквивалентна следующему утверждению о простых числах.
(*) Для любых двух натуральных чисел х& lt-у одинаковой четности существует такое натуральное число а& lt-у, что х+а и у+а простые числа.
Непосредственным следствием (*) является утверждение о том, что каждое четное число является разностью двух простых чисел. Это утверждение до сих пор не доказано и не опровергнуто [1], как и более сильные гипотезы Полиньяка и Диксона [2].
СПИСОК ЛИТЕРАТУРЫ
1. Серпинский В. Что мы знаем и чего не знаем о простых числах. — М.: ГИФМЛ, 1963. — 92 с.
2. Рибенбойм П. Рекорды простых чисел. //Успехи мат. наук, 1987. — Т. 42 — Вып. 5. — С. 119−176.
? Автор статьи:
Бирюков Альберт Васильевич
— докт. техн. наук, проф. каф. высшей математики КузГТУ. Тел. 8(3842)39−63−19
Бирюков Петр Альбертович
— канд. физ. -мат. наук, доц. каф. алгеб-вы и геометрии КемГУ. Тел. 8(3842)58−46−80

ПоказатьСвернуть
Заполнить форму текущей работой