Ч

Частичный граф - то же, что и Часть графа.

Часть графа(Subgraph)
- для графа G = (V,E) граф H = (V',E') такой, что V' [subseteq] V и E' [subseteq] E; другими словами, это граф, порождаемый ребрами (дугами) графа G. Частью графа являются цепь, цикл, каркас и т.д. Вместо термина Ч.г. часто используют термин подграф (в слабом смысле).
Литература:[Лекции]

Чередующаяся цепь(Alternating chain)
- пусть ребра графа разделены на два класса; тогда цепь называется Ч.ц., если она содержит попарно чередующиеся ребра из обоих классов.
Литература:[Берж]

Чередующийся цикл(Cyclic alternating chain)
- пусть ребра графа разделены на два класса; тогда цикл называется Ч.ц., если он содержит попарно чередующиеся ребра из обоих классов.
Литература:[Оре]

Четный граф(Even graph)
- 1) для разбиения множества вершин V(G) на три множества S, T и U (так называемая G-тройка (S,T,U)), целочисленной функции f: V(G) [rarr] Z и компоненты связности C индуцированного подграфа G[U] определим индекс четности

[Formula-17]

где [lambda](T,b) - число ребер, соединяющих вершину b с вершинами множества T. Граф C называется четным тогда и только тогда, когда I(C) - четно.
2) граф с четным числом вершин.
     Для функции f, тождественно равной единице, 1) и 2) совпадают.
Литература:[Татт]

Четный подграф - см. Четный граф.

Число ахроматическое - см. Ахроматическое число.

Число Бераха(Beraha number)
- для натурального числа n это число B[_n] = 2 + 2cos(2[pi] / n). Ч.Б. порядка n связано с гипотезой Бераха:
     Верно ли, что для любого [epsilon] > 0 существует плоская триангуляция G такая, что хроматический полином
P(G, [lambda]) имеет корень [lambda][_0], лежащий в интервале B[_n] - [epsilon] < [lambda] [_0] < B[_n] + [epsilon]?
     Первыми такими числами являются 4, 0, 1, 2, [tau][^2], 3, ..., где [tau] = (1 + [sqrt from 5])/2 - золотое отношение.
Литература:[Toft-Jensen]

Число Бетти - то же, что и Цикломатическое число.

Число вершинного покрытия(Point-covering number)
- число вершин в наименьшем вершинном покрытии графа.
Литература:[Лекции]

Число вершинной связности(Vertex-connectivity number)
- наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу.
Литература:[Лекции]

Число внешнего разделения(Outseparation number)
- число s[_0](v), определяемое для вершины v по формуле

[Formula-18]
где r(w) - вес пути длины d(v,w).
Литература:[Кристофидес]

Число внешней устойчивости - то же, что и Число доминирования.

Число внутреннего разделения(Inseparation number)
- число s[_t](v), определяемое для вершины v по формуле

[Formula-19]
где r(w) - вес пути длины d(w,v).
Литература:[Кристофидес]

Число внутренней устойчивости - то же, что и Число независимости.

Число выбора - то же, что и Число предписанное хроматическое.

Число гармоническое хроматическое(Harmonious chromatic number)
- наименьшее целое k такое, что существует гармоническая k-раскраска, т.е. раскраска вершин k цветами такая, что смежные вершины получают разные цвета и для всех i, j, 1 [leq] i < j [leq] k, существует не более одного ребра с концами, окрашенными цветами i и j. Это число было введено Франком, Харари, Плансолтом в 1982г.
Литература:[Toft-Jensen]

Число Гранди(Grundy number)
- раскраской Гранди порядка k графа G называется k-раскраска вершин цветами {1,2, ..., k} такая, что для любой вершины x ее цвет c(x) есть минимальное целое число, не использованное на ее соседях. Ч.Г. Г(G) - это наибольшее k, для которого G имеет раскраску Гранди порядка k. Известно, что

.[chi](G) [leq] Г(G) [leq] [Psi](G),

где [chi](G) и [Psi](G) - хроматическое и ахроматическое числа.
Литература:[Toft-Jensen]

Число доминирования(Dominance number)
- наименьшая мощность доминирующего множества в графе.
Литература:[Кристофидес]

Число звездное хроматическое(Star chromatic number)
- для (k,d)-раскраски графа G, под которой подразумевается такая функция [phi]: V(G) [rarr] {1,2, ..., k}, что
d [leq] | [phi] (u) - [phi](v) | [leq] k-d для каждого ребра (u,v) [include] E(G), число

.[chi][^*] (G) = inf{k/d: G имеет (k,d)-раскраску}.

Литература:[Toft-Jensen]

Число игровое хроматическое(Game chromatic number)
- пусть имеются граф G, множество цветов {1,2, ..., k} и два игрока A и B, которые делают свои ходы поочередно. Ход состоит в выборе неокрашенной вершины v [include] V(G) и в окрашивании ее в цвет, отличный от цветов уже окрашенных ее соседей из N[_G](v). Игра заканчивается и A объявляется победителем, если после |V(G)| ходов G k-раскрашиваем. Игра заканчивается и B объявляется победителем, если при некотором ходе выбранная вершина не может быть раскрашена одним из цветов {1, 2, ..., k}. Игровым хроматическим
числом [chi][_g](G) называется такое наименьшее k, для которого игрок A имеет выигрышную стратегию.
Известно, что

