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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

16
Основные понятия и определения
Множество вершин графа называется независимым (внутренне
устойчивым), если никакие две вершины из этого множества несмежны.
Независимое множество вершин называется максимальным, если оно не
является собственным подмножеством некоторого другого независимого
множества. Наибольшее по мощности из максимальных независимых
множеств называется наибольшим. Число вершин в наибольшем
независимом множестве графа
G называется числом независимости
(числом внутренней устойчивости, неплотностью) и обозначается через
0
α
(G).
На рис.6 показан граф G, у которого число независимости
0
α
(G) = 4.
Множества вершин {v
1
, v
2
, v
3
, v
7
}; {v
1
, v
2
, v
3
, v
8
};{v
2
, v
3
, v
5
, v
7
} и {v
2
, v
3
, v
5
, v
8
}
являются наибольшими независимыми множествами. Множество вершин
{v
4
, v
7
} максимальным независимым множеством, но не наибольшим.
Рис. 6 Граф G с числом независимости, равным четырем вершинам реберного графа
L(G), т. е.
1
α
(G) =
0
α
[L(G)].
Произвольное подмножество попарно несмежных ребер графа
называется паросочетанием (независимым множеством ребер).
Паросочетание графа G называется максимальным оно не содержится в
паросочетании с большим числом ребер. Паросочетание является
наибольшим, если число ребер в нем наибольшее среди всех
v
1
v
2
v
3
v
4
v
6
v
5
v
8
v
7 
                        Основные понятия и определения
       Множество вершин графа называется независимым (внутренне
устойчивым), если никакие две вершины из этого множества несмежны.
Независимое множество вершин называется максимальным, если оно не
является собственным подмножеством некоторого другого независимого
множества. Наибольшее по мощности из максимальных независимых
множеств     называется      наибольшим.              Число     вершин   в   наибольшем
независимом множестве графа G называется числом независимости
(числом внутренней устойчивости, неплотностью) и обозначается через
α 0 (G).

       На рис.6 показан граф G, у которого число независимости α 0 (G) = 4.
Множества вершин {v1, v2, v3, v7}; {v1, v2, v3, v8};{v2, v3, v5, v7} и {v2, v3, v5, v8}
являются наибольшими независимыми множествами. Множество вершин
{v4, v7} максимальным независимым множеством, но не наибольшим.
                                            v2
                             v1
                                                           v3


                                       v4                           v8

                              v5                      v6
                                                                    v7


  Рис. 6 Граф G с числом независимости, равным четырем вершинам реберного графа
                             L(G), т. е. α1 (G) = α 0 [L(G)].
       Произвольное подмножество попарно несмежных ребер графа
называется      паросочетанием          (независимым              множеством     ребер).
Паросочетание графа G называется максимальным оно не содержится в
паросочетании с большим числом ребер. Паросочетание является
наибольшим,      если    число     ребер          в    нем      наибольшее   среди   всех




                                             16

Страницы