М

Максимальное дерево(Maximal tree)
- максимальный граф исключения относительно семейства простых циклов; М.д. графа есть его каркас.
Литература:[Оре]

Максимальный граф исключения(Maximal exclusion graph)
- часть H некоторого графа такая, что никакой граф из семейства непустых графов {F[_i] } не является ее частью; H называется максимальным графом исключения для {F[_i] }, если он не является собственной частью другого графа исключения.
Литература:[Оре]

Максимальный поток - то же, что и Наибольший поток.

Максимальный сильно сингулярный граф(Maximal strongly singular graph)
- максимальный сингулярный граф, у которого никакая запрещенная составляющая (сумма некоторого числа запрещенных графов из заданного семейства), определяемая двумя добавляемыми к графу ребрами, не может быть ликвидирована удалением одного ребра.
Литература:[Оре]

Максимальный сингулярный граф(Maximal singular graph)
- максимальный граф H такой, что добавление одного ребра e к H порождает только одну запрещенную часть из заданного семейства запрещенных частей.
Литература:[Оре]

Маршрут(Sequence)
- чередующаяся последовательность

a = v[_0] , e[_1] , v[_1] , e[_2] , ... , v[_n][_-] [_1] , e[_n] , v[_n] = b
вершин и ребер графа такая, что e[_i] = (v[_i-1] ,v[_i] ), 1 [leq] i [leq] n. Говорят, что маршрут соединяет вершины
a и b - концы маршрута. Очевидно, что маршрут можно задать перечислением лишь его вершин
a = v[_0] , v[_1] , ... , v[_n] = b или его ребер e[_1] , e[_2] , ... , e[_n]. М. конечен, если число входящих в него ребер конечно, и бесконечен в противном случае. Бесконечный М., имеющий только одну концевую вершину (a или b), называется односторонне-бесконечным маршрутом; М. без концевых вершин называется двусторонне-бесконечным маршрутом.
См. Ориентированный маршрут,Цепь.
Литература:[Лекции], [Оре]

Маршрут бесконечный - см. Маршрут.

Маршрут двусторонне-бесконечный - см. Маршрут.

Маршрут длины n(Sequence of length n)
- маршрут, состоящий из n ребер.
Литература:[Лекции], [Оре]

Маршрут замкнутый - см. Замкнутый маршрут.

Маршрут конечный - см. Маршрут.

Маршрут неориентированный - то же, что и Маршрут.

Маршрут односторонне-бесконечный - см. Маршрут.

Маршрут ориентированный - см. Ориентированный маршрут.

Маршрут остовный - см. Остовный маршрут.

Маршрут открытый - см. Открытый маршрут.

Маршрут циклический - см. Циклический маршрут.

Маршрут Y-сводимый - см. Y-сводимый маршрут.

Матрица весов(Weight matrix)
- вариант матрицы смежности для взвешенного графа, представляет собой квадратную матрицу размером n [times] n (n - число вершин), (i,j)-й элемент которой равен весу ребра / дуги (v[_i] , v[_j]), если таковое имеется в графе; в противном случае (i,j)-й элемент полагается равным нулю или бесконечности в зависимости от решаемой задачи.
Литература:[Лекции]

Матрица вложенности контуров(Cycle embedding matrix)
- квадратная (0,1)-матрица размером c [times] c (c - число контуров в графе), (i,j)-й элемент которой равен 1, если контур C[_j] вложен в контур C[_i], т.е. если все вершины контура C[_j] принадлежат контуру C[_i], и равен 0 в противном случае.
Литература:[Евстигнеев]

Матрица достижимости(Reachibility matrix)
- квадратная (0,1)-матрица R(G) размером n [times] n (n - число вершин в G), (i,j)-й элемент r[_i][_j] которой равен 1, если в G существует путь из v[_i] в v[_j] (вершина v[_j] достижима из v[_i]), и равен 0 в противном случае.
См. Транзитивное замыкание.
Литература:[Харари], [Евстигнеев]

