На головну

Матричні уявлення мереж

  1. Iii) повідомлення для загального відома будь-якими засобами подання та виконання своїх творів.
  2. Базові уявлення про безпеку в Інтернет
  3. Базові уявлення про архітектуру ЕОМ. Типи архітектур.
  4. Квиток 25 СПОСОБИ ПОДАННЯ ПРОДУКЦІЇ НА КОНТРОЛЬ
  5. Векторні-МАТРИЧНІ умножителю
  6. Векторні і матричні функції.
  7. Види і аналіз електричних мереж

Кожна мережа може бути однозначно задана в матричному поданні. Основними використовуваними для цього матричними величинами є матриці узагальнених вартостей Cn, n, суміжності Xn, n і інціденцій Zn, k. Тут індекси є розмірністю матриць, n - Число вузлів мережі, k - Число її дуг.

елементом cij матриці вартостей Cn, n є узагальнена вартість дуги [I, j] A. Для неориентированной мережі ця матриця симетрична. значення елементів cij с i и j, Для яких в графі G не існує дуг [i, j], Визначається конкретним завданням і зазвичай вважається рівним нескінченності ( ).

елемент xij матриці суміжності Xn, n визначається наступним чином:

Xi j =    1, якщо [i, j] A, 0 в іншому випадку.

Властивості матриці суміжності для орієнтованої мережі:

1) кожен нульовий стовпець відповідає джерелу;

2) кожна нульова рядок відповідає стоку;

3) ненульовий елемент головної діагоналі відповідає петлі;

4) матриця не симетрична.

Для неориентированной мережі ця матриця симетрична, для неї виконується властивість 3) і кожному вузлу мережі, яка не пов'язана з усіма іншими її вузлами, відповідають нульові рядок і стовпець матриці суміжності.

Матриця інціденцій пов'язана з альтернативним поданням мережі, в якому кожній дузі ставиться у відповідність її номер, а не пара номерів пов'язаних з нею вузлів. елементи zij матриці інціденцій мають вигляд:

Zij=    1, якщо вузол i - Початок дуги j, -1, Якщо вузол i - Кінець дуги j,0 в інших випадках.  дляоріентірованнойсеті
Zij=    1, якщо вузол i належить дузі j, 0 в іншому випадку.  длянеоріентірованнойсеті

Матриці узагальнених вартостей Cn, n, суміжності Xn, n і інціденцій Zn, k для мережі (рис. 6) мають такий вигляд:

C = ; X = ;

Z = ,

для Z: [1, 2] = 1; (1, 3) = 2; [2, 2] = 3;

(2, 3) = 4; (2, 4) = 5; [3, 4] = 6.

Матриця відстаней. Для введення цього поняття визначимо відстань між вершинами i и j. якщо вершини i и j зв'язкові, то відстанню між ними назвемо довжину мінімального (по числу обходу ребер) простого шляху, який зв'язує ці вершини; якщо вершини i и j незв'язні, то покладемо відстань рівним нулю (нуль як заперечення будь-якого шляху зв'язує ці вершини). При такому визначенні відстані відстань між вершиною і яку сама ж дорівнює 2 (довжина шляху по ребру і назад). Якщо ж при вершині є петля, то відстань між вершиною і яку сама ж дорівнює 1.

Теорема. Для визначення маршрутів, що складаються з k ребер (дуг), необхідно звести в k-у ступінь матрицю суміжності вершин Х. тоді елемент хij[k] матриці Xk= X [k] дасть кількість маршрутів довжини k (Що складаються з k ребер) з вершини i в вершину j.

Для побудови матриці відстаней для n-вершина графа з матрицею суміжності X, Яка вказувала б відстань між будь-якими двома вершинами, введемо в розгляд матриці X{k}=X[k]?X[k?1], де k= 2,3, ...,n-1 і X{1}=X[1]=X. З способу побудови матриць X[k] випливає, що X[k]?X[k?1] (k= 2,3, ...,n-1) І, отже, X{k} (k= 1,2, ...,n-1) Є (0,1) -Матриця. причому матриця X{2} містить 1 тільки на тих місцях, де визначаються цим місцем (номер рядка і номер стовпця) вершини з'єднані деяким шляхом довжини два і не з'єднані меншим шляхом. аналогічно, X{3} містить 1 тільки на тих місцях, де визначаються цим місцем вершини з'єднані шляхом довжини три і не з'єднані ніяким шляхом меншої довжини, і т.д. Таким чином, матриця D= ?k=1n?1k?X{k} і буде шуканої матрицею відстаней. елемент dij цієї матриці і буде дорівнює відстані між вершинами i и j. Відстань між вершинами u и v будемо також позначати як d(u,v). по матриці D визначаються діаметр d графа G, як максимальне значення елементів цієї матриці.