.[chi](G) [leq] [chi] [_g](G) [leq] |V(G)|,

где [chi](G) - хроматическое число. Если G - плоский граф, то

7 [leq] [chi][_g](G) [leq] 33.

Литература:[Toft-Jensen]

Число кликового покрытия(Clique-covering number)
- наименьшее число клик, покрывающих вершины графа.
Литература:[Лекции]

Число кликовое - см. Кликовое число.

Число кохроматическое(Cochromatic number)
- число z(G), равное минимальному числу подмножеств, на которые можно разбить V(G) так, что каждое подмножество индуцирует либо независимое множество вершин, либо полный граф.
Литература:[Toft-Jensen]

Число независимости(Independence number)
- число вершин в наибольшем независимом множестве графа.
Другие названия - Число внутренней устойчивости, Неплотность.
Литература:[Лекции]

Число независимости вершинное - то же, что и Число независимости.

Число независимости реберное(Line-independence number)
- наибольшее число ребер в независимом множестве ребер.
Литература:[Харари]

Число несоответствия нумерации - то же, что и Глубина нумерации.

Число один-хроматическое(One-chromatic number)
- (обозначение [chi][_1](G)) для поверхности S наибольшее хроматическое число [chi](G) графов, допускающих 1-вложение в поверхность S, где под 1-вложением понимается такое вложение в S, что любое ребро пересекается не более чем с одним другим ребром.
Литература:[Toft-Jensen]

Число паросочетания(Matching number)
- число ребер в наибольшем паросочетании.
Литература:[Лекции]

Число пересечений(Intersection number)
- для графа G минимальная из мощностей таких множеств S, что G есть граф пересечений на S.
Литература:[Харари]

Число подхроматическое(Subchromatic number)
- (обозначение [chi][_s](G)) наименьшее целое k такое, что вершины графа могут быть разбиты на k V[_1] , V[_2] , ..., V[_k] такие, что каждый индуцированный подграф G[V[_i]] есть непересекающееся объединение полных графов.
Ч.п. было введено в 1985 году Мынхардтом и Броере.
Литература:[Toft-Jensen]

Число покрытия - то же, что и Число вершинного покрытия.

Число предписанное хроматическое(List chromatic number)
- идея приписать каждой вершине v [include] V(G) список L(v) с тем, чтобы цвет для вершины v при раскраске вершин графа G избирался из списка L(v), принадлежит Визингу (1976) и Эрдешу, Рабину и Тейлору (1979). Предписанное хроматическое число [chi][_L](G) графа G есть наименьшее k такое, что при любом приписывании списков L(v) мощности |L(v)| [geq] k для каждой вершины v [include] V(G) возможно построить вершинную раскраску G, выбирая цвета из списков.
Литература:[Toft-Jensen]

Число Рамсея(Ramsey number)
- наименьшее целое число r(m,n), для которого каждый граф с r(m,n) вершинами содержит K[_m] или [K^~][_n].
Литература:[Харари]

Число Рамсея реберное(Ramsey edge number)
- наименьшее натуральное число r[_1](m,n) такое, что для любого графа G с r[_1](m,n) вершинами его реберный граф L(G) содержит K[_m] или дополнение [L^~](G) содержит K[_n].
Литература:[Харари]

Число раскрасок - см. Хроматическая функция.

Число реберного покрытия(Line-covering number)
- число ребер в наименьшем реберном покрытии графа.
Литература:[Лекции]

Число реберное хроматическое - то же, что и Хроматический индекс.

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

Число связности - то же, что и Число вершинной связности.

Число симметрии графа(Graph symmetry number)
- порядок группы графа.
Литература:[Алгоритмы]

Число симметрии дерева(Tree symmetry number)
- порядок группы дерева.
Литература:[Евстигнеев-Касьянов]

Число скрещиваний(Crossing number)
- наименьшее число пересечений (двух ребер), получаемых при изображении графа на плоскости; Ч.с. планарного графа равно нулю.
Литература:[Лекции]

Число Турана(Turan number)
- (обозначение T(n,k,t)) наименьшее число t-подмножеств n-элементного множества X таких, что любое k-подмножество из X содержит по крайней мере одно из t-подмножеств.
Литература:[Оре], [Toft-Jensen]

Число Хадвигера(Hadwiger number)
- для графа G наибольший порядок полного графа, на который стягивается граф G.
Литература:[Лекции]

Число Хивуда(Heawood number)
- число

[Formula-20]

где [epsilon] ([epsilon] [leq] 2) - эйлерова характеристика.
Литература:[Зыков,а], [Харари], [Лекции], [Toft-Jensen]

Число хроматическое - см. Хроматическое число.

Число циклическое хроматическое(Cyclic chromatic number)
- (обозначение [chi][_c](G)) для 2-связного плоского графа G минимальное число цветов при такой раскраске вершин, что граница каждой грани содержит вершины разных цветов. Ч.ц.х. было введено в 1969 г. Оре и Пламмером.
Литература:[Toft-Jensen]

Число цикломатическое - см. Цикломатическое число.