Определение сильной связности темпоральных графов

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

ОПРЕДЕЛЕНИЕ СИЛЬНОЙ СВЯЗНОСТИ ТЕМПОРАЛЬНЫХ ГРАФОВ

Л.С. Берштейн

А.В. Боженюк

Технологический институт Южного федерального университета, Таганрог

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

Традиционно теория графов используется для представления отношений между элементами сложных структур различной природы [Кофман, 1975], [Кристофидес, 1978], [Харари, 1973]. При этом данные отношения между элементами являются постоянными и не меняются во времени. Такие графы в работе [Kostakos, 2008] были названы «статическими». В случае, когда отношения между элементами некоторой структуры изменяются во времени, традиционные «статические» графы неприменимы для их описания и моделирования.

В данной работе рассматривается подход к построению темпорального графа, то есть графовой модели, в которой связи между элементами (вершинами графа) меняются во времени. Необходимо отметить, что само понятие темпорального графа (temporal graph) известно в литературе и трактуется в достаточно широком диапазоне [Baldan et al., 2004], [Barzilay et al., 2002], [Bramsen et al., 2006], [Dittmann et al., 2005].

1. Основные понятия и определения

Темпоральным графом назовем тройку G=(X,{_t},T), где X - множество вершин графа c числом вершин |X|=n; T={1,2,…,N} - множество натуральных чисел, определяющих (дискретное) время; {_t} - семейство соответствий, или отображений множества вершин X в себя в момент времени tT, т.е. (tT)_t: XX. Причем, для различных моментов времени эти отображения, в общем случае, различные: (xX)(t₁,t₂T| t₁t₂) [_t1(x) _t2(x)].

Будем считать, что вершина x_j является смежной вершине x_i по моменту времени tT, если выполняется условие: x_jt(x_i); вершина x_k достижима из вершины x₁, если существует такая последовательность вершин

темпоральный граф связность мальгранж

seq(x₁,x_k) = (x₁,x₂,…,x_k), (1.1)

что , , …, и при этом выполняется условие:

i₁ i₂ … i_k-1, i₁, i₂,…, i_k-1T.

Иными словами, если в последовательности (1.1) каждая последующая вершина смежна предыдущей по моменту времени не меньшем чем моменты, по которым все предыдущие вершины в этой последовательности являются смежными.

Значение i_k-1 назовем временем достижимости вершины x_k из вершины x₁.

Если существует несколько L последовательностей вида (1.1) из вершины x₁ в вершину x_k, то значения для каждой последовательности могут быть различными. Наименьшее из них назовем минимальным временем достижимости вершины x_k из вершины x₁, т.е.:

.

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

Величину

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

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

Определение 1. Транзитивным замыканием вершины x_iX будем называть множество пар:

,

где величина t_jT определяет минимальное время, за которое вершина x_j достижима из вершины x_i. причем, t_i=1. Если вершина x_j ни за какое время не достижима из вершины x_i, то будем полагать, что t_j=.

Определение 2. Обратным транзитивным замыканием вершины x_iX будем называть множество пар:

,

где величина аналогично транзитивному замыканию, определяет минимальное дискретное время, за которое вершина x_i достижима из вершины x_j. причем, . Если вершина x_i не достижима из вершины x_j, то будем полагать, что .

Пример 1. Для темпорального графа G, приведенного на рисунке 1, множества времени T={1,2,3} и вершины x₁ транзитивным и обратным транзитивным замыканием являются: и .

Рис. 1. Пример темпорального графа

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

Если время , то исходный темпоральный граф сильно связный, а время сильной связности определится как: .

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

Так для темпорального графа G, приведенного на рис.1, имеем:

= =.

Отсюда следует, что темпоральный граф G является сильно связанный и время сильной связности равно 2.

2. Нахождение транзитивного замыкания

Обозначим через _ij, i,j=1,2,…, n - подмножество моментов времени, когда вершина x_i смежна с вершиной x_j. По определению будем считать, что _ii=T, т.е. вершина смежна сама с собой в любой момент времени.

Рассмотрим подход для нахождения транзитивного замыкания произвольной вершины, например, х₁:

Берем вершину х₁. Присваиваем ей наименьшее значение времени достижимости «1». Всем вершинам {x_j} смежным с вершиной х₁ присваиваем время достижимости t_j=min{_1j}. После этого помечаем вершину х₁ как «просмотренную».

