Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Январь 2012   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по дискретной математике


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Коцюрбенко Алексей aka Жерар
Статус: Профессор
Рейтинг: 3782
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2618
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2094
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика дискретная

Номер выпуска:267
Дата выхода:24.01.2012, 23:30
Администратор рассылки:Асмик (Академик)
Подписчиков / экспертов:53 / 60
Вопросов / ответов:1 / 1

Консультация # 185230: Уважаемые эксперты! Пожалуйста, ответьте на вопрос: По заданному орграфу построить матрицы базисного разрезающего множества и базисного цикла. Если можно, то само построение матриц объясните поподробнее. С матрицами смежности и инцинд...

Консультация # 185230:

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


Если можно, то само построение матриц объясните поподробнее. С матрицами смежности и инциндентности разобралась, а с этим нет.

Дата отправки: 20.01.2012, 13:41
Вопрос задал: Посетитель - 375268 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Профессор):

Здравствуйте, Посетитель - 375268!

Вначале вспомним теорию.

Пусть у нас имеется простой связный граф G = <X, E>, заданный множеством вершин X = {x1,..., xn} и множеством рёбер E = {e1,..., em}.

Циклом будет последовательность рёбер, такая что концевая вершина каждого ребра является начальной вершиной следующего, а конец последнего ребра совпадает с началом первого. Множество всех циклов графа записывается с помощью матрицы циклов С = (сik), строки которой соответствуют циклам Ci, а столбцы - рёбрам ek. При этом cik = 1, если ek∈Ci и cik = 0, если ek∉Ci. Для ориентированного графа выбирается также направление обхода цикла и при ek∈Ci принимается cik = -1 для ek↑↓Ci и cik = 1 для ek↑↑Ci.

Разрезающим множеством будет минимальное множество ребер, при удалении которых из графа G он перестанет быть связным и распадётся на два подграфа G1 и G2 (минимальное означает, что любое его подмножество разрезающим уже не будет). Все разрезающие множества графа также можно записать с помощью матрицы S = (sjk), строки которой соответствуют разрезающим множествам Sj, а столбцы - рёбрам ek. При этом sjk = 1, если ek∈Sj и sjk = 0, если ek∉Sj. Для ориентированного графа выбирается также направление разреза и при ek∈Sj принимается sjk = -1 для ek↑↓ ;Sj и sjk = 1 для ek↑↑Sj.

Граф T = <X, E'>, E'∈E (то есть содержащий все вершины графа G, но только часть его рёбер), являющийся деревом (то есть связный и не содержащий циклов), называется остовом графа G. Для ориентированного графа остов является ориентированным деревом, то есть помимо связности и отсутствия циклов выполняется условие: в каждую вершину входит ровно одна дуга (ребро), за исключением единственной вершины - корня дерева. Остальные рёбра (не входящие в остов) образуют коостов (кодерево) T*. Рёбра остова (из множества E') называют ветвями, а рёбра коостова (из множества E\E') - хордами. Любой связный (и только связный) граф имеет остов, причём число ветвей в нём равно n-1 (соответственно, число хорд в коостове равно m-n+1).

Так как остов T является деревом, то при добавлении к нему любой хорды из коостова T* в нём образуется ровно один цикл, называемый базисным циклом графа. Множество всех таких циклов называется базисным множеством циклов графа G относительно остова T (оно, очевидно, содержит m-n+1 базисный цикл - по числу хорд в коостове). Матрица базисных циклов Cf будет иметь размерность (m-n+1) x m. В каждой её строке ненулевыми будут: элемент в столбце, соответствующем одной из хорд коостова (своей для каждой строки), и элементы в столбцах, соответствующих ветвям остова, которые образуют цикл вместе с данной хордой. Остальные элементы будут равны нулю. Знак ненулевых элементов для ориентированного графа определяется совпадением или несовпадением направления соответствующего ребра с направлением цикла.

Так как остов T является деревом, то при удалении из него любой ветви он распадётся на два несвязных подостова T1 и T2. Добавляя все хорды коостова, вершины которых лежат в разных подостовах, получаем разрезающее мно жество, делящее граф G на два несвязных подграфа G1 и G2 (остовами которых и являются T1 и T2). Оно называется базисным разрезающим множеством графа G относительно остова T (всего будет n-1 базисное разрезающее множество - по числу ветвей остова). Матрица базисного разрезающего множества Sf будет иметь размерность (n-1) x m. В каждой её строке ненулевыми будут: элемент в столбце, соответствующем одной из ветвей остова (своей для каждой строки), и элементы в столбцах, соответствующих хордам коостова, которые образуют разрезающее множество вместе с данной ветвью. Остальные элементы будут равны нулю. Знак ненулевых элементов для ориентированного графа определяется совпадением или несовпадением направления соответствующего ребра с направлением разреза.

Как правило, в графе можно выбрать несколько разных остовов. В данном случае имеем ориентир ованный граф, содержащий 6 вершин и 9 рёбер. Следовательно, остов будет содержать 5 (6-1) рёбер, граф будет иметь 4 (9-6+1) базисных цикла и 5 (6-1) базисных разрезающих множества.

Для данного графа остовами будут следующие деревья: x1x6x2x3x4x5 и x3x4x5x6x2x1. Выберем второе из них, тогда множество ветвей остова будет E' = {2,3,4,8,9}, а множество хорд коостова - E\E' = {1,5,6,7}. Построим искомые матрицы.

Для построения матрицы базисных циклов будем по очереди добавлять к множеству ветвей остова одну из хорд и отмечать получившийся цикл (в качестве направления обхода циклов примем направление по часовой стрелке). При добавлении хорд 1, 5, 6 и 7 будут получаться циклы {1,3,2}, {5,3,4}, {6,3,4,8} и {7,3,4,8,9} соответственно. Заполним соответствующие элементы матрицы единицами:

Так как граф ориентированный, то нужно учесть направление обхода циклов. Для первого цикла все рёбра направлены против направления обхода, для второго и четвёртого - по направлению, для третьего - все по направлению, кроме ребра 6. Соответственно, матрица будет иметь вид:


Для построения матрицы базисного разрезающего множества будем по очереди убирать из остова каждую из ветвей и отмечать, какие рёбра образуют разрезающее множество для двух получившихся подграфов (за направление разреза примем направление от подграфа, содержащего корень остова - вершину x3). Например, при удалении ветви 2 получаем подграфы x3x4x5x6x2 и x1, связанные рёбрами {1,2}, причём первое из них идёт против направления разреза, а второе - по напра влению. При удалении ветви 3 получаем подграфы x3x4x5x6 и x2x1, связанные рёбрами {1,3,5,6,7}, среди которых рёбра 3 и 6 имеют положительное направление, а остальные - отрицательное. Продолжая аналогично, получаем матрицу:

Для проверки можно воспользоваться тем свойством, что Cf·SfT = Sf·CfT = 0.

Консультировал: Коцюрбенко Алексей aka Жерар (Профессор)
Дата отправки: 20.01.2012, 20:57
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.35 от 21.01.2012
В избранное