Анализ графов на ЭВМ. Методические указания. Макарычев П.П - 22 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

22
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 
                               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

Страницы