Алгоритмические вопросы теории фрактальных графов

• Автор: Кочкаров, Ахмат Магомедович
• Шифр специальности: 05.13.16
• Научная степень: Докторская
• Год защиты: 1998
• Место защиты: Черкесск
• Количество страниц: 208 с.

СОДЕРЖАНИЕ
Введение.

Глава 1. ФРАКТАЛЬНЫЕ ГРАФЫ. ОПРЕДЕЛЕНИЯ, СВОЙСТВА И

МОДЕЛИ НА ПРЕДФРАКТАЛЬНЫХ ГРАФАХ

1.1. Предфраотальный и фрактальный графы

1.2. Фракталы в природе, геофизике и модели

на иредфрактальных графах.

1.3. Свойсгеа предфрактального графа

Глава 2. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГО ГРАФА С

ПОЛНОЙ ЗАТРАВКОЙ

2.1. Распознавание л,Дграфа с полной затравкой, если старые

ребра не пересекаются.
2.2 Распознавание л,Арафа с пересекающимися
старыми ребрами
2.3. Проблема распознавания п,.графа в условиях
отсутствия информации о затравке.
Глава 3. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГ О ДЕРЕВА
3.1. Распознавание предфрактального дерева, если
затравка звезда
3.2. Распознавание канонического предфрактатьного
дерева с затравкой ребро.
Глава 4. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГО ГРАФА С РЕГУЛЯРНЫМИ ЗАТРАВКАМИ
4.1. Алгоритм распознавания предфрактального графа, порожденного циклической затравкой
4.2. Распознавание предфрактального ц.Арафа с
регу лярной затравкой степени
4.3. Распознавание предфрактального я.графа с
регу лярной затравкой степени 5 .
Глава 5. ФРАКТАЛЫ. ФРАКТАЛЬНЫЕ ГРАФЫ И ИХ РАЗМЕРНОСТЬ
5.1. Фракталы и фрактальная размерность
5.2. Триадная кривая Кох.
5.3. Полный фрактальный г,.1раф и алгоритм его построения
5.4. Определение фрактальной размерности полного
фрактального г,,Аграфа при г13.
5.5. Определение фрактальной размерности полного
фрактального ,,графа при г14
5.6. Определение фрактальной размерности полного
фрактального г,,гграфа при г1т
5.7. Определение фрактальной размерности полного
фрактального г,,А1рафа мри гф1.
5.8. Определение фрактальной размерности полного фрактального г,,Лграфа при гф и произвольном коэффициенте сжашя.
Глава 6. МЕТРИЧЕСКИЕ И ТОПОЛОГИЧЕСКИЕ ХАРАКТЕРИСТИКИ ФРАКТАЛЬНОГО И ПРЕДФРАКТАЛЬНОГО ГРАФА
6.1. Диаметр и радиус фрактального и предфракгально о графа.
6.2. Реберная раскраска и хромат ический индекс
предфракгальиых и фрактальных графов.
6.3. Вершинная раскраска и хроматическое число предфракатьного и фрактального графа.
6.4. Число внутренней устойчивости предфрактального 1рафа
6.5. Число внешней устойчивости нредфракгального графа.
6.6. Остовные деревья фракгального и предфрактального 1рафа
6.7. О гамильтоновости фрактального и предфрактального графа.
ЛИТЕРАТУРА


