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

               Рис. 15. Дерево и лес деревьев

    Определение 4. Деревом называется связный
граф, не имеющий циклов. Лесом называется мно-
жество, состоящее из неснольних деревьев.
    Например, на рис. 15 изображен лес, состоящий
из четырех деревьев. Деревья представляют простей-
ший тип графов, для которых получено много полез-
ных характеристик. Рассмотрим детальнее способ
построения деревьев. Для этого выберем какую-нибудь
вершину b0. Из нее проведем ребра в соседние вер-
шины b1, b2, ..., из них проведем ребра к их соседям b11,
b12, ..., b21, b22, и т. д. Первоначально выбранная
вершина bо называется корнем дерева. Поскольку в
дереве нет циклов, различные цепи, выходящие из
bо, будут изолированы друг от друга. Каждая цепь
дерева имеет последнее ребро с конечной вершиной,
из которой уже не выходит ни одного нового ребра.
На основании указанного процесса построения де-
ревьев нетрудно устанавливается
    Теорема 4. Лес, состоящий из т деревьев и
имеющий п вершин, содержит п — т ребер.
    Приведем пример одного из многочисленных при-
ложений понятия дерева.
   Пример 2. В библиотечной практике нашли при-
менение информационно-поисковые системы ручного
обращения, реализованные на перфокартах с краевой,
перфорацией. Процесс поиска на перфокартах можно
пре ь как дерево специального вида. Отверстия на
перфокартах дставит разбиты на группы (по 10
отверстий в каждой), которые выделены по тем или
иным признакам. Поэтому при поиске перфокарт по
первому признаку имеется 10 возможностей b0, b1 , ...,
b8, b9; по второму признаку при выполнимости
первого — еще 10 возможностей для               каждого
случая: b00 , b01,
                                                      31