Крім матриці відстаней теорія графів розглядає і інші матриці, елементи яких визначаються через довжину шляху. Такий, наприклад, є матриця обходів. В матриці обходів (i,j) -й Елемент дорівнює довжині найдовшого шляху (найбільш довгому ланцюгу) з i-ої вершини в j-у, а якщо таких шляхів немає взагалі, то відповідно до визначення відстані (i,j) -ий Елемент матриці обходів вважається рівним нулю.

ексцентриситет e(v) вершини v в зв'язковому графі ? визначається як max d(u,v) По всіх вершин u в ?. радіусом r(?) називається найменший з ексцентриситетом вершин. Зауважимо, що найбільший з ексцентриситетом дорівнює діаметру графа. вершина v називається центральної вершиною графа ?, якщо e(v) =r(?); центр графа ? - безліч всіх центральних вершин.

Теорема Жордана-Сильвестра. Кожне дерево має центр, що складається або з однієї вершини або двох суміжних вершин.

Доведення. позначимо через K1 граф, що складається з однієї ізольованої вершини, а через K2 - граф - з двох вершин з'єднаних ребром. За визначенням покладемо e(K1) =r(K1) = 0. Тоді твердження теореми буде виконано для K1 і K2. Покажемо, що у будь-якого дерева T ті ж центральні вершини, що і у дерева T', Отриманого з T видаленням всіх його висячих вершин. Ясно, що відстань від даної вершини u до будь-якої іншої вершини v може досягати максимального значення тільки тоді, коли v - Висяча вершина.

Таким чином, ексцентриситет кожної вершини дерева T'Точно на одиницю менше ексцентриситету цієї ж вершини в T. Звідси випливає, що вершини дерева T, Що мають найменший ексцентриситет в T, Збігаються з вершинами, що мають найменший ексцентриситет в T', Тобто центри дерев T и T'Збігаються. Якщо процес видалення висячих вершин продовжити, то ми отримаємо послідовність дерев з тим же центром, що і у T. В силу кінцівки T ми обов'язково прийдемо або до K1, або до K2. У будь-якому випадку все вершини дерева отриманого таким способом, утворюють центр дерева, який, таким чином, являє собою або з єдиною вершини, або з двох суміжних вершин. Доказ закінчено.

Укладання графа. Плоскі і планарні графи.

Укладання графа (вкладення графа) - таке відображення вершин і ребер графа відповідно в точки і безперервні криві деякого простору, що вершини, інцидентні ребру, відображаються в кінці кривої, що відповідає цьому ребру. Правильним укладанням називається укладання, при якій різним вершин відповідають різні точки, а криві, відповідні ребрах (виключаючи їх кінцеві точки), не проходять через точки, що відповідають вершинам, і не перетинаються. Будь-граф допускає правильну укладку в тривимірний простір. Граф, що допускає правильну укладку на площині, наз. плоским.

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

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

Приклад плоского графа наведений на рис. зліва. Ізоморфний йому повний граф К4 (На рис. Праворуч), що укладається на площині, має два пересічних ребра, тому граф К4 не є плоским - він тільки планарний.



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   Наступна

Вступ | Перелік використовуваних надалі позначень | визначення | Орієнтовані і неорієнтовані мережі | Теорема про максимальний потік і мінімальному розрізі | Ізоморфізм і гомеоморфизм графів. | Алгоритм рішення (алгоритм Дейкстри) | приклад рішення | Приклади економічних задач, що зводяться до задачі про найкоротшою ланцюга | Алгоритм рішення (алгоритм Літтла) |

© um.co.ua - учбові матеріали та реферати