На правах рукописи

Резников Андрей Владимирович

ИССЛЕДОВАНИЕ СВОЙСТВ И РАСПОЗНАВАНИЕ

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

01.01.09 – Дискретная математика и математическая кибернетика

Автореферат

диссертации на соискание ученой степени

кандидата физико-математических наук

Ярославль – 2013

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Северо-Кавказская государственная гуманитарно-технологическая академия»

(Карачаево-Черкесская Республика, г. Черкесск)

Научный руководитель: доктор физико-математических наук, профессор Кочкаров Ахмат Магомедович

Официальные оппоненты: Бондаренко Владимир Александрович, доктор физико-математических наук, профессор, заведующий кафедрой дискретного анализа ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова»

Пастор Алексей Владимирович, кандидат физико-математических наук, научный сотрудник лаборатории математической логики Санкт-Петербургского отделения Математического института им. В.А. Стеклова Российской академии наук

Ведущая организация: Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет»

Защита диссертации состоится 20 декабря 2013 г. в 12:30 на заседании диссертационного совета Д 212.002.03 при ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова» по адресу: 150008, г. Ярославль, ул. Союзная, 144, аудитория 426.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова».

Автореферат разослан «_» ноября 2013 г.

Ученый секретарь диссертационного совета Яблокова С.И.

Общая характеристика работы

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

Актуальность темы. Любые сложные системы, такие как информационные, энергетические, управленческие, претерпевают с течением времени определенные, вызванные внешними причинами, изменения. Довольно часто структуры таких систем уместно представлять в виде графа. В работах F. Harari (1973), C. Berge (1962), В.А. Емеличева (1990) и других рассматриваются операции над графами, такие как объединение, соединение, произведение, композиция, стягивание дуги и пр. С помощью этих операций можно описать изменения, происходящие в структурах сложных систем.

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

Общеизвестным сценарием структурной динамики является рост структуры — регулярное появление элементов и связей в структуре системы. В некоторых случаях для описания роста структуры используется перечень правил, причем такие правила могут допускать элемент случайности.

В настоящей работе рассматривается правило, задающее структурную динамику сложных систем. Результатом применения этого правила являются так называемые самоподобные (self-similar graphs) или фрактальные графы.

Фрактальный граф — это сложная абстрактная структура, обладающая свойствами фракталов и «простых» графов. В разных научных школах применяются различные правила построения структурной динамики, что в результате приводит к различным, по строению, самоподобным графам. По данной тематике написано множество статей в российских и зарубежных научных журналах. В статье F.G. Arenas, M.A. Sanchez-Granero (2000) исследуются графы, построенные на множестве точек отрезка 0,1. В работах E. Teufl, S. Wagner (2000); B. Krn (2002); B. Krn, E. Teufl (2004);

L. Malozemov, A. Teplyaev (2003); D. D’Angeli, A. Donno (2010) изучаются свойства графов, каждый из которых состоит из множества изоморфных подграфов, причем последние могут иметь ровно одну общую вершину.

Свойства графов, полученных «дискретизацией» фрактальных множеств, описали в своих трудах V. Nekrashevych (2007); D. Guido, T. Isola, M. Lapidus (2009). Самоподобные графы древовидной структуры исследованы в статье J. Neunhuserer (2007).

Другие способы построения самоподобных графов, а также вопросы практического применения фрактальных множеств рассмотрены в работах F. Comellas, A. Miralles (2009); C. Lee, P-S. Loh, B. Sudakov (2012);

В.А. Бондаренко, В.Л. Дольникова (1994).

Понятие фрактал, введенное Бенуа Мандельбротом, объединило объекты, обладающие особым свойством — свойством самоподобия (self-similar).

