5.2.10 Расчет числа внутренней устойчивости (g) графа g
С
Таблица 5.5 — Таблица образов
{xi,xj}
┐
4,6
5,7
8,9
4,8
5,7,9
6,9
4,9
5,7,8
6
5,8
4,6,7,9
5,9
4,6,7,8
6,8
5,7,9
4
6,9
5,7,8
4
и ┐
Поскольку не во всех строках столбца ┐ табл. 5.5 указаны знаки , сформируем табл. 5.6 трехэлементных множеств {xi,xj,xk} и найдем им образ и ┐ .
Таблица 5.6 — Таблица образов
и ┐
.
{xi,xj,xk}
┐
4,6,8
5,7,9
4,6,9
5,8,7
Поскольку во всех строках табл. 5.5 указаны знаки процесс вычислений закончен и можно перейти к анализу табл. 5.4 и табл. 5.5.
По итогам анализа можно сформировать множество S ядер графа G, т.е.
S={{x5,x8},{x5,x4},{x4,x6,x8},{x4,x6,x9}},
где S1={x5,x8}, S2={x5,x9}, S3={x4,x6,x8}, S4={x4x6,x6}.
Тогда
(G)=
{|Si|}=
{|
|}|i=1;4=3.
На этом расчеты числовых характеристик графа G закончены.
6 Методические указания по выполнению расчетно-графической работы № 2 на тему: «Нахождение кратчайшего остова неориентированного графа по алгоритму Дейкстра»
6.1 Задание на расчетно-графическую работу № 2
Задание на РГР
формулируется следующим образом: «Найти
кратчайший остов неориентированного
графа G
(рис. 6.1) по алгоритму Дейкстра. Протяженность
(вес) ребер приведены в табл. 6.1, где
— означает отсутствие ребра (
),
а «1» — его наличие, которое необходимо
умножить на вес ребра. Для вариантов 1
—10 начальной вершиной является
,
для вариантов 11 — 20 — вершина
,
для вариантов 21 — 30 — вершина
,
для вариантов 31 — 40 — вершина
,
для вариантов 41 — 50 — вершина
».
Таблица 6.1— Данные для формирования графа G по вариантам
Старший разряд номера варианта |
Индексы вершин, инцидентных ребру |
|||||||||
0,1 |
0,2 |
0,3 |
1,3 |
1,4 |
2,3 |
2,5 |
3,4 |
3,5 |
3,6 |
|
Вес ребра (условных единиц) |
||||||||||
7 |
9 |
12 |
6 |
4 |
6 |
7 |
10 |
7 |
11 |
|
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
3 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
4 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
5 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
6 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
7 |
1 |
1 |
|
1 |
1 |
|
1 |
1 |
1 |
1 |
8 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
9 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Таблица 6.1 — Продолжение
Младший разряд номера варианта |
Индексы вершин, инцидентных ребру |
|||||||||
4,6 |
4,7 |
5,6 |
5,8 |
6,7 |
6,8 |
6,9 |
7,9 |
8,9 |
|
|
Вес ребра (условных единиц) |
||||||||||
2 |
6 |
4 |
9 |
8 |
5 |
4 |
3 |
9 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
|
2 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
3 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
|
4 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
|
5 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
|
6 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
7 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
8 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
9 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
|