Распознавание предфрактального графа, порожденного полной двудольной затравкой

Размещено на http://www.allbest.ru/

Распознавание предфрактального графа, порожденного полной двудольной затравкой

Множество задач, возникающих в физике, технике, химии, социологии, экономике и других областях, адекватно моделируются средствами теории графов.

При моделировании сложных объектов с изменяющейся во времени структурой возникают задачи распознавания предфрактального графа [1]. Такого рода задачи могут возникать при распределении ресурсов целевых программ [2, 3, 4], при реализации крупных научно-исследовательских проектов, при организации экономических союзов, в военном деле при организации военных блоков.

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

Для формулировки определений будем использовать общепринятое обозначение для всякого конечного и бесконечного графа.

Термином ''затравка'' [1] условимся называть какой-либо связный n-вершинный граф c непомеченными, т.е. ненумерованными вершинами . Для определения фрактального (предфрактального) графа [1] нам потребуется операция замены вершины затравкой (ЗВЗ). Суть операции ЗВЗ заключается в следующем.

В данном графе у намеченной для замещения вершины [5] выделяется ее окружение, т.е. множество всех вершин, смежных с вершиной , и множество всех ребер, инцидентных вершине - число вершин во множестве . Далее определяется некоторое отображение вершин во множество вершин затравки:

, (1)

то есть каждой вершине ставится в соответствие определяемая с помощью вершина затравки (). После чего у каждого ребра из выделенного окружения конец заменяется на определяемую отображением (1) вершину затравки H. "Старое" ребро в "новом" измененном виде сохраняет первоначальное обозначение (нумерацию). Операция ЗВЗ считается оконченной, как только для каждого ребра замещаемая вершина будет заменена на определяемую отображением (1) вершину затравки H. Ненумерованным вершинам затравки присваиваются номера с учетом уже имеющихся номеров других вершин данного графа . Аналогично присваиваются обозначения (номера) ребрам затравки, которая заместила намеченную вершину .

Определим поэтапный процесс выполнения операции ЗВЗ. На этапе в данной затравке нумеруем вершины и ребра, полученный граф обозначим через .

Пусть выполнены этапы и по завершении этапа l получен граф , который называем предфрактальным (если , то речь будем вести о фрактальном графе ). На этапе для каждой вершины осуществляется операция ЗВЗ, т.е. замещение вершины затравкой . Операция ЗВЗ применяется к каждой вершине и, как отметили выше, представляет собой обобщение известной операции "расщепление вершины графа". Суть этого обобщения, как видно из определения предфрактального графа, состоит в том, что каждая расщепляемая вершина замещается не ребром, а затравкой . В процессе выполнения этой операции все ребра сохраняются и называются старыми ребрами по отношению ко всем текущим графам , где всегда . При этом все старые ребра, инцидентные замещаемой вершине , становятся (случайным или регулярным образом) инцидентными некоторым вершинам затравки, которая заместила вершину . Ребра каждой из таких появившихся затравок называются новыми ребрами, т.е. множество новых ребер есть множество (); ребра этого множества являются старыми ребрами в текущих графах . Граф получается в результате применения операции ЗВЗ к каждой из вершин из . При этом условимся говорить, что граф порожден затравкой H,. В качестве всегда принимается данная затравка .

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

, (2)

где ? номера шагов (этапов) процесса порождения графа .

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

Для мощности множества вершин существует непустое множество пар , таких, что или

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

предфрактальный граф сетевой модель

, где (3)

Замечание1. Для случая, когда формула (3) примет вид

Если количество вершин и ребер графа удовлетворяет необходимым условиям 1), 2), то ставятся два вопроса из области теории распознавания:

а) является ли данный граф G предфрактальным с полной двудольной затравкой;

б) можно ли построить достаточно эффективный алгоритм, который гарантированно дает положительный или отрицательный ответ на вопрос а).

Рассмотрим случай распознавания предфрактального (n,L)-графа с полной двудольной затравкой, если старые ребра не пересекаются.

Смысл распознавания предфрактального (n,L)-графа, по существу, сводится к построению траектории (2): .

Алгоритм .

Вычислительная схема алгоритма состоит из этапов.

