Page 46 - 2577
P. 46
інцидентності неможливо відтворити орієнтований граф. Таку можливість забезпечує
матриця суміжності.
Нехай G орієнтований граф, а В матриця, рядки якої означені вершинами графа і
стовпці означені тими же вершинами і в тому ж порядку. Елемент від матриці В дорівнює
одиниці, якщо є ребро (дуга) із і – ої вершини в j – ту вершину і дорівнює нулю в
протилежному випадку. Матриця В називається матрицею суміжності графа G.
b a b c
a 0 1 1
a b 1 1 1
c 0 0 0
c
Рисунок 3.13 – Орграф та його матриця суміжності
Підграф VG , E є каркасним графом для графа V ,E , якщо V V .
G
G
Вершина a зв’язаного графа V ,E є вершиною розрізу або точкою з’єднання,
V
якщо вилучення цієї вершини та інцидентних її ребер призводить до порушення зв’язаності
графа.
G
Теорема. Вершина а графа V ,E є точкою з’єднання тоді і тільки тоді, поки
існують різні вершини v і w такі, що кожний шлях із v в w проходить через а.
В графі, який показаний на рис. 3.14, вершини v , v та v – вершини розрізу (точки
3 4 6
з’єднання).
V5
V2
V4
V1
V7
V3
V6
V8
Рисунок 3.14 – Граф, який має точки розрізу
Граф V ,E називається двозв’язаним, якщо він не вміщує точок з’єднання.
G
Циклометричне число графа. Нехай G неорієнтований s – граф з N вершинами M
ребрами і р зв’язаними компонентами.
Число MG N p називається циклометричним числом.
По суті циклометричне число визначає кількість незалежних циклів, тобто таких
циклів у графі, які відрізняються хоча б одним ребром .
3.2 Вихідні дані для проектування топологічної структури комп’ютерної мережі
Задача синтезу топологічної структури є однією із основних при проектуванні
комп’ютерної мережі і включає в себе вибір оптимальної схеми з’єднання вузлів комунікації
і концентрації, вибір пропускної здатності ліній і оптимальних маршрутів передачі
s – граф – це мультограф, в якого найбільше число паралельних дуг, які з'єднують вершини
x i і x j дорівнюють s.
Детальніше в книзі Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир,
1978. – 430с.
43