Матрица инцидентности((vertex-edge) incidence matrix)
- (0,1)-матрица I(G) размером n [times] m (n - число вершин, m - число ребер/дуг графа G), (i,j)-й элемент которой равен 1, если вершина v[_i] инцидентна ребру e[_j] в неориентированном графе или если v[_i] есть начало дуги e[_j], равен -1, если вершина v[_i] есть конец дуги e[_j] (только для орграфов), и равен 0 в остальных случаях.
Матрица инцидентности определяет граф с точностью до изоморфизма.
Литература:[Лекции]

Матрица Кирхгофа(Kirchhoff's matrix)
- квадратная (0,1)-матрица B(G) размером n [times] n (n - число вершин в G), (i,j)-й элемент b[_i][_j] которой равен -1, если вершины v[_i] и v[_j] смежны (i [neq] j), равен степени deg v[_i] вершины v[_i] для i = j и равен 0 в остальных случаях. Сумма элементов в каждой строке и в каждом столбце этой матрицы равна нулю.
Литература:[Лекции]

Матрица клик(Clique matrix)
- (0,1)-матрица C(G) размером [rho] [times] n ([rho] - число клик, n - число вершин в графе G), строки которой соответствуют кликам Q[_1] , ... , Q[_pho], а столбцы - вершинам и (i,j)-й элемент равен 1, если клика Q[_i] содержит вершину v[_j], и равен 0 в противном случае.
Литература:[Лекции]

Матрица контрадостижимостей(Reaching matrix)
- (0,1)-матрица Q(G), (i,j)-й элемент которой равен 1, если из вершины v[_j] можно достичь вершину v[_i], и равен 0 в противном случае.
Другое название - Матрица обратных достижимостей.
Литература:[Кристофидес]

Матрица коциклов(Cocyclic matrix)
- (0,1)-матрица, строки которой соответствуют коциклам (минимальным разрезам) графа, а столбцы - ребрам графа и (i,j)-й элемент равен 1, если ребро e[_j] принадлежит коциклу i, и равен 0 в противном случае.
Литература:[Харари]

Матрица обратных достижимостей - то же, что и Матрица контрадостижимостей.

Матрица обходов(Tournament matrix)
- матрица, определенная для орграфов; (i,j)-й элемент ее равен длине самого длинного пути из вершины v[_i] в вершину v[_j], если такой путь существует, и равен [infinity] в противном случае.
Эффективных алгоритмов для нахождения элементов матрицы обходов не существует.
Литература:[Харари]

Матрица ограниченных достижимостей(Bounded reachibility matrix)
- матрица достижимостей, полученная при ограничении длин путей некоторым числом.
Литература:[Кристофидес]

Матрица ограниченных контрадостижимостей(Bounded reaching matrix)
- матрица контрадостижимостей, полученная при ограничении длин путей некоторым числом.
Литература:[Кристофидес]

Матрица полустепеней захода(In-degree matrix)
- матрица, получаемая из матрицы смежности изменением знаков всех элементов на обратные и заменой i-го элемента главной диагонали на полустепень захода i-й вершины.
Литература:[Харари]

Матрица полустепеней исхода(Out-degree matrix)
- матрица, получаемая из матрицы смежности изменением знаков всех элементов на обратные и заменой i-го элемента главной диагонали на полустепень исхода i-й вершины. Матрица Кирхгофа.
Литература:[Харари]

Матрица разрезов(Cut-set matrix)
- (0,1)-матрица, строки которой соответствуют простым разрезам, столбцы - ребрам графа и (i,j)-й элемент равен 1, если ребро j входит в разрез i, и равен нулю в противном случае.
Литература:[Кристофидес], [Зыков]

Матрица смежности(Adjacency matrix, vertex incidence matrix)
- (0,1)-матрица A(G) размером n [times] n (n - число вершин в G), (i,j)-й элемент a[_i][_j] которой равен 1, если вершины v[_i] и v[_j] смежны, т.е. соединены дугой (или ребром) (v[_i] , v[_j]), и равен 0 в противном случае. Для неориентированного графа М.с. есть симметричная матрица с нулями на главной диагонали. В М.с. для мультиграфов и псевдографов (i,j)-й элемент равен числу ребер, соединяющих вершины v[_i] и v[_j] (при этом петля считается как два ребра).
М.с. определяет граф (орграф, мультиграф, псевдограф) с точностью до изоморфизма.
Литература:[Лекции]

Матрица смежности вершин - то же, что и Матрица смежности.

Матрица смежности приведенная - см. Приведенная матрица смежности.

Матрица смежности ребер(Edge incidency matrix)
- (0,1)-матрица, в которой и строки, и столбцы соответствуют ребрам, а (i,j)-й элемент равен 1, если ребра i и j имеют общую вершину, и равен 0 в противном случае.
Литература:[Оре]

Матрица фундаментальных разрезов(Fundamental cut-set matrix)
- матрица разрезов, ограниченная множеством фундаментальных разрезов.
Литература:[Кристофидес]

Матрица фундаментальных циклов(Fundamental cycle matrix)
- матрица циклов, ограниченная множеством фундаментальных циклов.
Литература:[Кристофидес]

Матрица циклов(Cycle matrix)
- (0,1)-матрица, строки которой соответствуют простым циклам графа, столбцы - ребрам графа и (i,j)-й элемент равен 1, если ребро e[_j] входит в цикл C[_i], и равен 0 в противном случае.
Литература:[Кристофидес]

Матрица цикломатическая - см. Цикломатическая матрица.

Матричная теорема о деревьях(Matrix-tree theorem)
- теорема, доказанная Кирхгофом в 1847 г. и определяющая в неявном виде число каркасов в связном графе:
Число каркасов в связном графе G порядка n [geq] 2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа B(G). Следствием этой теоремы является Теорема Кэли
о числе помеченных n-вершинных деревьев (равным n[^n-2]).
Литература:[Харари-Палмер]

Матроид(Matroid)
- комбинаторный объект, представляющий собой пару (E, [bbb]), где E - конечное непустое множество элементов матроида, а [bbb] - непустое множество его подмножеств (называемых базами), удовлетворяющее следующим двум условиям (аксиомы баз):
B1. Никакая из баз не содержится в другой базе.
B2. Если B[_1] и B[_2] - базы, то для любого элемента b [include] B[_1] существует такой элемент c [include] B[_2], что (B[_1] \ b) [cup] c - также база.
Существуют другие эквивалентные определения матроида, например, через семейства независимых множеств, через ранговую функцию, через циклы и т.д.
Понятие матроида является естественным обобщением понятия линейной зависимости и поэтому играет важную роль в комбинаторной теории.
Литература:[Лекции], [Липский], [Свами-Тхуласираман]}