Плцен-Чехословакия, ), на Международной конференции "Проектирование автоматизированных систем контроля и управления сложными объектами" (Харьков, ), на IX Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, ), на Международной конференции "Применение компьютерных технологий в гражданском строительстве" (Ротердам, ), на Международной конференции "Нелокальные краевые задачи и родствегшые проблемы математической биологии, информатики и физики" (Нальчик, ), на Всероссийском симпозиуме "Математическое моделирование экологоэкономических систем" (Кисловодск, ). И научно-практической конференции Карачаево-Черкесского технологического института (Черкесск, ), на II Всероссийском симпозиуме "Математическое моделирование эколого-экономических систем" (Кисловодск, ), на Международном коллоквиуме математиков 1КМ' (Веймар, ), на Международном конгрессе математиков 1СМ’ (Берлин, ), а также на заседаниях научных семинаров САО РАН, ТГРУ, СГТУ и КЧТИ. По теме диссертации опубликовано научных работ, в том числе одна монография. Объем и структура работы. Диссертация состоит из введения, шести глав. Она содержит 8 страниц и рисунков. Список литературы включает 6 наименований. Первая глава диссертации состо»тт из трех параграфов, в которых дано индуктивное определение прелфрактального и фрактального графа. Определены свойства прелфрактального графа. На фрактальных и предфракталъных графах предложены некоторые математические модели задач из физики, техники, социологии, экономики. В 1. Для формулирования определений будем использовать общепринятое обозначение О - (У,Е) для всякого конечного и бесконечного графа. Термином "затравка" условимся называть какой-либо связный /1-вершинный іраф II = (И’,0 с непомеченными, т. IV. В качестве обобщения известной операции "расщепление вершины графа" определим операцию "замещение вершины затравкой" (ЗВЗ). Суть операции ЗВЗ состоит в следующем. В данном графе С = (Г,? И' выделяется ее окружение, т. ЯС/ всех ребер, инцидентных вершине у0 : Я0 ={е = (у0,и):и еі/0}, т0 =|? У, (1. Ж). После чего у каждого ребра е = (у0,и)е Я0 из выделенного окружения конец у0 заменяется на определяемую отображением (1. Я. "Старое" ребро е = (у0,н) в "новом" измененном виде (у,н),у = ^(м) сохраняет первоначальное обозначение (нумерацию). Операция ЗВЗ считается оконченной, как только для каждого ребра (у0. II. О. Аналогично присваиваются обозначения (номера) ребрам затравки, которая заместила намеченную вершину у0. Определим поэтапный процесс выполнения операции ЗВЗ. На этапе 5 =1 в данной затравке Н = (1У,0) нумеруем вершины и ребра, полученный граф обозначим через С) =(Г1,? Пусть выполнены этапы 5 = 1,2,. С/ - {У1,Е1)). На этапе 5=/+1 для каждой вершины V е У, осуществляется операция ЗВЗ, т. Операция ЗВЗ применяется к каждой вершине V е и, как отметили выше, представляет собой обобщение известной операции "расщепление вершины графа". Суть этого обобщения, как видно из определения предфрактального графа, состоит в том, что каждая расщепляемая вершина V е У/_1 замещается не ребром, а затравкой // = (И/,0. В процессе выполнения этой операции все ребра ? С/,С/+1,. С^, где всегда ? При этом все старые ребра, инцидентные заметаемой вершине V е У{_х, становятся (случайным или регулярным образом) инцидентными некоторым вершинам затравки, которая заместила вершину V. Ребра каждой из таких появившихся затравок называются новыми ребрами, т. Е,); ребра этого множества являются старыми ребрами в текущих графах = 1,2,. Граф Сц+ц =(Г(/+ц,? ЗВЗ к каждой из вершин из У,. I е {1,2,. В качестве С1 всегда принимается данная затравка Н. Обобщением описанного выше процесса порождения предфракгального графа <7 является такой случай, когда вместо единственной затравки Н задается множество затравок ж = {Н}={НХ,Н2,. Пт, Т> 2. С/ каждая вершина замещается некоторой затравкой И, € . Отличительной особенностью описанных выше процессов порождения предфрактального графа является то, что на каждом этапе / = 2,3,. V е К,. Предфрактальные графы, получаемые в результате такого процесса, называем каноническими. В общем случае неканонический предфрактальный граф порождается множеством затравок . К мощности . Сг в траектории (1. V е Уг^, а лишь подмножество вершин У'_х с Уг_1, которое определяется либо случайно, либо согласно конкретным правилам, отражающим содержательную специфику моделируемой задачи. В качестве затравки может использоваться не только обыкновенный граф, но и мультиграф. Предфрактальный граф С = <7, =(^//1'/. КПГ) называем термином "(//,?