Математические методы в библиотечной работе. Елизаров А.М - 30 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Отметим, что в двудольном
графе совсем не обязательно каждая
вершина из одного множества
соединена с каждой вершиной
другого множества; если же это
так, то он называется полным
двудольным графом. Если одно
множество вершин состоит из т
элементов, а другое — из п эле-
Рис. 14. Цепь и цикл ментов, то нетрудно проверяется
следующая
Теорема 3. Полный двудоль-
ный граф
с n + m вершинами имеет n m ребер.
С двудольными орграфами мы сталкиваемся при
интерпретации бинарного отношения R, заданного на
декартовом произведении двух множеств А X В. При
этом элементы множеств А и В обозначают вершины
графа, а стрелки, соединяющие эти вершины» прово-
дятся тогда, когда выполнено отношение R между
соответствующими элементами. Например, отношение
R
2
из примера 2 п. 1 характеризует читаемость чита-
телями из множества А литературы, перечисленной
в множестве В. Поэтому отношение R
2
легко пред-
ставить двудольным графом.
Цепью в данном графе с началом b
0
и концом b
п
называется последовательность ребер {b
0
, b
1
}, {b
1
, b
2
},
... , {b
n-1
, b
n
}, в которой все вершины b
0
, b
1
..., b
n
различны (кроме, быть может, b
0
=b
n
). Цепь, у которой
начало и конец совпадают, т. е. b
0
= b
n
, называется
циклом (рис. 14).
Например, {b
0
, b
1
}, {b
1
, b
2
}, {b
2
, b
4
} представляет
собой цепь с началом в вершине b
о
и концом в вер-
шине b
4
. Последовательность ребер {b
о
, b
1
}, {b
1
, b
3
}, {b
3
,
b
2
}, {b
2
, b
4
}, {b
4
, b
0
} является циклом.
Аналогичные понятия определяются и для оргра-
фов, например, орцепью называется последователь-
ность стрелок (b
0
, b
1
), (b
1
, b
2
), ..., (b
n-1
, b
n
) с раз-
личными вершинами.
С помощью введенных выше понятий можно оха-
рактеризовать свойство графа и орграфа состоять из
одного куска. Граф называется связным, если любые
две его вершины можно соединить цепью. Познако-
мимся с одним из наиболее распространенных типов
связанных грав,
vbvмимся с одним из наиболее распространенных типов
связных графов, часто используемым в приложениях.
30
связных графов, часто используемым в приложениях. 
                         Отметим, что в двудольном
                     графе совсем не обязательно каждая
                     вершина из одного множества
                     соединена с каждой вершиной
                     другого множества; если же это
                     так, то он называется полным
                     двудольным графом. Если одно
                     множество вершин состоит из т
                     элементов, а другое — из п эле-
Рис. 14. Цепь и цикл ментов, то нетрудно проверяется
                       следующая
                    Теорема 3. Полный двудоль-
ный граф с n + m вершинами имеет n m ребер.
     С двудольными орграфами мы сталкиваемся при
интерпретации бинарного отношения R, заданного на
декартовом произведении двух множеств А X В. При
этом элементы множеств А и В обозначают вершины
графа, а стрелки, соединяющие эти вершины» прово-
дятся тогда, когда выполнено отношение R между
соответствующими элементами. Например, отношение
R2 из примера 2 п. 1 характеризует читаемость чита-
телями из множества А литературы, перечисленной
в множестве В. Поэтому отношение R2 легко пред-
ставить двудольным графом.
     Цепью в данном графе с началом b0 и концом bп
называется последовательность ребер {b0, b1}, {b 1 , b2},
 ... , {bn-1, bn}, в которой все вершины b0, b1 ..., bn
различны (кроме, быть может, b0 =bn). Цепь, у которой
начало и конец совпадают, т. е. b 0 = b n , называется
циклом (рис. 14).
     Например, {b0, b1}, {b1, b2}, {b2, b4} представляет
собой цепь с началом в вершине bо и концом в вер-
шине b4. Последовательность ребер {bо, b1}, {b1 , b3}, {b3,
b2}, {b2, b4}, {b4, b0} является циклом.
     Аналогичные понятия определяются и для оргра-
фов, например, орцепью называется последователь-
ность стрелок (b0, b1), (b1 , b2), ..., (bn-1, bn) с раз-
личными вершинами.
     С помощью введенных выше понятий можно оха-
рактеризовать свойство графа и орграфа состоять из
одного куска. Граф называется связным, если любые
две его вершины можно соединить цепью. Познако-
мимся с одним из наиболее распространенных типов
связанных грав,
vbvмимся с одним из наиболее распространенных типов
связных графов, часто используемым в приложениях.
связных графов, часто используемым в приложениях.

30

Страницы