Т

Таблица с оглавлением - см. Информационное множество.

Теорема Брукса(R.L.Brooks, 1941)
- Если G - связный граф, не являющийся полным, и степень графа [BigDelta](G) [geq] 3, то [chi] [leq] [BigDelta](G).
    Здесь [chi](G) - хроматическое число графа G.
Литература:[Харари], [Лекции]

Теорема Визинга(В.Г.Визинг, 1964)
- Каков бы ни был граф G, его хроматический индекс [chi]'(G) удовлетворяет неравенствам

[BigDelta](G) [leq] [chi]'(G) [leq] [BigDelta](G) + 1.

Литература:[Лекции], [Зыков], [Berge], [Bondy-Murty]

Теорема Грецша(H. Gr[otzsch, 1958)
- Каждый плоский граф G без треугольников (с [smomega](G) = 2) имеет хроматическое число [chi](G) [leq] 3.
Литература:[Bondy-Murty], [Lov\'{a}sz], [Лекции]

Теорема Дилворта(R.P.Dilvorth, 1950)
- Для любого частично упорядоченного множества

P = (S, [leq])
минимальное число цепей, покрывающих все точки S, равно мощности наибольшей антицепи, т.е. мощности множества несравнимых точек в P.
Литература:[Оре]

Теорема Дирака(G.A.Dirac, 1952)
- Если в графе с n (n [geq] 3) вершинами для любой вершины v выполняется неравенство deg (v) [geq] n/2, то G - гамильтонов граф.
Литература:[Лекции]

Теорема КЈнига(D.K[onig, 1931)
- Максимальное число попарно независимых единиц бинарной матрицы равно минимальному числу ее линий, содержащих все единицы матрицы.
Литература:[Харари], [Лекции]

Теорема Куратовского(K.Kuratowski, 1930)
- Граф планарен тогда и только тогда, когда он не содержит частичных графов, гомеоморфных K[_5] или K[_3,3].
    Ряд авторов называют эту теорему теоремой Понтрягина-Куратовского.
Литература:[Харари], [Лекции], [Зыков,а стр.245]

Теорема Кэли(A.Cayley, 1897)
- Существует ровно n[^n-2] различных помеченных деревьев с n вершинами.
Литература:[Лекции]

Теорема Менгера(K.Menger, 1927)
- Наименьшее число вершин, разделяющих две несмежные вершины a и b графа равно наибольшему числу попарно непересекающихся простых (a,b)-цепей этого графа.
    Теорема Менгера известна в литературе в нескольких вариантах.
Литература:[Харари], [Лекции]

Теорема Татта(W.T.Tutte, 1947)
- Граф G имеет совершенное паросочетание тогда и только тогда, когда число нечетных компонент
c[_1] (G
\ X) подграфа G \ X для любого подмножества вершин X [subseteq] V(G) удовлетворяет неравенству

c[_1](G \ X) [leq] |X|.

Литература:[Татт], [Lov\'{a}sz], [Bondy-Murty]

Теорема Турана(P.Tur\'{a}n, 1941)
- Пусть n и k - два целых числа (n [geq] k [geq] 1) и пусть G[_n,k] - граф, состоящий из k непересекающихся клик
из [leftceil]n
/ k[rightceil] и [leftfloor]n / k[rightfloor] вершин. Если G - граф с n вершинами и неплотностью [alpha](G) = k, то число ребер
|E(G)| [geq] | E(G[_n,k] )| и равенство имеет место тогда и только тогда, когда G изоморфен G[_n,k].
Литература:[Berge], [Lov\'{a}sz]

Теорема Форда и Фалкерсона(L.R.Ford, D.R.Fulkerson, 1955)
- Во всякой сети величина любого максимального потока равна пропускной способности минимального разреза.
Литература:[Берж]

Теорема Фрухта - см. Группа автоморфизмов графа.

Теорема Хивуда(P.J.Heawood, 1890)
- Для любого положительного целого числа n хроматическое число ориентируемой поверхности рода n определяется формулой

[Formula-15].

Литература:[Харари]

Теорема Холла(Ph.Hall, 1935)
- Семейство конечных множеств S[_1], S[_2] , ..., S[_m] обладает системой различных представителей тогда и только тогда, когда для всех k = 1, ..., m объединение любых k множеств этого семейства содержит по крайней мере k элементов.
Литература:[Харари]

Теорема Эйлера(L.Euler, 1736)
- Непустой связный граф эйлеров тогда и только тогда, когда граф не имеет вершин нечетной степени.
Литература:[Лекции], [Bondy-Murty], [Харари], [Lov\'{a}sz]

Терм(Term)
- правильно построенная формула над некоторым алфавитом [sigma], образованным из множества символов переменных V и символов r-арных функций [sigma][_r], где r [geq] 0 - арность функций (количество ее "аргументов").
    Если терм t имеет вид

f(t[_1], t[_2], ..., t[_r]),
где f [include] [sigma][_r], r > 0, то f называется внешним (корневым) символом терма t, а термы t[_1], t[_2], ..., t[_r] и их подтермы - подтермами терма t. Терм t - замкнутый, если в нем нет переменных, и линейный, если он не содержит двух вхождений одной и той же переменной.
     Терм t называется редуцируемым (относительно некоторой системы переписывания R), если существует такой терм s, отличный от t, что t [RightLeftArrow][_R] s, и нередуцируемым (или тупиковым) в противном случае. Термы t и s эквивалентны, если t [RightLeftArrow][_R] s или s [RightLeftArrow][_R] t.
     Если t [RightLeftArrow][_R] s и s нередуцируемый, то s называется нормальной формой терма t. Термы конвергентны, если их нормальные формы совпадают.
Литература:[Евстигнеев-Касьянов]

Тождественная группа графа(Identical group of a graph)
- группа автоморфизмов, состоящая из тождественного автоморфизма.
Литература:[Алгоритмы]

Толщина графа(Thickness of a graph)
- наименьшее число планарных частичных графов (подграфов в слабом смысле) графа G, объединение которых дает исходный граф G. Очевидно, что толщина планарного графа равна 1.
Литература:[Лекции]

Толщина тороидальная(Toroidal thickness)
- наименьшее число тороидальных частичных графов графа G, объединение которых дает исходный граф G.
Литература:[Уилсон]

Топологическая сортировка(Topological sorting)
- такая нумерация вершин бесконтурного графа, при которой номер начала дуги всегда меньше номера ее конца. Если нумерация такова, что номер начала дуги всегда больше номера ее конца, то говорят об обратной топологической сортировке.
Литература:[Евстигнеев]

Топологический граф(Topological graph)
- граф, размещенный в некотором пространстве без пересечения ребер; такими графами, например, являются плоский и тороидальный графы.
Литература:[Зыков]

S-топологический граф(S-topological graph)
- граф, размещенный на поверхности S (ориентированной или неориентированной) без пересечения ребер, см. Топологический граф.
Литература:[Зыков]

Топологическое представление (графа)(Topological representation of a graph)
- для данного графа G изоморфный ему расположенный в некотором пространстве топологический граф.
Литература:[Зыков]

Тороидальный граф(Toroidal graph)
- граф, который нельзя уложить на плоскости, но можно уложить на торе. Тороидальными являются, например, графы K[_5] , K[_3,3] , K[_7], K[_4,4].
Литература:[Харари], [Лекции]

Тотальная раскраска(Total colouring)
- одновременная раскраска вершин и ребер, при которой никакие два смежных или инцидентных элемента не окрашиваются в один цвет.
Литература:[Зыков], [Toft-Jensen]

Тотально сбалансированный гиперграф(Totally balanced hypergraph)
- гиперграф, в котором каждый цикл сбалансирован.
Литература:[Lov\'{a}sz]

Тотальный граф(Total graph)
- для данного графа G граф T(G), у которого множеством вершин является V(G) [cup] E(G) и две вершины в T(G) смежны, если они соседние (т.е. смежные или инцидентные) в графе G.
Литература:[Харари], [Лекции]

Точка(Point)
- 1) см. Вершина; 2) элемент частично упорядоченного множества.
Литература:[Лекции]

Точка сочленения графа(Articulation point, cut-vertex)
- вершина v графа G, при удалении которой граф G \ v имеет больше компонент связности,
чем исходный граф G.
Другие названия - Разделяющая вершина, Шарнир.
Литература:[Лекции], [Харари], [Оре], [Зыков]

Точка сочленения уграфа(Articulation point, cut-vertex)
- вершина, являющаяся начальной или конечной у некоторой линейной компоненты уграфа.
Литература:[Касьянов]

Точка Штейнера(Steiner's point)
- дополнительная вершина, вводимая в граф, моделирующий исходное множество точек на плоскости при решении Евклидовой задачи Штейнера.
Литература:[Лекции]

Транзитация - см. Транзитируемый граф.

Транзитивная группа графа(Transitive group of a graph)
- группа автоморфизмов, в которой для любой пары вершин существует автоморфизм, отображающий одну вершину в другую.
Литература:[Алгоритмы]

k-транзитивная группа графа(k-transitive group of a graph)
- группа автоморфизмов, в которой для любой пары упорядоченных наборов из k различных вершин существует автоморфизм, отображающий один из них в другой.
Литература:[Алгоритмы]

Транзитивная редукция орграфа(Transitive reduction of a directed graph)
- для данного орграфа G орграф с наименьшим числом дуг, транзитивное замыкание которого совпадает (изоморфно) с транзитивным замыканием исходного графа G.
Литература:[Свами-Тхуласираман]

Транзитивное замыкание орграфа(Transitive closure of a directed graph)
- для данного орграфа G орграф G[^*] с тем же множеством вершин, что и G, в котором дуга (v,w) существует тогда и только тогда, когда w достижима из v в G.
Литература:[Евстигнеев]

Транзитивный граф - то же, что и Граф вершинно-симметрический.

k-транзитивный граф(k-transitive graph)
- для натурального k граф, в котором имеются k-пути с корнем и для любых двух таких k-путей существует автоморфизм, отображающий один из этих путей на другой с переносом корней.
Литература:[Харари]

Транзитивный орграф(Transitive directed graph)
- орграф, у которого из существования дуг (u,v) и (v,w) вытекает существование дуги (u,w).
Литература:[Лекции]

Транзитивный турнир(Transitive tournament)
- турнир, у которого из существования дуг (u,v) и (v,w) вытекает существование дуги (u,w).
Литература:[Уилсон]

Транзитируемый граф(Transitivable graph)
- граф, ребра которого можно ориентировать так, чтобы получился граф частичного порядка; каждая такая ориентация называется транзитацией.
Литература:[Зыков]

Трансверсаль (семейства S)(Transversal (of family S))
- подмножество T элементов некоторого множества E такое, что для данного семейства S = (S[_1] , ..., S[_m]) подмножеств множества E существует биекция [phi]: T [rarr] {1,2, ..., m}, при которой для каждого t [include] T выполняется условие t [include] S[_phi(t)]. Трансверсаль называется частичной, если [phi] - инъективное отображение.
Другое название - Семейство различных представителей.
Литература:[Лекции]

Трансверсальное множество гиперграфа(Transversal set of a hypergraph)
- трансверсаль семейства ребер гиперграфа. Другими словами, подмножество T вершин гиперграфа называется Т.м.г., если для любого ребра e справедливо соотношение T [cap] e [neq] [zero].
Литература:[Лекции]

Транспортная сеть(Transportation network)
- орграф, в котором выделены две вершины - вход и выход сети и для каждой дуги определена пропускная способность.
Литература:[Кристофидес], [Свами-Тхуласираман]

Трехвалентный граф - то же, что и Кубический граф.

Треугольник(Triangle)
- цикл длины 3.
Литература:[Лекции]

Триангулированный граф(Triangulated graph, chordal graph)
- граф, ни один подграф (в сильном смысле) которого не является простым циклом длины l [geq] 4. Другими словами, в триангулированном графе для любого его простого цикла длины l [geq] 4 существует ребро, соединяющее две несоседние вершины этого цикла (хорда).
Другое название - хордальный граф.
Литература:[Лекции]

Тривиальное дерево - то же, что и Дерево вырожденное.

Тривиальный граф(Trivial graph)
- граф, состоящий из одной вершины.
Литература:[Свами-Тхуласираман]

Трудоемкость алгоритма - то же, что и Временная сложность.

Турнир(Tournament)
- орграф, превращающийся в полный неориентированный граф после удаления ориентации дуг. Этот класс графов получил свое название в связи со спортивными турнирами без ничьих, проводимых по круговой системе. Вершины турнира соответствуют участникам соревнований, а дуга (u,v) присутствует в орграфе, если участник u победил участника v.
Литература:[Лекции], [Харари]

Турнир транзитивный - см. Транзитивный турнир.

Тэта-граф(Theta-graph, [THETA]-graph)
- граф, содержащий две вершины степени 3, соединенные тремя простыми попарно непересекающимися цепями длины не менее двух. Каждый негамильтонов двусвязный граф содержит часть, гомеоморфную тэта-графу.
Литература:[Лекции]