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

самых различных разделах математики и техники,
физики и биологии, кибернетики и библиотековедения.
Дадим строгие определения.
     Определение 1. Графом Г называется пара
<В (Г), Р(Г)>, где В (Г) — непустое конечное множе-
ство элементов, называемых вершинами, а Р(Г) —
конечное множество пар элементов из В (Г) (не
обязательно различных), называемых ребрами.
Обычно говорят, что ребро {х, у} соединяет вершины
х и у. Ребро {х, х}, соединяющее вершину х с ней
самой, называется петлей. Отметим, что в графах
допускается несколько ребер, соединяющих одну и
ту же пару вершин.
     Например, на рис. 12 изображен граф, у которого
В ( Г ) = { b 1 , b 2 , b 3 , b 4 } , а м н о ж е с т в о р е б е р Р ( Г ) состоит из
пар {b1 , B2}, {b1, b3}, {b 1 , b4}, {b3,, b3}, {b2, b4}, {b2, b4), {b3, b4). В
этом графе ребро {b3, b3} является петлей, а ребро {b2,
b4} проведено дважды.
     Заметим, что в определении графа в качестве ребер
выбирались неупорядоченные (!) пары вершин. Взяв
вместо неупорядоченных пар упорядоченные, мы при-
дем к понятию ориентированного графа.
     Определение 2. Ориентированным графом
(или кратко, орграфом) называется пара <В(Г),
С (Г)>, где В (Г)—непустое конечное множестве эле-
ментов, называемых вершинами, а С(Г) — конечное
множество упорядоченных пар элементов из В (Г) (не
обязательно различных), называемых стрелками.
     Обычно говорят, что (х, у) является стрелкой из
вершины х в вершину у. Заметим, что стрелки (x-, у)
и (у, х) различны. Так, на рис. 12 изображен орграф со
стрелками (b1, b2), (b1, b3), (b2, b1), (b2, b3) и (b2, b2).
   При изучении графов оказываются полезными
числовые характеристики, связывающие множества
вершин и ребер (или стрелок). Назовем степенью
вершины х (обозначается ст (х)) в графе число ребер,
соединенных с этой вершиной. Если в вершине графа
есть петля, то ребро, образующее эту петлю, под-
считывается дважды. Между числом ребер и степе-
нями вершин графа существует простое соотношение.
   Теорема 1. Число ребер графа равно половине
суммы степеней его вершин.
   Доказательство. Пусть дан граф Г с верши-
нами b1, ..., bп, степени которых соответственно
28