Динамические монополии в регулярных графах

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


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

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

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

Прикладная математика
15
6. Снетков В. И., Снеткова А. В. Обоснование размера фильтра при сглаживании горногеологических показателей способом скользящего среднего // Проблемы развития минеральной базы Восточной Сибири. Сб. научн. тр. — Иркутск, 2003, с. 90−94.
7. Снетков В. И., Снеткова А. В. Теоретические основы сглаживания статистических рядов способом скользящей средней // Проблемы развития минеральной базы Восточной Сибири. Сб. научн. тр. -Иркутск, 2003, с. 111−120.
8. Снетков В. И. Динамическое прогнозирование параметров подсчёта запасов по слоям на глубину для жильных пегматитовых месторождений. — Маркшейдерский вестник. — 2005. -№ 2. — с. 36 — 41.
9. Четыркин Е. М. Статистические методы прогнозирования. — М.: Статистика, 1975. — 184 с.
? Автор статьи:
Снетков Вячеслав Иванович
— доц. каф. маркшейдерского дела Иркутского Государственного технического университета
УДК 519. 21
А. В. Бирюков, П.А. Бирюков
ДИНАМИЧЕСКИЕ МОНОПОЛИИ В РЕГУЛЯРНЫХ ГРАФАХ
Пусть G — связной граф с вершинами x 1, xn. Предпо-
ложим, что в любой из моментов времени ґ=0,1,2,… каждая вершина может находиться в одном из двух состояний 0,1. Обозначим состояние вершины
xi в момент t через Xj (t). Вектор х (ґ). =[ Х$),…, Хп (ґ) ] назовем состоянием графа G в момент ґ.
Вершина хі и все смежные с ней вершины образуют окрестность Б (х,). Зададим правило перехода от состояния х (ґ) к состоянию х (ґ+1):
(Т): Если в момент ґ не менее половины вершин из окрестности Б (х) находились в состоянии 1, то Хі(ґ+1)=1 — в противном случае хі(ґ+1)=0.
Это правило определяет на графе О дискретную динамическую систему с пространством состояний {0,1}п. Произвольно заданное начальное состояние х (0) порождает траекторию, т. е. последовательность состояний, в которой каждое состояние х (ґ+1) получается из предыдущего состояния х (ґ) по правилу перехода (Т). Поскольку число возможных состояний конечно, любая траек-
тория становится и — периодической, начиная с некоторого /. В [1] показано, что период любой траектории равен 1 или 2. Это означает, что с некоторого момента ^ граф либо переходит в стационарное состояние х =х{(+1) =…, либо принимает два состояния поочередно.
Множество тех вершин, начальное состояние которых равно 1, называется динамической монополией (динамо) в графе О [2], если соответствующая траектория выходит на стационарное состояние (1,1,., 1). Пусть
т{О) — наименьшее число вершин, образующих динамо в графе О, и и{О)=т{О)/п, где п — порядок О. В [2] для любого к построен граф Ок порядка 2к+3, для которого т{Оп)=3. Таким образом, /и{Ок)^0 при к^ж. Отметим, что граф Ок содержит вершины степени 1, 2, 3, к. Можно предположить, что в классе всех регулярных графов степени г значение и{О) ограничено снизу некоторой положительной константой (зависящей от г). Мы докажем эту гипотезу для г & lt- 4. Случай г =1 тривиален. При г=2 граф О является простым циклом и легко проверить, что /и{О)& gt-½.
Пусть М — динамо в регулярном графе О степени г & lt- 4. Тогда любой цикл С графа О должен содержать хотя бы одну вершину из множества М. Действительно, если начальное состояние всех вершин цикла равно 0, то для любой вершины хі єС по крайней мере три вершины из окрестности Б (х) находятся в состоянии 0 при ґ=0. Поскольку окрестность содержит не более пяти вершин, по правилу перехода вершина
хі остается при ґ=1 в состоянии 0. Аналогично, все вершины цикла остаются в состоянии 0 в любой момент ґ, что противоречит условию. Таким образом, хотя бы одна вершина цикла должна иметь начальное состояние 1. Тогда граф О-М, полученный удалением из О всех вершин множества М, не содержит циклов, т. е. представляет собой лес.
Пусть п — порядок графа О, т — число вершин множества М и q — число ребер графа О-М. Так как число ребер леса меньше числа его вершин [3], то q& lt-n-m. С другой стороны, граф О имеет г-п/2 ребер и удаление т вершин приводит к удалению не более, чем г-т/2
Іб
А. В. Бирюков, П.А. Бирюков
ребер, поэтому 0.5 г-п -г -т.
Таким образом, 0.5 г-п -г-т & lt- п-т и, следовательно, т& gt-п{г-2)/{2г-2) для г=3,4. В частности, для кубических графов (т. е. для г=3) имеем оценку
и{О)& gt-¼. Эта оценка является точной. Например, если Рп -граф п-угольной призмы, то можно показать, что т{Рп)=[{п+4)/2] при пф4, т. е. ц{Рп)-¼ при п-ж. Для гра-
СПИСОК ЛИТЕРАТУРЫ
фов степени 4 получается оценка и{О)-- 1/3, но в этом случае вопрос о точности оценки остается открытым.
1. Goles E., Olivos J. Periodic behaviour of generalized threshold functions. Discrete Math. 1980, v. 30, p. 187 — 189.
2. Peleg D. Size bounds for dynamic monopolies. Discrete Appl. Math. 1998, v. 86, p. 263 — 273.
3. Харари Ф. Теория графов. — М.: Мир, 1973.
? Авторы статьи:
Бирюков Альберт Васильевич
— докт. техн. наук, проф., зав. каф.
высшей математики
Бирюков Петр Альберович ¦ канд. физ. -мат. наук, доц. каф. алгебры и геометрии КемГУ

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