Выбираем произвольную вершину x_k, помеченную временем t_k, и не являющуюся еще просмотренной. Для всех вершин {x_j} смежных с вершиной x_k вычисляем время t'_j следующим образом: если t_k>max{_kj}, то t'_j=; если t_kmax{_kj}, то определяем наименьшее t'_j{_kj} так, что бы выполнялось t'_j= t_k. Если вершина x_j еще не просмотренная, и время не было присвоено, то присваиваем ей время t_j=t'_j; Если вершине x_j уже было присвоено некоторое время t_j, но t'_j<t_j, то присваиваем новое время t_j=t'_j, и кроме того, вершину x_j помечаем как непросмотренную. После этого вершину x_k, помечаем как просмотренную.

Процесс продолжается до тех пор, пока все вершины, помеченные временем, не станут просмотренными.

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

Пример 2. Рассмотрим пример нахождения транзитивного замыкания вершины х₁ для графа G, приведенного на рисунке 2:

Рис.2. Нахождение транзитивного замыкания вершины х₁

- Присваиваем вершине х₁ время достижимости «1». Вершине x₂ смежной с вершиной х₁ присваиваем время достижимости t₂=min{1,2}=1. Вершине x₄ смежной с вершиной х₁ присваиваем время достижимости t₄=min{1,3}=1. После этого помечаем вершину х₁ как «просмотренную».

- Берем одну из помеченных временем и не просмотренных вершин (x₂, x₄) - например вершину x₂. Вершине x₃ смежной с вершиной х₂ присваиваем время достижимости t₃= 1. После этого помечаем вершину х₂ как «просмотренную».

- Далее берем одну из помеченных временем и не просмотренных вершин (x₃, x₄) - например вершину x₃. Вершине x₅ смежной с вершиной х₂ присваиваем время достижимости t₅= 3. После этого помечаем вершину х₃ как «просмотренную».

- Берем одну из помеченных временем и не просмотренных вершин (x₅, x₄) - например вершину x₅. Так как (любое) время из множества ₅₆ меньше чем t₅, то вершине x₆ ничего не присваиваем, а вершину x₅ помечаем как просмотренную.

- Берем единственную помеченную временем и не просмотренную вершину x₄. Для вершины x₅ вычисляем t'₅,=2. Так как величина t'₅<t₅, то вершине x₅ присваиваем новое время t₅,=2 и помечаем ее как непросмотренную. Вершину x₄ помечаем как просмотренную.

- Берем единственную помеченную временем и не просмотренную вершину x₅. Для вершины x₆ вычисляем t₂,=2. Вершину x₅ помечаем как просмотренную.

- Берем единственную помеченную временем и не просмотренную вершину x₆. Помечаем ее как просмотренную.

- Так как все вершины графа просмотрены, то по помеченным вершинам (входят все вершины множества X) записываем транзитивное замыкание: .

3. Нахождение обратного транзитивного замыкания

Рассмотрим теперь подход для нахождения обратного транзитивного замыкания произвольной вершины, например, х₁:

Берем вершину х₁. Присваиваем ей значение наименьшего времени достижимости «1». Всем вершинам {x_j}, которым вершина х₁ является смежной, присваиваем множество пар времени T_j={<t_j/t_j>}, где t_jj1. После этого помечаем вершину х₁ как «просмотренную».

Пример 3. Для фрагмента графа, приведенного на рисунке 3, множество пар T_j={<2/2>,<3/3>,<4/4>}.

Рис. 3. Фрагмент графа

Выбираем произвольную вершину x_k, помеченную множеством пар T_k, и не являющуюся просмотренной. Всем вершинам {x_j}, для которых вершина x_k является смежной, вычисляем множество T'_j согласно правилам:

Пусть множество пар T_k={<a₁/a₂>}, а подмножество времени смежности _jk={b}. Каждый элемент b сравниваем со всеми вторыми элементами a₂.

Если во всех парах множества T_k второй элемент a₂>b, то присваиваем T'_j=.

Если ba₂, то пару <a₁/b> записываем в T'_j. После этого, все пары в T'_j сравниваем между собой. Если существуют две пары <a₁/a₂> и <a₃/a₄>, такие, что a₁a₃ и a₂a₄, то пару <a₁/a₂> вычеркиваем из множества T'_j.

В таблице 1 приведены примеры нахождения множества T'_j:

Табл.1. Примеры нахождения множества T'_j

Количество пар в T'_j определяет число моментов времени, когда вершина х₁ достижима из x_j. Причем, первый элемент пары (a₁) определяет само время достижения, а второй элемент (a₂) определяет последнее (т.е., наименьшее) время в пути из вершины x_j в вершину x₁. Естественно, что выполняется неравенство a₁a₂.

