Дискретная математика. Громов Ю.Ю - 23 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

23
i-й строке – слово µ
i
, определяемое S-отношением, а значение её произ-
вольного элемента q
ij
определяется выражением:
q
ij
=
µ∈
.случаепротивномв0
,если,1
ij
m
Например, 3-отношение в множестве M = {а, и, о, р, с, ы}, определяю-
щее слова µ
1
= {с, о, р}, µ
2
= {р, и, с}, µ
3
= {с, ы, р}, µ
4
= {о, с, а}, с помощью
матрицы инцидентности Q можно задать следующим образом:
а и о р с ы
0 0 1 1 1 0
µ
1
Q = 0 1 0 1 1 0
µ
2
.
0 0 0 1 1 1
µ
3
1 0 1 0 1 0
µ
4
Модельным графом (мографом) называется граф, в котором верши-
ны соответствуют буквам, а каждой его вершине сопоставляется множе-
ство идентификаторов слов, в которые входит соответствующая буква.
Процесс сопоставления каждой букве множества идентификаторов слов
будем называть моделизацией графа. Две вершины графа, имеющие хотя
бы один общий идентификатор, называются смежными и соединяются
ребром (неориентированной дугой).
Модельный граф, изображённый на рис. 11, представляет рассматри-
ваемое в качестве примера 3-отношение в множестве M = {а, и, о, р, с, ы}.
Гиперграфом называется граф, вершинам которого сопоставлены
буквы, а кругами Эйлера заданы слова, определяемые S-отношением.
Геометрическая интерпретация гиперграфа, соответствующего приве-
дённому выше мографу, представлена на рис. 12.
Граф G = 〈V, U〉 называется двудольным, если его носитель V разбит
на непересекающиеся подмножества V
+
и V
−
и начало каждой дуги из
множества U принадлежит подмножеству V
+
, а конец − подмножеству V
−
.
{µ
1
, µ
2
, µ
3
, µ
4
}
{
µ
2
}
{
µ
3
}
{
µ
4
}
{µ
1
, µ
2
, µ
3
}
{µ
1
, µ
4
}
Рис. 11
с
и
ы
а
р
о
с
и
ы
а
р
о
Рис. 12
µ
2
µ
1
µ
3
µ
4

Страницы