Работы, связанные с исследованием фрактальных объектов, фрактальных множеств, долгое время считались интересными, но не имеющими серьезных практических приложений. Мнения в мировой научной среде изменились после издания книги «Фракталы в физике». В настоящее время о перспективности и значимости исследований можно судить по регулярно проводимым конференциям и периодическим изданиям, полностью посвященным соответствующей тематике, и большому количеству книг, учебников и монографий. Это позволяет говорить о сформировавшемся круге прикладных физических задач на основе фрактальных множеств. Среди них выделяются задачи и модели, в которых фрактальные множества представлены как самоподобные, масштабно-инвариантные графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например задачи о броуновском движении, диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких как коммуникационные сети.

Изучение фрактальных графов и их приложений ведется под руководством профессора А.М. Кочкарова. Наиболее активно прорабатываются задачи многокритериальной оптимизации в системах с фрактальной структурой и вопросы выявления свойств и характеристик графов. Метрические свойства исследуются в работах А.М. Кочкарова.

В работе Д.А. Павлова построены оценки метрическим характеристикам предфрактального графа с затравкой простая цепь, в монографии Кочкарова А.А. получены оценки диаметра и радиуса произвольных предфрактальных графов и некоторых классов графов при сохранении смежности старых ребер.

Другим направлением исследования является распознавание фрактальных (предфрактальных) графов. Предфрактальные графы состоят из конечного количества элементов (вершин и ребер), поэтому любая задача распознавания таких графов допускает переборное решение. Для практических задач важен не факт существования алгоритма распознавания, а важно наличие эффективного алгоритма решения поставленной задачи. Наиболее «быстрыми»

являются, как известно, полиномиальные алгоритмы. Разработка таких алгоритмов является одной из целей данной работы.

В частности, А.М. Кочкаровым (1998) разработаны полиномиальные алгоритмы распознавания предфрактальных графов с полными затравками, некоторых предфрактальных деревьев, некоторых предфрактальных графов с регулярными затравками. Вопросы распознавания предфрактальных графов также исследуются в работах Е.В. Бобылевой (2005); Е.М. Киселевой, Е.В. Бобылевой (2005); И.Х. Утакаевой (2007); Л.Х. Хапаевой, А.М. Кочкарова (2011).

Цели и задачи исследования.

1. Исследование структуры предфрактальных графов.

2. Выявление свойств и характеристик предфрактальных графов с различными затравками.

3. Разработка алгоритмов распознавания предфрактальных графов.

Методы исследования. В диссертационной работе используются методы исследования операций, теории графов, теории предфрактальных и фрактальных графов, теории алгоритмов и сложности алгоритмов, комбинаторики.

Научная новизна.

1. Предложен алгоритм распознавания предфрактальных графов, порожденных регулярными затравками.

2. Предложен алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при несмежности старых ребер.

3. Предложен алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.

4. Предложен алгоритм распознавания предфрактальных графов, порожденных n-вершинными затравками, степень каждой вершины 5. Получены оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.

6. Получены оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.

Практическая ценность и теоретическая значимость работы. В диссертационной работе получен ряд результатов, позволяющих расширить область применения теории графов.

Апробация работы. Основные результаты работы докладывались на конференциях:

1. Первая Всероссийская конференция молодых ученых «Математическое моделирование фрактальных процессов, родственные проблемы анализа и информатики», Россия, 2. Всероссийская научно-методическая конференция «Актуальные проблемы углубленного математического образования», 3. Международная научно-практическая конференция «Перспективные инновации в науке, образовании, производстве и транспорте 2010», 4. VI Всероссийская научно-практическая конференция «Математические методы и информационно-технические средства», 5. VII Международная научная конференция молодых ученых «Наука.

Образование. Молодежь», Майкоп, 2011.

Публикации. По результатам выполненной работы имеется публикаций, в том числе, 3 статьи в журналах из списка ВАК, тезисы докладов в материалах двух Всероссийских конференций, тезисы докладов в материалах двух международных конференций. На разработанные алгоритмы получено свидетельства о государственной регистрации программ для ЭВМ.