Матроид бинарный - см. Бинарный матроид.

Матроид векторный(Vector matroid)
- матроид на множестве E векторов; независимыми множествами в нем являются все линейно независимые в E системы векторов и пустое множество.
Литература:[Лекции]

Матроид графа - то же, что и Циклический матроид.

Матроид графический - см. Графический матроид.

Матроид графовый - то же, что и Графический матроид.

Матроид двойственный(Dual matroid)
- для данного матроида M матроид M[^*], базами которого служат кобазы матроида M.
Литература:[Лекции]

Матроид кографический - см. Кографический матроид.

Матроид коциклический - см. Матроид разрезов.

Матроид коциклов графа - см. Матроид разрезов.

Матроид матричный(Matrix matroid)
- матроид на множестве столбцов некоторой матрицы.
Литература:[Лекции]

Матроид планарный - см. Планарный матроид.

Матроид разрезов(Cut-set matroid)
- матроид, двойственный матроиду циклов графа.
Литература:[Лекции]

Матроид свободный(Discrete matroid)
- матроид (E,{E}), единственной базой которого служит само множество E.
Литература:[Лекции]

Матроид циклический - см. Матроид циклов.

Матроид циклов(Cycle matroid)
- матроид, элементы которого суть ребра некоторого графа, а базы - каркасы этого графа; циклами матроида служат фундаментальные циклы графа.
Литература:[Лекции]