Подэтап этапа осуществляет выделение и окрашивание множества стартовых вершин (СВ) , где индексы нумерации СВ пробегают значения в случае, если G представляет собой (n,L)-граф. Всякая СВ вершина определяется относительно множества вершин блоков , выделенных на предыдущих этапах 1,2,...,k-1. Множество СВ составляют вершины , каждая из которых к началу этапа k удовлетворяет двум условиям: a) вершина не является окрашенной; b) она смежна с уже окрашенной вершиной некоторого блока , т.е. существует неокрашенное ребро , соединяющее окрашенную вершину и неокрашенную вершину . В этом случае ребро называем термином "СР этапа k".

Специфика этапа k=1 обусловлена тем, что к его началу в данном графе G отсутствуют окрашенные ребра и окрашенные вершины. Суть первого подэтапа этапа 1 состоит в том, что в качестве его множества СВ выбирается подмножество вершин степени degv= . Результатом первого подэтапа является выделенное множество СВ ; каждая СВ ; , окрашивается; .

Примечание 1. Согласно определению (n,L)-графа G, каждая СВ смежна в G с долями подграфа, изоморфного затравке Н.

Работу этапа k=1 продолжает его второй подэтап р=2. Его результатом являются выделенные для каждой стартовой вершины с помощью процедуры блоки первого ранга , ребер каждого из блоков окрашивается.

Замечание 2. В силу того, что старые ребра в траектории не пересекаются, все вершины могут иметь степень или .

ПРОЦЕДУРА .

Просматривая вершины графа определяем любую вершину степени . Согласно замечанию 2 такое возможно.

В силу того, что затравка - двудольный граф, предполагаем, что выделенная СВ вершина то, (так как затравка полная) мы сразу можем выделить вторую долю , выделив все смежные с вершины. Определим принцип выделения другой доли Из выделенной доли берем произвольную вершину Согласно замечанию 2 возможны два случая.

1) Если степень вершины равна , то мы выделяем сразу другую долю .

2) Если степень вершины равна , выбираем смежную ей вершину , если выбранная вершина будет смежна с любой вершиной из доли , то она принадлежит доле .

Если на каком-то шаге, мы попадем в вершину, не принадлежащую доле , тогда все остальные смежные ей вершины определяют долю .

Таким образом, мы выделяем затравку-блок .

Процесс выделения блока состоит в проверке изоморфен ли затравке Н подграф, порожденный СВ и теми вершинами, которые смежны с .

На этом процедура заканчивает свою работу.

Из выделенного блока придем по старому ребру к другой свободной вершине и, применяя процедуру , опять выделяем блок (вершина уже будет степени ).

Замечание 2. В силу вычислений в пункте 2) количество вершин графа на шаге будет равно , а мощность множества старых ребер графа равна , так как

при , то , то есть число вершин графа на шаге будет больше удвоенного числа старых ребер графа

Следовательно, количества необходимых вершин, достаточно, чтобы траектории не пересекались.

Положительным результатом этапа k=1 является выделение окрашенных блоков. Причем ребра каждого из этих блоков образуют полный п-вершинный двудольный граф, изоморфный затравке предфрактального графа G . Если указанный изоморфизм отсутствует, то этап k=1 заканчивается с отрицательным результатом в том смысле, что рассматриваемый граф G не является предфрактальным (n,L)-графом. Положительный (отрицательный) результат означает продолжение (остановку) работы алгоритма. Аналогичное утверждение сохраняет свою силу и для дальнейших этапов и соответствующих подэтапов алгоритма.

После окончания первого этапа по «обратному» принципу ЗВЗ замещаем затравку вершиной. Замещаем целиком затравку выделенной одной вершиной, так чтобы все ребра , инцидентные этой затравке, были инцидентны этой вершине. Обозначим блок , изоморфный затравке вершиной .

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

(n-1,L-1)- графом. Положительный (отрицательный) результат означает продолжение (остановку) алгоритма.

Примечание 2. В самом общем виде схема работы каждого этапа

состоит в следующем.

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

Получаем предфрактальный граф с полной двудольной затравкой Н и непересекающимися «старыми» ребрами.

Алгоритм закончит свою работу на этапе , когда получим предфрактальный граф , то есть распознавание предфрактального графа свелось к построению траектории .

