Б


База матроида(Base of a matroid)
- максимальное по включению независимое множество матроида.
Литература:[Лекции], [Липский]}

База орграфа(Base of a directed graph)
- подмножество B вершин орграфа G = (V,E), удовлетворяющее условиям: (1) вершины базы не достижимы одна из другой; (2) любая вершина из V\B достижима из какой-либо вершины базы. См. также Антибаза, 1-база.
Литература:[Берж]

1-база(1-base)
- такой минимальный набор S попарно несмежных вершин, что любая вершина орграфа или принадлежит S или смежна с некоторой вершиной множества S. Каждый орграф имеет вершинную базу, но не каждый имеет 1-базу; однако каждый бесконтурный орграф имеет 1-базу.
Литература:[Харари]

Базис коциклов(Cocycle basis)
- базис пространства коциклов графа, состоящий только из коциклов. Мощность базиса коциклов пространства коциклов графа называется коциклическим рангом. См. Разрез, Кограница.
Литература:[Харари]

Базис циклов(Cycle basis)
- базис пространства циклов графа, состоящий только из простых циклов. Б.ц. является максимальным набором независимых простых циклов графа или минимальным набором простых циклов, от которых зависят все циклы. Мощность базиса циклов пространства циклов графа называется циклическим рангом графа. См. также Фундаментальные циклы.
Литература:[Харари]

Базисная нумерация(Basic numbering)
- нумерация вершин графа, основанная на поиске в глубину. К базисным нумерациям относятся прямая нумерация (или M-нумерация), обратная нумерация (или N-нумерация) Для фиксированного обхода графа в глубину прямая нумерация определяется порядком первого попадания в вершины, а обратная - порядком, обратным порядку возврата из вершин.
Литература:[Евстигнеев], [Евстигнеев-Касьянов], [Касьянов]

Базисное множество циклов(Basic cycle set)
- множество всех m - n + 1 базисных циклов графа G относительно каркаса T. Любой цикл графа G может быть выражен в виде кольцевой суммы базисных циклов. Другое название - множество фундаментальных циклов.
Литература:[Берж]

Базисный блок - то же, что и линейный участок.

Базисный цикл(Basic cycle)
- цикл, образуемый добавлением хорды графа к каркасу T, относительно которого определена данная хорда. Особенностью базисного цикла является то, что он содержит только одну хорду и эта хорда не принадлежит более никакому базисному циклу относительно T.
Другое название - фундаментальный цикл.
Литература:[Берж]

Баланс вершины(Balance of a vertex)
- корневой баланс вершины, рассматриваемой как корень соответствующего поддерева. Б.в. служит характеристикой локальной сбалансированности дерева сортировки; ближайшая к листьям вершина с нарушенным балансом определяет место проведения восстанавливающих структуру дерева преобразований.
Литература:[Рейнгольд-Нивергельт-Део], [Евстигнеев]

Баланс корневой - см. Корневой баланс.

Балансированное по весу дерево - то же, что и BB-дерево.

Балансированное по высоте дерево - то же, что и АВЛ-дерево.

Бездефицитное множество вершин - см. Дефицит.

Бектрекинг - см. Поиск в глубину.

Бесконечная грань плоского графа(Unbounded face)
- единственная неограниченная грань плоского графа. Другое название - внешняя грань.
Литература:[Харари], [Лекции]

Бесконечный граф(Infinite graph)
- граф с бесконечным числом вершин или иногда граф с бесконечным числом ребер, т.е. граф с бесконечным числом изолированных вершин считается конечным.
Литература:[Берж]

Бесконтурный орграф(Acyclic graph, DAG)
- орграф, не содержащий контуров, но возможно имеющий циклы (см. цикл в орграфе). В англоязычной литературе встречается в виде аббревиатуры DAG от directed acyclic graph. Отсюда другое название - ациклический граф.
Литература:[Евстигнеев], [Липский]

Бивершина(Binode)
- для фиксированных базисных нумераций M и N такая вершина v, что для любого индекса i < N(v) она принадлежит N-области N[i]. Каждой бикомпоненте графа соответствует в заданной N-нумерации ровно одна бивершина - та из вершин бикомпоненты, которая имеет наименьший N-номер.
Литература:[Касьянов], [Евстигнеев]

Биграф - то же, что и двудольный граф.

