Анализ графов на ЭВМ - 22 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

Pис. 8. Ориентированные графы
Вершина и ребро графа покрывают друг друга, если они
инцидентны. Ребро (v
i
, v
j
) покрывает вершины v
i
, и v
j
, а каждая из этих
вершин покрывает это ребро. Подмножество
VS
⊆
называйся покрытием
(вершинным покрытием, опорой) графа G, если каждое ребро из U
инцидентно хотя бы одной вершине из S. Покрытие графа G называется
минимальным, если оно не содержит покрытия с меньшим числом вершин,
и наименьшим, если число вершин в нем — наименьшее среди всех
покрытий графа G. Число вершин в наименьшем покрытии графа G
называется числом покрытия (числом вершинного покрытия) графа G и
обозначается через
)(G
β
.
Реберным покрытием графа G называется такое подмножество
ребер
UW
⊆
, которое скрывает все вершины графа. При этом каждая
вершина в G инцидентна по крайней мере одному ребру из W. Реберное
покрытие графа называется минимальным, если в нем не содержится
покрытий с меньшим числом ребер, и наименьшим, если число ребер в нем
— наименьшее среди всех покрытий. Число ребер в наименьшим реберном
покрытии графа G называется числом реберного покрытия и обозначается
через
)(
1
G
β
.
Лабораторное задание
1. Выполните генерацию матрицы смежности M(G) неориентированного
помеченного графа G порядка
6
≥
n
. Метки графа выберите из
подмножества натуральных чисел {1,2,…,n}.
v
1
v
2
v
3
v
4
v
1
v
2
v
3
22
                               v2                           v2

                   v1
                                      v3
                                                    v1           v3
                               v4



                         Pис. 8. Ориентированные графы
       Вершина и ребро графа покрывают друг друга, если они
инцидентны. Ребро (vi, vj) покрывает вершины vi, и vj, а каждая из этих
вершин покрывает это ребро. Подмножество S ⊆ V называйся покрытием
(вершинным покрытием, опорой) графа G, если каждое ребро из U
инцидентно хотя бы одной вершине из S. Покрытие графа G называется
минимальным, если оно не содержит покрытия с меньшим числом вершин,
и наименьшим, если число вершин в нем — наименьшее среди всех
покрытий графа G. Число вершин в наименьшем покрытии графа G
называется числом покрытия (числом вершинного покрытия) графа G и
обозначается через β (G ) .
       Реберным покрытием графа G называется такое подмножество
ребер W ⊆ U , которое скрывает все вершины графа. При этом каждая
вершина в G инцидентна по крайней мере одному ребру из W. Реберное
покрытие графа называется минимальным, если в нем не содержится
покрытий с меньшим числом ребер, и наименьшим, если число ребер в нем
— наименьшее среди всех покрытий. Число ребер в наименьшим реберном
покрытии графа G называется числом реберного покрытия и обозначается
через β 1 (G ) .
                              Лабораторное задание
 1. Выполните генерацию матрицы смежности M(G) неориентированного
помеченного графа G порядка                n≥ 6.   Метки графа выберите из
подмножества натуральных чисел {1,2,…,n}.




                                       22

Страницы