Теорема 1. Алгоритм определяет траекторию (n ,L)- предфрактального графа если затравка - двудольный полный граф и старые ребра не пересекаются, где , причем трудоемкость алгоритма равна .

Доказательство следует из построения алгоритма .

Рассмотрим случай распознавания предфрактального (n,L)-графа с полной двудольной затравкой, если старые ребра пересекаются.

Определим сначала два термина: "новая затравка" (НЗ) и "старая затравка" (СЗ). Подграф [1] данного графа G=(V,E), , называется НЗ (СЗ), если он изоморфен затравке и состоит только из "новых" (только из "старых") ребер, т.е. ()). Множество всех НЗ и СЗ в графе G обозначим через .

Подмножество называется покрытием графа G (затравками), если каждая вершина графа G принадлежит хотя бы одной затравке .

Доказана

Лемма 1. Для всякого (n,q,L)-графа покрытие, состоящее только из НЗ (т.е. покрытие ), является единственным, причем количество ребер в этом покрытии, состоящем из попарно непересекающихся затравок, равно

. (4)

Приведем алгоритм распознавания предфрактального (n,L)-графа с полной двудольной затравкой, если старые ребра пересекаются.

Алгоритм .

Алгоритм состоит из трех этапов: , и . Цель этапа - выделение множества , , всех затравок (НЗ и СЗ) в данном графе , который обладает сформулированными в начале признаками предфрактального графа. При этом значение параметра n (размерность затравки) считается априори известным. Тогда ранг , .

Работа этапа состоит в том, что в данном графе G=(V,E) последовательно к каждой вершине применяются вышеописанные три подэтапа , и . При этом если у очередной вершины обнаружится, что все инцидентные ей ребра уже окрашены в цвет 1, то эту вершину окрашиваем сразу же, не воспроизводя работы вышеуказанных подэтапов. После чего переходим к рассмотрению очередной неокрашенной вершины из V.

Окраска всех вершин в G означает, что путем окрашивания ребер в графе G выделено множество всех его затравок.

Работа этапа завершается проверкой, выполняется ли равенство

, (5)

которое, согласно лемме 1, означает, что состоит только из новых затравок, совокупность ребер которых составит множество, если G окажется (n,L)-графом. В этом случае следует переход к этапу .

На этапе каждая НЗ стягивается в одну вершину , в которую стянулись, соответственно затравки , а множество состоит из ребер . Граф будем называть условно-предфрактальным (n,L-1)-графом.

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

Этап применяется к результату работы этапа в том случае, когда не выполняется равенство (5), что означает наличие СЗ в множестве всех затравок. В результате работы этапа ребра каждой из СЗ окрашиваются в цвет 2, а ребра каждой из НЗ по-прежнему остаются окрашенными в цвет 1. После чего следует переход к этапу , на котором каждая из НЗ стягивается в вершину.

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

Лемма 2. Для того чтобы какая-либо затравка представляла собой СЗ, необходимо, чтобы у всякой вершины ее степень удовлетворяла неравенству

 (6)

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

Лемма 2 доказана.

Применительно к графу работа этапа состоит в просмотре вершин из и обнаружении такой вершины , для которой неравенство (6) не выполняется. Если такая вершина найдется, то эта вершина принадлежит только одной НЗ . Тогда, в силу леммы 1, множество всех затравок, отличных от и пересекающихся с НЗ , является множеством СЗ. После такого локального распознавания осуществляются два действия: 1) в графе G окрашиваются в цвет 2 ребра всех СЗ ; 2) в графе вычеркиваются все ребра и ребра всех СЗ . В оставшемся графе (обозначим его через ) снова осуществляется локальное распознавание очередной НЗ. Результатом этапа является граф, в котором ребра всех НЗ окрашены в цвет 1, а ребра всех СЗ окрашены в цвет 2. После чего следует переход к этапу . Для полного обоснования остается показать, что является справедливой

Лемма 3. В каждом графе последовательности ,,..., порождаемой в процессе работы этапа , всегда найдется вершина , для которой не выполняется условие (6).

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

Упомянутому в лемме 1 покрытию приписан индекс k=1, остальные покрытия пронумеруем индексами и через обозначим множество всех покрытий графа G; - количество затравок, составляющих покрытие . Покрытие называется минимальным, если для него выполняется равенство .

