Низкая цена
Всего 249a за скачивание одной диссертации
Скидки
75 диссертаций за 4900a по акции. Подробнее
О проекте

Электронная библиотека диссертаций — нашли диссертацию, посмотрели оглавление или любые страницы за 3 рубля за страницу, пополнили баланс и скачали диссертацию.

Я впервые на сайте

Отзывы о нас

Исследование свойств и распознавание предфрактальных графов : диссертация ... кандидата физико-математических наук : 01.01.09

Год: 2013

Номер работы: 178

Автор:

Стоимость работы: 249 e

Без учета скидки. Вы получаете файл формата pdf

Оглавление и несколько страниц
Бесплатно

Вы получаете первые страницы диссертации в формате txt

Читать онлайн
постранично
Платно

Просмотр 1 страницы = 3 руб



Оглавление диссертации:

Актуальность диссертационного исследования Любые сложные системы [1-6], такие как информационные, энергетические, управленческие, претерпевают с течением времени определенные, вызванные внешними причинами, изменения [7-11]. Довольно часто структуры таких систем уместно представлять в виде графа [12-29]. В работах F. Harari (1973) [28], С. Berge (1962) [22], В.А. Емеличева (1990) [12] и других рассматриваются операции над графами, такие как объединение, соединение, произведение, композиция, ст

1.9). 4. Оценки диаметра и радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер. Практическая ценность и теоретическая значимость исследования В диссертационной работе получен ряд результатов, позволяющих расширить область применения теории графов. Апробация результатов исследования Основные результаты работы докладывались на конференциях: 1. Первая Всероссийская конференция молодых ученых «Математическое моделирование фр

Основными рассматриваемыми объектами данной работы являются предфрактальные графы [50]. Определению предфрактального графа предшествуют дополнительные определения и понятия. Термином затравка [50] условимся называть какой-либо фиксированный связный «-вершинный граф H = (w,Q) с непомеченными вершинами. Определим операцию замещения вершины затравкой (ЗВЗ) [50], которая является обобщением операции расщепления вершины графа [12]. Суть операции ЗВЗ состоит в следующем. В данном графе G = (V,E)

1.2. Свойства затравками предфрактальных графов, порожденных регулярными Следующая лемма устанавливает, что существует не более одного ребра, соединяющего два блока одного ранга. Лемма

1.1 Для любых двух блоков м[° =(v{l),E(1}) и м[2) = (И

2) ,£ (2) ) ранга к (k = l,L-l) v,eV(l\v2&V(2). (A/'jp.Afj2* e f i f ) существует не более одного ребра e = v,v2, такого что Доказательство. Иными словами, требуется доказать, что блоки М^ и М^ соединены не более чем одним ребром. Пу

Установим ряд свойств предфрактальных графов, в траектории которых старые ребра не смежны. Пусть GL=(vL,EL) — предфрактальный граф, в траектории которого старые ребра не смежны. Следующая теорема доказывает, что окружение выбранной вершины «почти полностью» лежит в том же блоке, что и сама вершина. Теорема

1.5 Если G,=(vL,EL) — предфрактальный граф, в траектории которого старые ребра не смежны, H = (w,Q) — затравка GL, Z = (W\Q') — блок первого ранга G, (ZeB{p), v — вершина Z (veW), U

ГЛАВА 2. МЕТРИЧЕСКИЕ СВОЙСТВА ПРЕД ФРАКТАЛЬНЫХ ГРАФОВ

Пусть H = (w,Q) — и-вершинный связный граф, v, и v2 — две его вершины (v p v 2 e»0. Расстоянием [28] d(u,v) между двумя вершинами и и v графа Я называется длина кратчайшей простой цепи, соединяющей их. Эксцентриситетом [28] s(v) вершины v (veW) определяется как maxd(u,v) по всем вершинам и в Я . Радиусом [28] г{н) называется наименьший из всех эксцентриситетов вершин. Геодезической [28] вершин и и v называется кратчайшая простая, соединяющая их, цепь. Диаметр [28] d{H) графа — это длина его

2.2. Оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре Рассмотрим п -вершинный граф Я = {w,Q), удовлетворяющий условию Оре. Лемма

2.1 [28] Наибольший из всех эксцентриситетов вершин графа равен его диаметру. Следующая лемма оценивает диаметр графа, удовлетворяющего условию Оре. Лемма

2.2 Пусть Я = {w, Q) — п -вершинный граф, удовлетворяющий условию Оре, тогда верно неравенство d{H)<2. Доказательство. При п = 2 или «=3 утверждение леммы

ГЛАВА 3. АЛГОРИТМЫ РАСПОЗНАВАНИЯ ПРЕД ФРАКТАЛЬНЫХ ГРАФОВ На вход каждого из рассматриваемых далее алгоритмов распознавания пред фрактальных графов подается простой граф G = (V,E). Задачей алгоритма является установка факта принадлежности G к классу предфрактальных графов определенного вида. Например, алгоритм распознавания а, определяет, является ли G предфрактальным графом, порожденным затравкой, представляющей собой регулярный п -вершинный граф степени ^, причем s > п/С. Дополнительн

3.1. Алгоритм распознавания предфрактальных графов с регулярной пвершинной затравкой степени не менее п/2 Постановка задачи Пусть задан граф графом G = (v,E). Необходимо проверить, является ли он пред фрактальным G,-(vL,EL), порожденным множеством затравок, п представляющих собой регулярные п -вершинные графы степени л-, причем s•> /~ . Алгоритм а у Алгоритм а, предназначен для распознавания свойства предфрактальности данного граф G = (v,E) В случае, когда G, предположительно, «-вер

Постановка задачи Пусть задан граф предфрактальным графом G-{v,E). Необходимо проверить, является ли он затравкой H = (W,Q), GL=(VL,EL), порожденным Алгоритм а2 Алгоритм а2 предназначен для распознавания свойства предфрактальности данного граф G = (v,E) В случае, когда G предположительно затравкой является H = (W,Q), удовлетворяющей условию Оре, при несмежности старых ребер предфрактальным графом, порожденным «-вершинной удовлетворяющей условию Оре, при несмежности старых ребер, если зна

Постановка задачи Пусть задан граф графом G = (V,E). Необходимо проверить, является затравкой ли он пред фрактальным G,=(vL,EL), порожденным H = (W,Q), удовлетворяющей условию Оре, при сохранении смежности старых ребер. Алгоритм а 3 Алгоритм а 3 предназначен для распознавания свойства предфрактальности данного граф G = (v,E) графом, В случае, когда G, предположительно, затравкой является H = (w,Q), пред фрактальным порожденным «-вершинной удовлетворяющей условию Оре, при сохранен

3.4. Алгоритм распознавания предфрактальных графов с и-вершинной затравкой, степень каждой вершины которой не менее 2и-1 Постановка задачи Пусть задан граф графом G = (V,E). Необходимо проверить, является ли он предфрактальным GL=(vL,EL), порожденным О 1 «-вершинной . затравкой Н = (w,Q), степень каждой вершины которой не менее Алгоритм а4 Алгоритм а4 предназначен для распознавания свойства предфрактальности графа G = (v,E) В случае, когда G, предположительно, является предфракт