Медиана абсолютная - см. Абсолютная медиана.

Метка(Label)
- число, символ, слово в некотором алфавите, вектор и т.п., приписанные вершине (или ребру/дуге) графа и играющие различительную (идентифицирующую) роль. Разметка или приписывание меток есть отображение вида [phi]: V(G) [rarr] L, где L - множество меток. В отличие от нумерации здесь не требуется взаимной однозначности.
См. Помеченный граф.
Литература:[Лекции]

Минимально связный граф(Minimal connected graph)
- сильно связный орграф, утрачивающий это свойство после удаления любой дуги.
Литература:[Берж]

Минимальный поток(Minimal flow)
- поток наименьшей величины, удовлетворяющий нижним ограничениям на пропускную способность дуг.
Литература:[Евстигнеев]

Многовходовая зона(Multiinput zone)
- зона с двумя или более входными вершинами.
Литература:[Касьянов]

Многомерное дерево сортировки(Multidimensional search tree)
- структура данных на базе бинарного дерева сортировки для хранения многомерных данных.
Другое название - k - d - деревья.
Литература:[Евстигнеев-Касьянов]

Многомерное B-дерево(Multidimensional B-tree)
- структура данных на базе B-дерева для хранения многомерных данных.
Другое название - kB-деревья.
Литература:[Евстигнеев-Касьянов]

Многочлен деревьев графа(Tree polynom of a graph)
- сумма слов каркасов помеченного графа, где под словом каркаса понимается последовательность (как-то упорядоченная) всех символов, приписанных ребрам каркаса.
Литература:[Харари]

Многочлен хроматический - см. Хроматический многочлен.

Множество вершин внешне устойчивое - см. Внешне устойчивое множество вершин.

Множество вершин внутренне устойчивое - см. Внутренне устойчивое множество вершин.

Множество вершин всесмежное - то же, что и Доминирующее множество вершин.

Множество вершин доминирующее - см. Доминирующее множество вершин.

Множество вершин зависимое - см. Зависимое множество вершин.

Множество вершин замкнутое - см. Замкнутое множество вершин.

Множество вершин конезависимое - см. Конезависимое множество вершин.

Множество вершин накрывающее - см. Накрывающее множество вершин.

Множество вершин независимое - см. Независимое множество вершин.

Множество вершин отделяющее - см. Отделяющее множество вершин.

Множество вершин покрывающее - см. Покрывающее множество вершин.

Множество вершин полностью зависимое - см. Полностью зависимое множество вершин

Множество вершин разделяющее - см. Разделяющее множество вершин.

Множество вершин связанное - см. Связанное множество вершин.

Множество вершин субдоминирующее - см. Субдоминирующее множество вершин.

Множество ребер независимое - то же, что и Паросочетание.

Мост(Bridge)
- ребро графа, удаление которого увеличивает число компонент связности графа; мост является вырожденным блоком графа.
Другое название - Перешеек.
Литература:[Лекции], [Оре]

Моток(Skein)
- граф, состоящий из непересекающихся по ребрам простых циклов, имеющих только две общие вершины.
Литература:[Оре]

Мощность ребра - то же, что и Пропускная способность ребра.

Мультиграф(Multigraph)
- пара (V,E), где V - непустое множество вершин, а E - семейство подмножеств множества V [times] V (ребра); другими словами, мультиграф есть граф с кратными ребрами.
Литература:[Лекции]

Мультиграф мощности s(Multigraph of strength s)
- мультиграф, в котором любая пара вершин соединяется не более чем s ребрами.
Литература:[Харари-Палмер]

Мультиграф ориентированный - см. Ориентированный мультиграф.

Мультиграф раскрашенный - см. Раскрашенный мультиграф.