Рассмотрим теперь на примере (n,l)-графа G=(V,E) вопрос существования такого покрытия , каждая затравка которого состоит только из старых ребер. Согласно (2), (3) и (4), всех старых ребер

, (7)

где для (n,l)-графа значение . Величина (4) превосходит величину (7). Этот факт с учетом следствия 1 означает, что количество старых ребер в предфрактальном (n,l)-графе меньше такого количества ребер, которое необходимо для построения минимального покрытия.

Отсюда получаем, что построенный на этапе nсуграф содержит вершины, каждая из которых принадлежит лишь одной НЗ . Это же утверждение распространяется на всякую компоненту связности графа или на такую ее часть, которая порождается в процессе работы этапа . Иными словами, получаемая в процессе реализации этапа последовательность , обладает тем свойством, что в каждом ее элементе найдется вершина v, для которой условие (6) не выполняется. Следовательно, эта вершина идентифицирует собой НЗ , удаление которой из (согласно правилам этапа ) приводит к графу , содержащему вершину с аналогичным свойством.

Таким образом, если данный граф G является предфрактальным (n,l)-графом, то работа этапа завершается с положительным результатом.

Приведенные выше леммы 1 - 3 обеспечивают обоснование алгоритма в случае перехода от исходного графа G к условно - предфрактальному графу . Если G действительно является (n,l)-графом, то результативная (L-кратная) работа алгоритма означает построение последовательности условно-предфрактальных графов

, (8)

которая в обратном порядке воссоздает последовательность (2). Построение последовательности (8), состоящей из L графов, и означает положительный результат распознавания предфрактального графа.

Теорема 2. Алгоритм определяет траекторию (n,l)- предфрактального графа если затравка - двудольный полный граф и старые ребра пересекаются, причем причем трудоемкость алгоритма равна , где .

Литература

1. Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО, 1998

2. Кочкаров А.А., Малинецкий Г.Г. Управление безопасностью и стойкостью сложных систем в условиях внешних воздействий // Проблемы управления. 2005.№5.С.70-76.

3. Кочкаров Р.А. Целевые программы: инструментальная поддержка. М: ЗАО «Издательство «Экономика» », 2007. 223с.

4. Кунижева Л.А. Кочкаров Р.А. Многокритериальная постановка задачи выбора проектов целевых программ / Л.А. Кунижева, Р.А. Кочкаров // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета (Научный журнал КубГАУ) [Электронный ресурс]. - Краснодар: КубГАУ, 2013. - №04 (88). - IDA [article id]: 0881304031

5. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика. - 1994. Т. 6, вып. 1.

6. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.

7. Харари Ф. Теория графов. - М.: Мир, 1973.

References

1.Kochkarov A.M. Raspoznavanie fraktal'nyh grafov. Algoritmicheskij podhod. Nizhnij Arhyz: RAN SAO, 1998

2.Kochkarov A.A., Malineckij G.G. Upravlenie bezopasnost'ju i stojkost'ju slozhnyh sistem v uslovijah vneshnih vozdejstvij // Problemy upravlenija. 2005.№5.S.70-76.

3.Kochkarov R.A. Celevye programmy: instrumental'naja podderzhka. M: ZAO «Izdatel'stvo «Jekonomika» », 2007. 223s.

4.Kunizheva L.A. Kochkarov R.A. Mnogokriterial'naja postanovka zadachi vybora proektov celevyh programm / L.A. Kunizheva, R.A. Kochkarov // Politematicheskij setevoj jelektronnyj nauchnyj zhurnal Kubanskogo gosudarstvennogo agrarnogo universiteta (Nauchnyj zhurnal KubGAU) [Jelektronnyj resurs]. - Krasnodar: KubGAU, 2013. - №04 (88). - IDA [article id]: 0881304031

5. Emelichev V.A., Perepelica V.A. Slozhnost' diskretnyh mnogokriterial'nyh zadach // Diskretnaja matematika. - 1994. T. 6, vyp. 1.

6. Kristofides N. Teorija grafov. Algoritmicheskij podhod. - M.: Mir, 1978.

7. Harari F. Teorija grafov. - M.: Mir, 1973.

Размещено на Allbest.ru