Контрольная работа ОДМиТА вариант 10
.pdf
|
x2x6 |
x4x6 |
x5x6 |
x2 |
1 |
|
|
x4 |
|
1 |
|
x5 |
|
|
1 |
x6 |
1 |
1 |
1 |
Удалению из матрицы подлежит строка х6 и все столбцы.
Из этого можно сформулировать окончательный вывод: наименьшее вершинное покрытие составляют вершины {х1, х3, х6} и число вершинного покрытия β0(G) = 3;
Найдем наибольшее паросочетание α1 (G) . Следуя алгоритму, первым можно исключить ребро x1x5 и смежные ему ребра x1x2, x1x4, x3x5, x5x6. Исключая следом ребро x2x6, из графа удаляются ребра x2x3, x4x6. Действуя таким образом, в искомое паросочетание на последнем этапе включается оставшееся ребро x3x4.
В итоге получаем, что в искомое покрытие включаются 3 ребра (на рисунке ребра, выделенные жирными линиями):
Число паросочетания α1 (G) = 3 .
Согласно Лемме 2 число реберного покрытия графа β1 (G) = 3 .
Найдем наименьшее доминирующее множество. Для этого построим матрицу смежности и дополним ее единицами по главной диагонали:
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1 |
1 |
1 |
|
1 |
1 |
|
x2 |
1 |
1 |
1 |
|
|
1 |
x3 |
|
1 |
1 |
1 |
1 |
|
x4 |
1 |
|
1 |
1 |
|
1 |
x5 |
1 |
|
1 |
|
1 |
1 |
x6 |
|
1 |
|
1 |
1 |
1 |
12
Вводим в искомое покрытие строку х1, так как она содержит наибольшее число единиц, вычеркиваем ее из матрицы и столбцы, которые она покрывает.
|
x3 |
x6 |
x2 |
1 |
1 |
x3 |
1 |
|
x4 |
1 |
1 |
x5 |
1 |
1 |
x6 |
|
1 |
Повторяя шаги алгоритма, вводим в искомое покрытие строку х2, так как она содержит наибольшее число единиц, вычеркиваем ее из матрицы и столбцы, которые она покрывает.
В результате получаем доминирующее множество вершин {х1, х2} и число доминирования графа μ (G) = 2 .
Найдем хроматическое и реберно–хроматическое числа графа. Согласно правилам раскраски вершин и ребер и алгоритму раскраски графа, сначала строим булеву матрицу, строки которой представляют собой независимые подмножества, а столбцы – вершины графа. Решаем задачу о кратчайшем покрытии.
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x1x3x6 |
1 |
|
1 |
|
|
1 |
x2x4x5 |
|
1 |
|
1 |
1 |
|
В результате получаем покрытие, представляющее собой совокупность независимых подмножеств П = {{х1х3х6},{х2х4х5}}.
Хроматическое число графа χ (G) = 2 ;
Реберно–хроматическое число графа χ E (G) = 3
13
Найдем цикломатическое и коцикломатическое числа графа. Для этого построим покрывающее дерево и подсчитаем число ветвей и число хорд.
Цикломатическое число γ(G) = 4;
Коцикломатическое число γ*(G) = 5.
14