Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Методи формування фундаментальних дерев.

Матриці перерізів та контурів.

При вивчені структурних властивостей графів зручно користуватися їх матричними представленнями.

Основні суграфи, які мають велике значення у прикладній області теорії графів - дерева, доповнення, перерізи, контури( цикли).

Базова матрична модель графа - це матриця інцидентності S. Над матрицею інцидентності S можемо проводити еквівалентні перетворення:додавати рядки, переставляти стовпці. Елементи матриць інцидентності неорієнтованих графів можуть бути тільки нулі і одиниці. Тому додавання над елементами виконуються за так званим mod 2(якщо у стовпцю стоїть дві одиниці, то при додаванні рядків даних стовпців, ми отримуємо нуль, але при додаванні рядків у стовпцю яких стоять 0 та 1 ми отримуємо одиницю).

Із n рядків матриці S зв’язного графа один рядок завжди лінійно залежний, тобто ранг матриці S r = n - 1. Число незалежних стовпців матриці інцидентності також дорівнює n - 1, якщо відповідні їм ребра утворюють дерево графа. Решта m - n + 1 стовпців відповідає ребрам, які утворюють доповнення графа.

Якщо необхідно сформувати одне дерево, яке володіє будь-якими властивостями (наприклад, екстремальне дерево), то можемо скористуватися алгебраїчними способами перетворення матриці інцидентності.

Попередньо ребра графа нумеруються. Необхідно вибрати n - 1 стовпців, щоб у сукупності вони були незалежні. Для цього використовуються операції над матрицею інцидентності, не порушуючи рангу матриці.

У результаті в матриці S можемо виділити одиничну матрицю, стовпці якої будуть відповідати гілкам дерева. Якщо використовується матриця S, то в кінці всі елементи останнього рядка перетворюються в нулі і виділяється одинична матриця (n - 1) -го порядку. Ця процедура подібна алгоритму виключення Гауса-Жордана з вибором опорних елементів за стовпчиками.

Приклад.

Рис. 18. Граф.

S = .

Замінимо перший рядок її сумою з другим рядком по mod 2;

S ^I = _.

Замінимо третій рядок її сумою з першим рядком .

S ^II = .

Тепер замінимо:

n перший рядок її сумою з третім рядком ;

n другий рядок її сумою з третім рядком;

n четвертий рядок її сумою з третім рядком;

S ^III = _.

В перших трьох стовпцях та рядках утворилися елементи одиничної матриці. Але в наступному стовпці неможливо вибрати опорний елемент, так як у решти рядків цього стовпчика стоять нульові елементи. Тому четвертий стовпець пропускається і розглядається п’ятий.

Тепер замінимо:

n другий рядок її сумою з четвертим рядком;

n третій рядок її сумою з четвертим рядком;

n п’ятий рядок її сумою з четвертим рядком;

S ^IМ = .

Далі маємо можливість вибрати опорний (ведучий) елемент в сьомому стовпчику. Заміняємо останній рядок її сумою з п’ятим рядком та отримуємо.

S ^М = _.

Як і чекали останній рядок перетворився в нульовий його ми можемо відкинути. Маємо п’ять стовпців, в яких є тільки по одному одиничному елементу. Вони складають одиничну субматрицю, а відповідні їм ребра {e₁, e₂, e₃, e₅, e₇} утворюють дерево графа. Решта стовпців {e₄, e₆, e₈, e₉}, відповідають хордам, які утворюють доповнення дерева. Переставимо стовпчики так, щоб з ліва була одинична субматриця. Результат перетворення матриці інцидентності запишемо так:

П = .

Сформували фундаментальне дерево, яке покажемо на рис. 19.

Рис. 19.

Дерево графа визначає множину перерізів, яке представлене в аналітичній формі матрицею П, яка називається матрицею перерізів. Між гілками дерева та перерізами є взаємно-однозначне співвідношення. Тому рядки матриці П будемо позначати номерами тих гілок, які визначають перерізи. Матрицю перерізів можемо представити в канонічній формі яка має вигляд:

П = ,

де p - матриця перерізів для хорд розміру (n - 1) ´ (m - n + 1).

Гілка дерева, яка визначає переріз, називається визначаючою гілкою. Різні дерева породжують і різні сукупності незалежних перерізів.

Матриця контурів.

Будь-яка з m - n + 1 хорд утворює сумісно з сукупністю гілок дерева простий цикл. Число s = m - n + 1 називається цикломатичним числом графа.

Головний цикл (контур) - визначається кожною хордою, яка називається визначаючою хордою.

Матриця контурів Р розміру (m - n + 1) ´ m, рядки якої відповідають контурам,, а стовпці - ребрам

Р = _ .

Стовпці матриці контурів, відповідні хордам, можемо виділити в одиничну підматрицю.

Р = _ .

Таким чином, в канонічній формі матриця контурів має вигляд:

Р = [r, 1],

де r - матриця контурів для гілок дерева розміру (m - n + 1) ´ (n - 1).

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Алгоритми побудови дерев екстремальної ваги	\|	Внутрішнє законодавство як джерело МПрП.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.006 сек.