[Править] к

• Клетка — регулярный граф наименьшего обхвата для заданной степени вершин.

• Клика — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом.

  • Кликовое число (англ. Clique number) — число (G) вершин в наибольшей клике. Другие названия — густота, плотность.

  • Максимальная клика — клика с максимально возможным числом вершин среди клик графа.

• Конструктивное перечисление графов — получение полного списка графов в заданном классе.

• Компонента связности графа — некоторое подмножество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

• Компонента сильной связности графа, слой — максимальное множество вершин ориентированного графа такое, что для любых двух вершин из этого множества существует путь как из первой во вторую, так и из второй в первую.

• Контур — замкнутый путь в орграфе.

• Корень дерева — выбранная вершина дерева; в орграфе — вершина с нулевой степенью захода.

• Коцикл — минимальный разрез, минимальное множество ребер, удаление которого делает граф несвязным.

• Кратные рёбра — несколько рёбер, инцидентных одной и той же паре вершин. Встречаются в мультиграфах.

• Кубический граф — регулярный граф степени 3, то есть граф в котором каждой вершине инцидентно ровно три ребра.

• k-дольный граф — граф G, у которого хроматическое число c(G)=k

• k-связный граф — связный граф, в котором не существует набора из или менее вершин, такого, что удаление всех вершин и инцидентных им рёбер нарушает связность графа. В частности, связный граф является 1-связным, а двусвязный — 2-связным.

[править] Л

• Лама́нов граф с n вершинами — такой граф G, что, во-первых, для каждого k любой подграф графа G, содержащий k вершин, имеет не более, чем 2k −3 ребра и, во-вторых, граф G имеет ровно 2n −3 ребра.

• Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья.

• Лист дерева — вершина дерева с единственным ребром или входящей дугой.

• Локальная степень вершины — число рёбер ей инцидентных. Петля дает вклад, равный «2» в степень вершины.

[править] М

• Макси-код — трудновычислимый полный инвариант графа, получаемый путем выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Макси-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является максимально возможным.

• Маршрут в графе — это чередующаяся последовательность вершин и рёбер , в которой любые два соседних элемента инцидентны. Если , то маршрут замкнут, иначе открыт.

• Матрица достижимости орграфа — это матрица, содержащая информацию о существовании путей между вершинами в орграфе.

• Матрица инцидентности графа — это матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.

• Матрица смежности графа — это матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые инцидентны обоим вершинам). Петля считается сразу двумя соединениями для вершины, то есть к значению элемента матрицы в таком случае следует прибавлять 2.

• Мини-код — трудновычислимый полный инвариант графа, получаемый путем выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным.

• Минимальный каркас (или Каркас минимального веса, Минимальное остовное дерево) графа — ациклическое (не имеющее циклов) множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём минимальна.

• Множество смежности вершины v — множество вершин, смежных с вершиной v. Обозначается

• Мост — ребро, удаление которого увеличивает количество компонент связности в графе.

• Мультиграф — граф, в котором может быть пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.