Дискретная математика. Кулаков Ю.В - 18 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

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

Страницы