Структура диссертации. Поставленные задачи определили структуру работы и содержание отдельных разделов. Диссертация состоит из введения, трех разделов, заключения, списка использованных источников и приложения.

Она изложена на 117 страницах машинописного текста (без приложений), содержит 42 рисунка, одно приложение, список использованных источников из 189 наименований.

Основные положения, выносимые на защиту.

1. Эффективные полиномиальные алгоритмы распознавания предфрактальных графов.

2. Теорема об окружении вершины предфрактального графа, в траектории которого старые ребра не смежны (теорема 1.6).

3. Теорема об окружении старой вершины предфрактального графа, в траектории которого смежность старых ребер сохраняется 4. Оценки диаметра и радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.

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

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

Основным элементом определения фрактального графа является затравка. Термином затравка условимся называть какой-либо фиксированный связный граф H W, Q.

Определим операцию замещения вершины затравкой (ЗВЗ): в данном графе G V, E у намеченной для замещения вершины v0 выделяется ее окружение, т.е. множество U 0 всех вершин, смежных с вершиной v0. Далее, из графа G удаляется вершина v0 и все инцидентные ей ребра. Вместо нее в граф G добавляется затравка H. Затем каждая вершина множества U 0 соединяется ребром с одной из вершин затравки H. Вершины соединяются случайным образом или по определенному правилу при необходимости.

Предфрактальный граф будем обозначать через G L VL, E L, где VL, E L – множества вершин и ребер графа соответственно. Определим его рекуррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе l 1, 2,..., L графе Gl Vl, El каждую его вершину затравкой H. На этапе l предфрактальному графу соответствует затравка G1 H. В таком случае говорят, что предфрактальный граф G L порожден затравкой H. В процессе порождения определяется последовательность графов G1, G2,...,G L. Эта последовательность называется траекторией предфрактального графа G L.

Ребра, появившиеся на l -ом этапе порождения l 1,2,..., L, будем называть ребрами ранга l. Ребра ранга l называются новыми ребрами предфрактального графа G L, остальные ребра – старыми.

Если из графа G L удалить все ребра рангов 1,..., L 1, то исходный граф распадается на множество связных компонент BL1), каждая из которых изоморфна затравке H. Множество компонент BL1) будем называть блоками первого ранга. Аналогично, при удалении из G L ребер рангов 1,..., L 2 получим множество BL2) блоков второго ранга. Подобным образом определяются множества блоков остальных рангов BL3,..., BLL 1. Всякий блок ранга k ( k 1, L 1 ) является предфрактальным графом ранга k.

На рисунке 1 изображена траектория предфрактального графа G3 V3, E3, порожденного затравкой H W, Q – треугольником. Линиями удвоенной толщины обозначены старые ребра предфрактальных графов G1, G2, G3, тонкими линиями – новые ребра.

Рисунок 1. Траектория предфрактального графа G3 V3, E3.

Показателем блока первого ранга Z ( Z BL1 ) предфрактального графа GL VL, EL назовем степень такой вершины v графа GL 1 VL1, E L1 ( v VL 1 ), из которой был получен блок Z с помощью операции ЗВЗ. Обозначают: indexZ.

затравками, описаны в следующих утверждениях:

Теорема о существовании блока первого ранга, показатель которого не превосходит n 1 :

Теорема 1.1 В предфрактальном графе GL VL, EL найдется блок первого ранга Z W ', Q' ( Z BL1 ), показатель которого не превосходит n 1, Теорема о существовании блока первого ранга, показатель которого не превосходит n 1, в предфрактальном графе, из которого удалены несколько таких блоков:

Теорема 1.2 После удаления из предфрактального графа GL VL, EL множества блоков первого ранга M M L1,..., M LT BL1 со всеми инцидентными их вершинам ребрами во вновь образовавшемся графе G ' V ', E ' найдется блок первого ранга Z W ', Q ', такой что indexZ n 1.

предфрактального графа выделяют:

1) предфрактальные графы, в траектории которых старые ребра не 2) предфрактальные графы, в траектории которых старые ребра сохраняют смежность;

3) предфрактальные графы общего вида.

Вершину v предфрактального графа GL VL, EL назовем старой вершиной, если она инцидентна хотя бы одному старому ребру. Остальные вершины будем называть новыми вершинами.

Будем говорить, что n -вершинный граф H W, Q удовлетворяет условию Оре, если для любой пары его вершин v1 и v2 ( v1, v2 W ) выполняется условие Получен ряд свойств затравок предфрактальных графов.

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

Теорема 1.3 Если n -вершинный граф H W, Q ( n 3 ) удовлетворяет условию Оре и если v1 и v2 ( v1, v2 W ) — две несмежные вершины ( e v1v2 Q ) графа H, то в H найдутся вершины w1 и w2 ( w1, w2 W ), такие что v1 w1, v1 w2, v2 w1, v2 w2 Q ). Другими словами, найдутся, по меньшей мере, две вершины, каждая из которых смежна одновременно с вершинами v1 и v2.

Следующая лемма доказывает отсутствие висячих вершин в графе, удовлетворяющем условию Оре.

удовлетворяющий условию Оре, n 2, то все вершины H имеют степень не Следующая лемма доказывает, что в графе, удовлетворяющем условию Оре, «почти все» вершины имеют степень.

удовлетворяющий условию Оре, v — вершина минимальной степени графа H ( v V ), то все, отличные от v, вершины графа H, имеют степень не меньше, Следующая лемма дает достаточное условие связности графа.

вершины которого не менее, то H является связным графом.

Следующая теорема дает достаточное условие связности окружения произвольно выбранной вершины.

Теорема 1.4 Если H V, E — n -вершинный граф, степень каждой вершины которого не менее, v — произвольная вершина графа H ( v V ), U — окружение вершины v ( U V ), то подграф, порожденный множеством U, является связным.

Получен ряд утверждений о свойствах предфрактальных графов, в траектории которых старые ребра не смежны.

Следующая теорема доказывает, что окружение выбранной вершины «почти полностью» лежит в том же блоке, что и сама вершина.