Если вершина x_j еще не просмотренная, и множество T_j ей еще не было присвоено, то присваиваем T_j =T'_j;

Если вершине x_j уже было присвоено множество пар T_j, то производим сравнение T_j T'_j и формируем новое множество пар T_j^new.

Рассмотрим правило сравнения множеств T_j и T'_j и формирования множества T_j^new:

Пусть множество T_j={<a₁/a₂>}, а T'_j ={<b₁/b₂>}.

Сформируем вначале T_j^new=T_j={<a₁/a₂>}. Затем, каждую пару <b₁/b₂> из T'_j сравним с каждой парой <a₁/a₂> из T_j^new согласно правилу:

- Если a₁b₁ и a₂ b₂, то пару <a₁/a₂> вычеркиваем из множества T_j^new. После этого в любом случае пару <b₁/b₂> дописываем во множество T_j^new.

Пример 4. Рассмотрим пример формирования множества T_j^new. Пусть множество T_j={<7/3>,<4/2>,<3/1>}, а множество T'_j={<3/3>,<2/1>}. Произведя сравнения по рассмотренному правилу, получаем множество T_j^new={<3/3>,<4/2>,<2/1>}.

Если множество T_j^new отличается от старого множества T_j, то вершине x_j приписываем новое множество T_j=T_j^new, и кроме того, вершину x_j помечаем как непросмотренную. Вершину x_k помечаем как просмотренную.

Процесс продолжается до тех пор, пока все вершины, помеченные временем, станут просмотренными.

В результате каждой просмотренной вершине будет присвоено множество пар времени достижимости вершины х₁. Наименьший первый элемент пар множества определит минимальное время достижения вершины х₁. Те вершины, которые останутся не помеченными и не просмотренными, не будут достижимыми из вершины х₁. Помеченные временем вершины войдут в обратное транзитивное замыкание с соответствующим временем.

Пример 5. Рассмотрим пример нахождения обратного транзитивного замыкания вершины х₁ для графа G, приведенного на рисунке 2.

Вершине х₁ присваиваем значение наименьшего времени достижимости «1». Вершине x₂, которой вершина х₁ является смежной, присваиваем множество пар времени , а вершине х₄ - множество пар . После этого помечаем вершину х₁ как «просмотренную» (рис.4).

Рис.4. Нахождение обратного транзитивного замыкания вершины х₁

- Выбираем вершину x₂, помеченную множеством пар T₂ и не являющуюся просмотренной. Для вершины x₃, для которой вершина x₂ является смежной, вычисляем множество T'₃={<2,1>,<4,3>}. Так как вершина x₃ не была помечена, то присваиваем T₃=T'₃={<2,1>,<4,3>} и помечаем ее как помеченную. Аналогично присваиваем вершине x₅ множество T₅={<2,1>,<4,3>} и x₆ множество T₆={<2,1>,<4,3>}, помечая их как просмотренные.

- Выбираем помеченную и непросмотренную вершину x₄. Для вершины x₅ определяем множество T'₅={<1,1>}. Далее определяем новое множество T₅={<1,1>,<4,3>} и вершину x₅ опять помечаем как непросмотренную. Аналогично для вершины x₆ находим новое множество T₆={<1,1>,<4,3>}. После чего опять помечаем их как просмотренные.

- Так как все вершины графа просмотрены, то по помеченным вершинам (входят все вершины множества X) записываем обратное транзитивное замыкание:

.

Таким образом, рассматриваемый темпоральный граф G является сильно связным, а время сильной связности равно 2.

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 10-01-00029а).

Список литературы

1. Кофман А. Введение в прикладную комбинаторику. - М.: Наука, 1975.

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

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

4. Baldan P., Corradini A., Konig B. Verifying finite-state graph grammars: An unfolding-based approach. // Proc. of CONCUR'04, vol.3170 of Lecture Notes in Computer Science, Springer, 2004.

5. Barzilay R, Elhadad N., McKeown K. Inferring strategies for sentence ordering in multidocument news summarization. // Journal of Artificial Intelligence Research. 2002. №17.

6. Bramsen P.J. Doing Time: Inducing Temporal Graphs. // Technical report, Massachusetts Institute of Technology, 2006.

7. Dittmann F., Bobda C. Temporal graph placement on mesh-based coarse grain reconfigurable systems using the spectral method // From Specification to Embedded Systems Application. Springer. 2005. №184.

8. Kostakos V. Temporal graphs. // Proc. of Physica A: Statistical Mechanics and its Applications. Vol.388. Issue 6. Elsevier, 2008.

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