Математическое моделирование на графах. Часть 1. Берцун В.Н. - 20 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

20 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
Теоретически можно проверить два графа G и G
1
с n вершинами
на изоморфизм, переставляя строки и соответствующие столбцы
матрицы смежности, например, графа G, пока она не превратится в
соответствующую матрицу графа G
1
[1]
. Если это не произойдет по-
сле n! перестановок, то графы неизоморфны. Однако практическое
использование такого алгоритма при компьютерном анализе мало-
эффективно для больших значений n.
Задачи распознавания изоморфизма графов, изоморфного вложе-
ния и изоморфного пересечения возникают, например, при автома-
тизации проектирования радиоэлектронной аппаратуры, анализе мо-
лекулярных структур химических соединений, разработке эффек-
тивных параллельных вычислительных алгоритмов [16].
1.6. Двудольные графы и их свойства
Множество вершин U ⊆ V называется вершинным покрытием
множества E, если каждое ребро графа G(V, E) инцидентно некото-
рой вершине из U. Очевидно, что все вершины связного графа V все-
гда образуют одно из вершинных покрытий. Наименьшее число
вершин в вершинных покрытиях графа G называется числом вер-
шинного покрытия α
0
, а наименьшее число ребер в реберных покры-
тиях определяет число реберного покрытия α
1
. Эти два числа явля-
ются инвариантами графа [16]. Например, α
0
(K
n
) = n – 1, α
1
(K
2n
) = n,
α
1
(K
2n+1
) = n + 1, α
1
(С
2n
) = n, α
1
(С
2n+1
) = n + 1. Для изоморфных гра-
фов на рис. 1.20 α
0
= 3, α
1
= 2, а для графов на рис. 1.21 α
0
= 3,
α
1
= 3.
Множество вершин (ребер) графа называется независимым, если
никакие две (два) из них не смежные. Максимальная мощность вер-
шин в независимом множестве вершин называется вершинным чис-
лом независимости (числом внутренней устойчивости) β
0
. Соответ-
ственно максимальная мощность ребер в независимом множестве
ребер называется реберным числом независимости β
1
. Например,
β
0
(K
n
) = 1, β
1
(K
2n
) = n, β
1
(K
2n+1
) = n – 1. Известно [16], что в связном
графе (n > 1) имеют место соотношения
α
0
+ β
0
= n, α
1
+ β
1
= n .

Страницы