Теорема 1.5 Если GL VL, EL — предфрактальный граф, в траектории которого старые ребра не смежны, H W, Q — затравка G L, Z W ', Q ' — блок первого ранга G L ( Z BL1 ), v — вершина Z ( v W ' ), U — окружение вершины v, то либо все вершины множества U принадлежат блоку Z, либо все, за исключением одной, вершины множества U принадлежат блоку Z.

Следующая теорема доказывает, что вершины, смежные с двумя вершинами окружения выбранной вершины, лежат в том же блоке, что и сама вершина.

Теорема 1.6 Если GL VL, EL — предфрактальный граф, в траектории которого старые ребра не смежны, H W, Q — затравка G L, Z W ', Q ' — блок первого ранга G L ( Z BL1 ), v — вершина Z ( v W ' ), U — окружение вершины v, U 2 — множество вершин GL VL, EL ( U 2 VL ), каждая из которых смежна хотя бы с двумя вершинами множества U, то все вершины множества U принадлежат блоку Z W ', Q '.

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

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

предфрактального графа GL VL, EL, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, N — множество вершин блока Z, степень каждой из которых не менее n ( N W ' ), то Пусть GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема устанавливает факты для окружения новой вершины.

Теорема 1.8 Если GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, v — новая вершина G L, Z W ', Q ' — блок первого ранга ( Z BL1 ), содержащий вершину v ( v W ' ), U — окружение вершины v ( U VL ), N — подмножество вершин множества U, степень каждой из которых не менее n ( N U ), то верны следующие два утверждения:

а) U W ', т.е. все вершины, смежные с v, принадлежат блоку Z ;

Пусть GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема устанавливает факты для окружения старой вершины.

Теорема 1.9 Если GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, H удовлетворяет условию Оре, v — старая вершина G L, степень вершины v меньше n ( v n ), Z W ', Q ' — блок первого ранга ( Z BL1 ), содержащий вершину v ( v W ' ), U — окружение вершины v ( U VL ), N — подмножество вершин множества U, степень каждой из которых не менее n ( N U ), то верны следующие три утверждения:

Пусть GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема дает оценку степени старой вершины.

Теорема 1.10 Если G L VL, E L — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, степень каждой вершины H не меньше,v— старая вершина G L, то степень вершины v не меньше n, т.е. v n.

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

Следующая лемма оценивает диаметр графа, удовлетворяющего условию Оре.

Лемма 2.2 Если H W, Q — n -вершинный граф, удовлетворяющий условию Оре, то d H 2.

Следующая лемма оценивает радиус графа, удовлетворяющего условию Оре.

Лемма 2.3 Если H W, Q — n -вершинный граф, удовлетворяющий условию Оре, то r H 2.

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

Теорема 2.1 Пусть GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, H удовлетворяет условию Оре, тогда верно Теорема 2.2 Пусть GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, H удовлетворяет условию Оре, тогда верно Следующие теоремы дают оценки радиуса предфрактального графа, в траектории которого смежность старых ребер сохраняется.

Теорема 2.3 Пусть GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, H удовлетворяет условию Оре, тогда верно Теорема 2.4 Пусть GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, H удовлетворяет условию Оре, тогда верно Теорема 2.5 Пусть GL VL, EL — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, H W, Q — n -вершинная затравка, породившая G L, H удовлетворяет условию Оре, степень каждой вершины H меньше n 1, тогда верно неравенство r G L 2 L.

Третий раздел диссертации содержит описание и обоснование алгоритмов 1, …, 4 распознавания предфрактальных графов.

Такие алгоритмы условно можно разделить на следующие группы:

алгоритмы, распознающие предфрактальные графы общего вида, т.е.

графы, в траектории которых взаимное расположение старых ребер может быть произвольным – алгоритмы 1, 4 ;

алгоритмы, распознающие предфрактальные графы, в траектории которых старые ребра не смежны – алгоритмы 2, 2 ' ;

алгоритмы, распознающие предфрактальные графы, в траектории которых смежность старых ребер сохраняется – алгоритмы 3, 3 '.

регулярной n-вершинной затравкой степени не менее.

Теорема 3.1 Всякий предфрактальный граф GL VL, EL, порожденный затравкой, являющейся регулярным n -вершинным графом степени s, с условием s, распознается алгоритмом 1, причем если n Oln E L, то 1 ~ O E L L, где 1 — трудоемкость алгоритма 1.

Алгоритмы 2, 2 ' распознают предфрактальные графы с затравкой, удовлетворяющей условию Оре, при несмежности старых ребер.

Теорема 3.2 Всякий предфрактальный граф GL VL, EL, порожденный затравкой, удовлетворяющей условию Оре, при несмежности старых ребер распознается алгоритмом 2, причем если n Oln E L, то 2 ~ O E L L, где 2 — трудоемкость алгоритма 2, n — количество вершин затравки.

Теорема 3.2.1 Всякий предфрактальный граф GL VL, EL, порожденный несмежности старых ребер, распознается алгоритмом 2 ', причем если Алгоритмы 3, 3 ' распознают предфрактальные графы, порожденные затравкой, удовлетворяющей условию Оре, при сохранении смежности старых ребер.

Теорема 3.3 Всякий предфрактальный граф GL VL, EL, порожденный затравкой, удовлетворяющей условию Оре, при сохранении смежности старых ребер распознается алгоритмом 3, причем если n Oln E L, то 3 ~ O E L L, где 3 — трудоемкость алгоритма 3, n — количество вершин затравки.

Теорема 3.3.1 Всякий предфрактальный граф GL VL, EL, порожденный сохранении смежности старых ребер, распознается алгоритмом 3 ', причем Теорема 3.4 Всякий предфрактальный граф GL VL, EL, порожденный n вершинной затравкой H W, Q, степень каждой вершины которой не менее где 4 — трудоемкость алгоритма 4.

Основные результаты, полученные в диссертации:

1. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных регулярными затравками; получена оценка его 2. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при несмежности старых ребер; получена оценка его сложности.

3. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер; получена оценка его 4. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных n-вершинными затравками, степень каждой 5. Получены следующие оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при 6. Получены следующие оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при где r H, d H — соответственно радиус и диаметр затравки.

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

8. Сформулирована и доказана теорема об окружении старой вершины предфрактального графа, в траектории которого старые ребра не Основные положения диссертации отражены в следующих публикациях:

Статьи в ведущих рецензируемых научных журналах и изданиях, входящих в перечень ВАК 1. Резников А.В. Распознавание предфрактальных графов с затравкой, удовлетворяющей условию Оре [текст] / А.В. Резников // Вестник Адыгейского государственного университета. – Майкоп, 2010. – 2. Резников А.В. Алгоритм распознавания предфрактальных графов с регулярной N-вершинной затравкой степени не менее N/2 [текст] / А.В. Резников, А.А. Кочкаров // Экологический вестник научных центров черноморского экономического сообщества. – Краснодар, 2010. – Выпуск 2. – С. 63-69.

3. Резников А.В. Распознавание предфрактальных графов с затравкой, удовлетворяющей условию Оре, при условии что смежность «старых»

ребер в траектории предфрактального графа сохраняется [текст] / А.В. Резников // Вестник Адыгейского государственного университета. – Майкоп, 2011. – Выпуск 1. – С. 25-33.

Свидетельства о государственной регистрации программ для ЭВМ 4. Резников А.В. Программный комплекс для распознавания предфрактальных графов с регулярными затравками («Recognize 1.0») / А.В. Резников, А.А. Кочкаров // Свидетельство о государственной регистрации программы для ЭВМ, № 2010613649, 03.06.2010.

5. Резников А.В. Программный комплекс для распознавания предфрактальных графов с затравками, о структуре которых информация отсутствует («Recognize 2.0») / А.В. Резников, А.А. Кочкаров // Свидетельство о государственной регистрации программы для ЭВМ, № 2011611836, 28.02.2011.

Материалы и тезисы конференций, статьи в сборниках 6. Резников А.В. Об изучении алгоритмов распознавания образов [текст] / А.В. Резников // Актуальные проблемы углубленного математического образования: Материалы XXVII Пленума Учебнометодического совета по математике и механике и Всероссийской научно-методической конференции. – Майкоп, 2010. – С. 177-180.

7. Резников А.В. Распознавание предфрактальных графов с затравкой удовлетворяющей условию Оре [текст] / А.В. Резников // Сборник научных трудов по материалам международной научно-практической конференции «Перспективные инновации в науке, образовании, производстве и транспорте `2010». – Одесса, 2010. – С. 52-55.

8. Резников А.В. Распознавание предфрактальных графов, при условии сохранения смежности «старых» ребер [текст] / А.В. Резников // Математическое моделирование фрактальных процессов, родственные проблемы анализа и информатики: Материалы Первой Всероссийской конференции молодых ученых. – Терскол, 2010. – С. 140-143.

9. Резников А.В. Распознание предфрактальных графов [текст] / А.В. Резников // Математические методы и информационнотехнические средства: труды VI Всерос. Науч.-практ. конф. – Краснодар, 2010. – С. 145-147.

10. Резников А.В. Алгоритм распознавания предфрактальных графов, при условии сохранения смежности «старых» ребер [текст] / А.В. Резников // «Наука. Образование. Молодежь»: Материалы VIII Международной научной конференции молодых ученых. – Майкоп, 2011. – С. 363-366.

Подписано в печать 6.11.2013 г. Формат 6084/16.