Бикомпонента(Strongly connected component)
- максимальный по включению вершин сильно связный подграф орграфа. Другие названия - сильная компонента, компонента сильной связности.
Литература:[Зыков,а], [Евстигнеев], [Касьянов]

Бинарная вершина(Binary vertex)
- вершина с двумя потомками в бинарном дереве. См. Унарная вершина.
Литература:[Евстигнеев]

Бинарное дерево(Binary tree)
- ордерево, растущее из корня, причем из каждой вершины исходит не более двух дуг, помеченных как правая или левая дуга. Другими словами, возможны следующие комбинации: выходят правая и левая дуги, выходит одна правая дуга, выходит одна левая дуга, нет выходящих дуг.
Другое название - двоичное дерево. Иногда под Б.д. просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. m-арное дерево.
Литература:[Кнут], [Евстигнеев], [Евстигнеев-Касьянов], [Касьянов-Поттосин]

Бинарное дерево сортировки(Binary sorting tree)
- дерево сортировки на базе бинарного дерева. Б.д.с. обладает следующим свойством: слово, хранящееся в вершине v, больше любого слова в левом поддереве вершины v и меньше любого слова из правого поддерева вершины v.
Литература:[Кнут], [Евстигнеев]

Бинарное отношение (на множестве M)(Binary relation)
- набор упорядоченных пар из элементов множества M. Наиболее удачный способ представления бинарного отношения R на множестве M - представление с помощью орграфа, вершины которого суть элементы множества M, а дуги - упорядоченные пары элементов, определяющие отношение R.
Литература:[Лекции]

Бинарное отношение эквивалентности - то же, что и отношение эквивалентности.

Бинарный матроид(Binary matroid)
- матроид, представимый над полем GF(2) целых чисел по (mod2). Бинарными являются графический матроид, циклический матроид и матроид разрезов графа.
Литература:[Лекции]

Бисвязные вершины(Mutually connected vertices)
- такие вершины a и b в орграфе, что существуют пути P(a,b) из a в b и Q(b,a) из b в a.
Другие названия - взаимно связанные и сильно связанные.
Литература:[Оре]

Бисвязный орграф - то же, что и сильно связный орграф.

Бистохастическая матрица(Bistochastic matrix, doubly stochastic matrix)
- квадратная матрица с действительными неотрицательными элементами, у которой сумма элементов в каждой строке и каждом столбце равна 1.
Литература:[Липский], [Lov\'{a}sz]

Бихроматический гиперграф(Bichromatic hypergraph)
- гиперграф, хроматическое число которого не превосходит 2. Другими словами, гиперграф, вершины которого раскрашены двумя цветами так, что любое гиперребро не является одноцветным. В отличие от графов для гиперграфов известны лишь достаточные условия бихроматичности.
Литература:[Лекции]

Бихроматический граф(Bichromatic graph)
- граф с хроматическим числом, равным 2. К бихроматическим графам относятся деревья и двудольные графы.
Литература:[Харари], [Лекции]

Бицентр(Bicentre, bicenter)
- множество центральных вершин графа, содержащее ровно две вершины. См. Центр, Бицентральное дерево.
Литература:[Берж], [Харари]

Бицентральное дерево(Bicentre (bicenter) tree)
- дерево, центр которого состоит из двух смежных вершин.
Литература:[Харари]

Блок графа(Block of a graph)
- связный, непустой, не имеющий собственных точек сочленения максимальный подграф неориентированного графа.
Другое название - компонента двусвязности.
Литература:[Харари], [Лекции], [Оре], [Ахо-Хопкрофт-Ульман]

Брат вершины v(Brother of a vertex v)
- вершина w ордерева, имеющая того же предка (отца), что и v.
Литература:[Евстигнеев]

Братское дерево(Brother tree)
- бинарное дерево, у которого все висячие вершины находятся на одном и том же уровне и каждая вершина x с одним потомком имеет брата [beta](x) с двумя потомками. Другое название - HB-дерево.
Литература:[Евстигнеев], [Евстигнеев-Касьянов]

1-2-братское дерево(1-2 brother tree)
- бинарное дерево, у которого все висячие вершины находятся на одном уровне и каждая вершина с одним потомком (сыном) имеет брата с двумя сыновьями.
Литература:[Евстигнеев-Касьянов]