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

 равны ст (b 1 ), ..., ст (b n ). Чтобы найти число всех
 ребер графа, сосчитаем их в каждой вершине. Оно
 равно степени этой вершины ст (bk ). Сложим все
 числа ст(bk). Тогда число всех ребер будет равно
 половине этой суммы, потому что каждое ребро мы
 сосчитаем дважды в тех вершинах, которые оно
 соединяет ■.
    Для орграфов также имеется подобное утвержде-
 ние. Назовем полустепенью исхода вершины х
 (обозначается cт(x)) число стрелок орграфа,
 имеющих вид (х, у); аналогично               полустепенью
 захода вершины х
 (обозначается ст(x)) назовем число стрелок орграфа
 вида (у, x): Отсюда сразу следует
    Теорема 2. Число стрелок орграфа равно сум-
же полустепеней исхода или сумме полустепеней
вахода его вершин.
    Пример 1. Пусть Ф1, ..., Ф т — филиалы ЦБС,
которые обмениваются литературой в процессе об-
служивания читателей. Подсчет обращаемой литера-
туры в сети несложно осуществить, если сформули-
ровать эту задачу на языке теории графов. Для этого
обозначим вершины графа Ф1, ..., Фт и соединим Фi и
Фj стрелкой в том случае, когда филиал Фi передал
книгу филиалу Ф j . Тогда количество переданных
книг будет равно числу стрелок построенного оргра-
фа, т. е., по теореме 2, сумме полустепеней исхода
(или захода) всех вершин графа. В нашем случае
полустепень исхода (захода) представляет собой коли-
чество книг, переданных (принятых) филиалом, соот-
ветствующим данной вершине. Таким образом, коли-
чество обращаемой литературы в ЦБС равно сумме
книг, передаваемых (или только
принимаемых) филиа-
лами.
    Познакомимся еще с одним
важным типом графов.
    Определение 3. Двудоль-
ным графом (или орграфом)
называется граф (орграф), вер-
шины которого можно разбить
на два непересекающихся мно-
жества так, что никакие две
вершины из одного и того же
множества не соединены реб-             Рис. 13. Двудольный
ром (или стрелкой) (рис. 13).                    граф




29