Глоссарий теории графов

Найдите Приложение: Глоссарий теории графов в Викисловаре, бесплатном словаре.

Это глоссарий теории графов . Теория графов — это изучение графов , систем узлов или вершин, соединенных попарно линиями или ребрами.

Символы

Квадратные скобки [ ]: $G [S]$ — индуцированный подграф графа $G$ для подмножества вершин $S$ .
Главный символ ': Символ штриха часто используется для изменения обозначения инвариантов графа таким образом, чтобы он применялся к линейному графу вместо заданного графа. Например, $α (G)$ — число независимости графа; $α'(G)$ — соответствующее число графа, равное числу независимости его линейного графа. Аналогично, $χ (G)$ — хроматическое число графа; $χ'(G)$ — хроматический индекс графа, равный хроматическому числу его линейного графа.

А

поглощающий: Поглощающее множество ориентированного графа — это множество вершин, такое , что для любой вершины существует ребро из в сторону вершины . $А$ $G$ $v\in G\setminus A$ $v$ $А$
ахроматический: Ахроматическое число графа — это максимальное количество цветов в полной раскраске. ^[1]
ациклический: 1. Граф ацикличен, если он не имеет циклов. Неориентированный ациклический граф — это то же самое, что и лес . Ациклический ориентированный граф, который является орграфом без направленных циклов, часто называют ориентированным ациклическим графом , особенно в информатике. ^[2]; 2. Ациклическая раскраска неориентированного графа — это правильная раскраска, в которой каждые два цветовых класса порождают лес. ^[3]
матрица смежности: Матрица смежности графа — это матрица, строки и столбцы которой индексируются вершинами графа, при этом в ячейке для строки $i$ и столбца $j$ содержится единица , когда вершины $i$ и $j$ являются смежными, и ноль в противном случае. ^[4]
соседний: 1. Связь между двумя вершинами, которые являются конечными точками одного и того же ребра. ^[2]; 2. Связь между двумя различными ребрами, имеющими общую конечную вершину. ^[5]
α: Для графа $G$ $α (G)$ (используя греческую букву альфа) — его число независимости (см. независимые), а α $' (G)$ — его число соответствия (см. соответствие).
чередование: В графе с паросочетанием чередующийся путь — это путь, ребра которого чередуются между сопоставленными и не сопоставленными ребрами. Аналогично, чередующийся цикл — это цикл, ребра которого чередуются между сопоставленными и не сопоставленными ребрами. Увеличивающий путь — это чередующийся путь, который начинается и заканчивается в ненасыщенных вершинах. Большее паросочетание может быть найдено как симметричная разность паросочетания и увеличивающего пути; паросочетание является максимальным тогда и только тогда, когда у него нет увеличивающего пути.
антицепь: В ориентированном ациклическом графе — подмножество $S$ вершин, которые попарно несравнимы, т. е. для любого из $S$ не существует направленного пути из $x$ в $y$ или из $y$ в $x$ . Вдохновлено понятием антицепей в частично упорядоченных множествах . $x\leq y$
анти-край: Синоним не-ребра , пары несмежных вершин.
антитреугольник: Независимое множество из трех вершин, дополнение треугольника.
вершина: 1. Граф вершин — это граф, в котором можно удалить одну вершину, оставив планарный подграф. Удаленная вершина называется вершиной. Граф вершин $k$ — это граф, который можно сделать планарным, удалив $k$ вершин.; 2. Синоним универсальной вершины , вершины, смежной со всеми другими вершинами.
древовидность: Синоним корневого и направленного дерева; см. дерево.
дуга: См. край.
стрелка: Упорядоченная пара вершин, например, ребро в ориентированном графе. Стрелка $(x, y)$ имеет хвост $x$ , голову $y$ и направление $от x к y$ ; $y$ называется прямым преемником $x$ , а $x —$ прямым предшественником $y$ . Стрелка $(y, x)$ — это перевернутая стрелка стрелки $(x, y)$ .
точка сочленения: Вершина в связном графе, удаление которой разорвет граф. В более общем смысле, вершина, удаление которой увеличивает количество компонентов.
-арный: K $-$ арное дерево — это корневое дерево, в котором каждая внутренняя вершина имеет не более $k$ потомков. 1-арное дерево — это просто путь. 2-арное дерево также называется бинарным деревом , хотя этот термин более точно относится к 2-арным деревьям, в которых потомки каждого узла различаются как левые или правые потомки (не более одного каждого типа). $K$ -арное дерево называется полным, если каждая внутренняя вершина имеет ровно $k$ потомков.
увеличивающий: Особый тип чередующегося пути; см. чередование.
автоморфизм: Автоморфизм графа — это симметрия графа, изоморфизм графа на самого себя.

Б

сумка: Один из наборов вершин в разложении дерева.
сбалансированный: Двудольный или многодольный граф сбалансирован, если каждые два подмножества его вершинного разбиения имеют размеры в пределах одного друг от друга.
пропускная способность: Ширина полосы пропускания графа $G$ — это минимум, среди всех упорядочений вершин $G$ , длины самого длинного ребра (числа шагов в упорядочении между двумя его конечными точками). Она также на единицу меньше размера максимальной клики в надлежащем интервальном завершении $G$ , выбранном для минимизации размера клики.
бикли: Синоним полного двудольного графа или полного двудольного подграфа; см. полный.
двусвязный: Обычно синоним $2-$ вершинно-связного , но иногда включает K ₂ , хотя он не является 2-связным. См. связный; для двусвязных компонентов см. компонент.
обязательный номер: Наименьшее возможное отношение числа соседей собственного подмножества вершин к размеру подмножества. ^[6]
двудольный: Двудольный граф — это граф, вершины которого можно разделить на два непересекающихся множества таким образом, что вершины в одном множестве не связаны друг с другом, но могут быть связаны с вершинами в другом множестве. Другими словами, двудольный граф — это граф без нечетных циклов; эквивалентно, это граф, который можно правильно раскрасить двумя цветами. Двудольные графы часто записывают как $G = (U, V, E)$ , где $U$ и $V$ — подмножества вершин каждого цвета. Однако, если граф не связный, он может не иметь уникальной 2-раскраски.
бирегулярный: Бирегулярный граф — это двудольный граф, в котором существует только две различные степени вершин, по одной для каждого набора вершин двудольного разбиения.
блокировать: 1. Блок графа $G$ — это максимальный подграф, который является либо изолированной вершиной, либо ребром-мостом, либо 2-связным подграфом. Если блок 2-связен, то каждая пара вершин в нем принадлежит общему циклу. Каждое ребро графа принадлежит ровно одному блоку.; 2. Блочный граф графа $G$ — это другой граф, вершинами которого являются блоки графа $G$ , с ребром, соединяющим две вершины, когда соответствующие блоки имеют общую точку сочленения; то есть это граф пересечений блоков графа $G.$ Блочный граф любого графа — это лес.; 3. Граф блоков-сочленений (или блоков-точек сочленений) графа $G$ — это двудольный граф, в котором одно множество долей состоит из вершин сочленений $G$ , а другое имеет вершину для каждого блока G. $Когда$ G $связен$ , его граф блоков-точек сочленений является деревом. $b_{i}$ $B_{i}$; 4. Блочный граф (также называемый кликовым деревом, если он связан, и иногда ошибочно называемый деревом Хусими) — это граф, все блоки которого являются полными графами. Лес — это блочный граф; так, в частности, блочный граф любого графа является блочным графом, и каждый блочный граф может быть построен как блочный граф графа.
связь: Минимальное разделительное множество: множество ребер, удаление которых разъединяет граф, для которого ни одно собственное подмножество не обладает тем же свойством.
книга: 1. Книга , книжный граф или треугольная книга — это полный трехдольный граф $K 1,1, n$ ; набор из $n$ треугольников, соединенных общим ребром.; 2. Другой тип графа, также называемый книгой или четырехугольной книгой, представляет собой набор $4$ -циклов, соединенных общим ребром; декартово произведение звезды с ребром.; 3. Вложение книги — это вложение графа в топологическую книгу, пространство, образованное путем соединения набора полуплоскостей вдоль общей линии. Обычно вершины вложения должны находиться на линии, которая называется позвоночником вложения, а ребра вложения должны лежать в пределах одной полуплоскости, одной из страниц книги.
граница: 1. В графовом вложении граничный обход — это подграф, содержащий все инцидентные грани ребра и вершины.
ежевика: Ежевика — это совокупность взаимно соприкасающихся связанных подграфов, где два подграфа соприкасаются, если они имеют общую вершину или каждый включает одну конечную точку ребра. Порядок ежевики — это наименьший размер набора вершин, который имеет непустое пересечение со всеми подграфами. Ширина дерева графа — это максимальный порядок любого из его ежевик.
ветвь: Путь вершин степени два, заканчивающийся вершинами, степень которых не равна двум. ^[7]
ветвь-разложение: Разложение ветви G — это иерархическая кластеризация ребер $G$ $,$ представленная некорневым бинарным деревом с листьями, помеченными ребрами $G.$ Ширина разложения ветви — это максимум, по ребрам $e$ этого бинарного дерева, числа общих вершин между подграфами, определяемыми ребрами G $в$ двух поддеревьях, разделенных $e$ . Ширина ветви $G$ — это минимальная ширина любого разложения ветви $G.$
ширина ветки: См. разложение ветвей.
мост: 1. Мост , перешеек или разрезаемое ребро — это ребро, удаление которого разорвет граф. Граф без мостов — это граф, не имеющий мостов; эквивалентно 2-рёберно-связному графу.; 2. Мост подграфа H — это максимальный связный подграф, отделенный от остальной части графа H. То есть это максимальный подграф, который не пересекается по ребрам с H и в котором каждые две вершины и ребра принадлежат пути, который внутренне не пересекается с H. H может быть набором вершин. Хорда — это мост с одним ребром. В тесте планарности H — это цикл, а периферийный цикл — это цикл с не более чем одним мостом; он должен быть границей грани в любом планарном вложении своего графа.; 3. Мост цикла может также означать путь, который соединяет две вершины цикла, но короче любого из путей в цикле, соединяющих те же две вершины. Мостовой граф — это граф, в котором каждый цикл из четырех или более вершин имеет мост.
безмостовой: Граф без мостов или перешейков — это граф, не имеющий ребер-мостов (т. е. перешейков); то есть каждый связный компонент представляет собой граф с 2-связными ребрами .
бабочка: 1. Граф бабочки имеет пять вершин и шесть ребер; он образован двумя треугольниками, имеющими общую вершину.; 2. Сеть-бабочка — это граф, используемый в качестве сетевой архитектуры в распределенных вычислениях, тесно связанный с кубическими связными циклами .

С

С: $C n$ — граф-цикл $с n$ вершинами; см. цикл.
кактус: Граф кактусов , дерево кактусов, кактус или дерево Хусими — это связный граф, в котором каждое ребро принадлежит не более чем одному циклу. Его блоки являются циклами или одинарными ребрами. Если, кроме того, каждая вершина принадлежит не более чем двум блокам, то он называется рождественским кактусом.
клетка: Клетка — это регулярный граф с минимально возможным порядком обхвата.
канонический
канонизация: Каноническая форма графа — это инвариант, такой что два графа имеют равные инварианты тогда и только тогда, когда они изоморфны. Канонические формы также могут называться каноническими инвариантами или полными инвариантами, и иногда определяются только для графов в пределах определенного семейства графов. Канонизация графа — это процесс вычисления канонической формы.
карта: Граф, образованный из заданного графа путем удаления одной вершины, особенно в контексте гипотезы реконструкции . См. также колода, мультимножество всех карт графа.
ширина резьбы: Ширина вырезания — это понятие ширины графа, аналогичное ширине ветвей, но использующее иерархическую кластеризацию вершин вместо иерархической кластеризации ребер.
гусеница: Гусеничное дерево или гусеница — это дерево, в котором внутренние узлы образуют путь.
центр: Центр графа — это множество вершин с минимальным эксцентриситетом .
центроид: Центроид дерева — это вершина $v,$ такая, что при наличии корня в $v$ никакая другая вершина не имеет размера поддерева, превышающего половину размера дерева.
цепь: 1. Синоним слова «прогулка».; 2. При применении методов алгебраической топологии к графам элемент цепного комплекса , а именно набор вершин или набор ребер.
постоянная Чигера: См. расширение.
вишня: Вишня — это путь по трем вершинам. ^[8]
χ: $χ (G)$ (используя греческую букву хи) — хроматическое число $G$ , а $χ'(G)$ — его хроматический индекс; см. хроматика и окраска.
ребенок: В корневом дереве дочерний узел вершины $v$ является соседом $v$ по исходящему ребру, направленному от корня.
аккорд
хордовый: 1. Хорда цикла — это ребро, не принадлежащее циклу, у которого обе конечные точки принадлежат циклу.; 2. Хордовый граф — это граф, в котором каждый цикл из четырех или более вершин имеет хорду, поэтому единственными индуцированными циклами являются треугольники.; 3. Сильно хордальный граф — это хордовый граф, в котором каждый цикл длины шесть или более имеет нечетную хорду.; 4. Хордальный двудольный граф не является хордальным (если только он не является лесом); это двудольный граф, в котором каждый цикл из шести или более вершин имеет хорду, поэтому единственными индуцированными циклами являются 4-циклы.; 5. Хорда окружности — это отрезок прямой, соединяющий две точки окружности; граф пересечения набора хорд называется графом окружности .
хроматический: Имеющий отношение к раскраске; см. цвет. Хроматическая теория графов — это теория раскраски графов. Хроматическое число $χ (G)$ — это минимальное количество цветов, необходимое для правильной раскраски графа $G$ . $χ'(G)$ — это хроматический индекс графа $G$ , минимальное количество цветов, необходимое для правильной раскраски рёбер графа $G$ .
выбираемый
возможность выбора: Граф является $k$ -выбираемым, если он имеет списочную раскраску , когда каждая вершина имеет список из $k$ доступных цветов. Выбираемость графа — это наименьшее $k,$ для которого он является $k$ -выбираемым.
круг: Граф окружности — это граф пересечения хорд окружности.
схема: Контур может относиться к замкнутому пути или элементу пространства циклов (эйлеров остовной подграф). Ранг контура графа — это размерность его пространства циклов.
окружность: Окружность графа — это длина его самого длинного простого цикла. Граф является гамильтоновым тогда и только тогда, когда его окружность равна его порядку.
сорт: 1. Класс графов или семейство графов — это (обычно бесконечная) коллекция графов, часто определяемая как графы, имеющие некоторое определенное свойство. Слово «класс» используется вместо «множество», поскольку, если не наложены специальные ограничения (например, ограничение вершин, которые должны быть взяты из определенного множества, и определение ребер как множеств из двух вершин), классы графов обычно не являются множествами при формализации с использованием теории множеств.; 2. Цветовой класс цветного графа — это набор вершин или ребер, имеющих один определенный цвет.; 3. В контексте теоремы Визинга о раскраске ребер простых графов граф называется графом класса один, если его хроматический индекс равен его максимальной степени, и класса два, если его хроматический индекс равен единице плюс степень. Согласно теореме Визинга, все простые графы принадлежат либо к классу один, либо к классу два.
коготь: Клешня — это дерево с одной внутренней вершиной и тремя листьями, или, что эквивалентно, полный двудольный граф $K 1,3$ . Граф без клешни — это граф, который не имеет индуцированного подграфа, являющегося клешней.
клика: Клика — это множество взаимно смежных вершин (или полный подграф, индуцированный этим множеством). Иногда клика определяется как максимальное множество взаимно смежных вершин (или максимальный полный подграф), которое не является частью большего такого множества (или подграфа). K $-$ клика — это клика порядка $k$ . Число клики $ω$ $($ $G$ $)$ графа $G$ — это порядок его наибольшей клики. Граф клик графа G — это граф пересечений максимальных клик в G . См. также биклику, полный двудольный подграф.
дерево клики: Синоним блочного графа.
клика-ширина: Ширина клики графа $G$ — это минимальное количество различных меток, необходимое для построения $G$ с помощью операций, которые создают помеченную вершину, формируют непересекающееся объединение двух помеченных графов, добавляют ребро, соединяющее все пары вершин с заданными метками, или перемаркировывают все вершины с заданной меткой. Графы ширины клики не более $2$ — это в точности кографы .
закрыто: 1. Замкнутая окрестность — это окрестность, включающая свою центральную вершину; см. окрестность.; 2. Замкнутый маршрут — маршрут, который начинается и заканчивается в одной и той же вершине; см. маршрут.; 3. Граф транзитивно замкнут, если он равен своему собственному транзитивному замыканию; см. транзитивный.; 4. Свойство графа замкнуто относительно некоторой операции над графами, если всякий раз, когда аргумент или аргументы операции имеют свойство, то и результат тоже имеет его. Например, наследственные свойства замкнуты относительно индуцированных подграфов; монотонные свойства замкнуты относительно подграфов; а минорно-замкнутые свойства замкнуты относительно миноров.
закрытие: 1. О транзитивном замыкании ориентированного графа см. транзитивный.; 2. Замыкание ориентированного графа — это множество вершин, не имеющих исходящих ребер к вершинам вне замыкания. Например, сток — это замыкание с одной вершиной. Задача о замыкании — это задача нахождения замыкания минимального или максимального веса.
со-: Этот префикс имеет различные значения, обычно включающие дополнительные графы . Например, кограф — это граф, полученный с помощью операций, включающих дополнение; ко-раскраска — это раскраска, в которой каждая вершина индуцирует либо независимое множество (как при правильной раскраске), либо клику (как при раскраске дополнения).
цвет
раскрашивание: 1. Раскраска графа — это маркировка вершин графа элементами из заданного набора цветов или, что эквивалентно, разбиение вершин на подмножества, называемые «цветовыми классами», каждое из которых связано с одним из цветов.; 2. Некоторые авторы используют «раскраску» без уточнения, имея в виду правильную раскраску, которая назначает разные цвета конечным точкам каждого ребра. В раскраске графов цель состоит в том, чтобы найти правильную раскраску, которая использует как можно меньше цветов; например, двудольные графы — это графы, которые имеют раскраску только двумя цветами, а теорема о четырех цветах утверждает, что каждый планарный граф может быть раскрашен максимум четырьмя цветами. Граф называется $k$ -раскрашенным, если он был (правильно) раскрашен в $k$ цветов, и $k$ -раскрашиваемым или $k$ -хроматическим, если это возможно.; 3. Было изучено множество вариаций раскраски, включая раскраску ребер (раскраска ребер таким образом, что никакие два ребра с одной и той же конечной точкой не имеют общего цвета), раскраску списков (правильная раскраска, при которой каждая вершина ограничена подмножеством доступных цветов), ациклическую раскраску (каждый двухцветный подграф является ациклическим), совместную раскраску (каждый цветовой класс индуцирует независимый набор или клику), полную раскраску (каждые два цветовых класса имеют общее ребро) и полную раскраску (раскрашиваются как ребра, так и вершины).; 4. Число раскраски графа равно единице плюс вырожденность . Оно так называется потому, что применение жадного алгоритма раскраски к порядку вырожденности графа использует не более этого количества цветов.
сопоставимость: Неориентированный граф является графом сравнимости, если его вершины являются элементами частично упорядоченного множества , а две вершины являются смежными, когда они сравнимы в частичном порядке. Эквивалентно, граф сравнимости является графом, имеющим транзитивную ориентацию. Многие другие классы графов могут быть определены как графы сравнимости специальных типов частичного порядка.
дополнять: Дополнительный граф простого графа $G$ — это другой граф с тем же множеством вершин, что и G $,$ с ребром для каждых двух вершин, которые не являются смежными в $G.$ ${\bar {G}}$
полный: 1. Полный граф — это граф, в котором каждые две вершины смежны: присутствуют все ребра, которые могли бы существовать. Полный граф с $n$ вершинами часто обозначается $K n$ . Полный двудольный граф — это граф, в котором каждые две вершины на противоположных сторонах разбиения вершин смежны. Полный двудольный граф с $a$ вершинами на одной стороне разбиения и $b$ вершинами на другой стороне часто обозначается $K a, b$ . Та же терминология и обозначения были также распространены на полные многодольные графы , графы, в которых вершины разделены более чем на два подмножества, и каждая пара вершин в разных подмножествах смежна; если числа вершин в подмножествах равны $a, b, c, ... ,$ то этот граф обозначается $K a, b, c, ...$ .; 2. Пополнение данного графа — это надграф, который имеет некоторое желаемое свойство. Например, хордовое пополнение — это надграф, который является хордовым графом.; 3. Полное совпадение является синонимом идеального совпадения ; см. совпадение.; 4. Полная раскраска — это правильная раскраска, в которой каждая пара цветов используется для конечных точек хотя бы одного ребра. Каждая раскраска с минимальным количеством цветов является полной, но могут существовать полные раскраски с большим количеством цветов. Ахроматическое число графа — это максимальное количество цветов в полной раскраске.; 5. Полный инвариант графа — синоним канонической формы, инвариант, имеющий различные значения для неизоморфных графов.
компонент: Связный компонент графа — это максимальный связный подграф. Этот термин также используется для максимальных подграфов или подмножеств вершин графа, которые имеют более высокий порядок связности, включая двусвязные компоненты , трехсвязные компоненты и сильно связные компоненты .
конденсация: Конденсация ориентированного графа $G —$ это ориентированный ациклический граф с одной вершиной для каждого сильно связанного компонента $G$ и ребром, соединяющим пары компонентов , которые содержат две конечные точки хотя бы одного ребра в $G.$
конус: Граф, содержащий универсальную вершину .
соединять: Причина быть связанным.
подключен: Связный граф — это граф, в котором каждая пара вершин образует конечные точки пути. Более высокие формы связности включают сильную связность в ориентированных графах (для каждых двух вершин существуют пути от одной до другой в обоих направлениях), графы с $k$ -вершинной связностью (удаление менее $k$ вершин не может разорвать граф) и графы с k -рёберной связностью (удаление менее $k$ рёбер не может разорвать граф).
связанный компонент: Синоним компонента.
сокращение: Стягивание ребер — это элементарная операция, которая удаляет ребро из графа, объединяя две вершины, которые оно ранее соединило. Стягивание вершин (иногда называемое идентификацией вершин) похоже, но две вершины не обязательно соединены ребром. Стягивание путей происходит над набором ребер в пути, которые стягиваются, чтобы сформировать одно ребро между конечными точками пути. Обратной стягиванию ребер является расщепление вершин.
общаться: Обратный граф является синонимом транспонированного графа; см. транспонирование.
основной: 1. $k$ -ядро — это индуцированный подграф, образованный путем удаления всех вершин степени, меньшей $k$ , и всех вершин, степень которых стала меньше $k$ после более ранних удалений. См. вырождение.; 2. Ядро — это граф $G,$ такой что любой гомоморфизм графа из $G$ в себя является изоморфизмом.; 3. Ядро графа $G$ — это минимальный граф $H,$ такой что существуют гомоморфизмы из $G$ в $H$ и наоборот. $H$ единствен с точностью до изоморфизма. Он может быть представлен как индуцированный подграф $G$ и является ядром в том смысле, что все его самомоморфизмы являются изоморфизмами.; 4. В теории паросочетаний графов ядром графа является аспект его разложения Дульмейджа–Мендельсона , образованный как объединение всех максимальных паросочетаний.
котри: 1. Дополнение остовного дерева .; 2. Структура корневого дерева, используемая для описания кографа , в которой каждая вершина кографа является листом дерева, каждый внутренний узел дерева помечен 0 или 1, а две вершины кографа являются смежными тогда и только тогда, когда их наименьший общий предок в дереве помечен 1.
крышка: Покрытие вершин — это набор вершин, инцидентных каждому ребру в графе. Покрытие рёбер — это набор рёбер, инцидентных каждой вершине в графе. Набор подграфов графа покрывает этот граф, если их объединение — взятое по вершинам и по рёбрам — равно графу.
критический: Критический граф для заданного свойства — это граф, который имеет свойство, но такой, что каждый подграф, образованный удалением одной вершины, не имеет свойства. Например, факторно-критический граф — это граф, который имеет идеальное паросочетание (1-фактор) для каждого удаления вершины, но (поскольку у него нечетное число вершин) сам не имеет идеального паросочетания. Сравните hypo- , используемый для графов, которые не имеют свойства, но для которых каждое удаление одной вершины имеет.
куб
кубический: 1. Граф куба , граф из восьми вершин и ребер куба.; 2. Граф гиперкуба , многомерное обобщение графа куба.; 3. Сложенный кубический граф , образованный из гиперкуба путем добавления парных соединяющих противоположных вершин.; 4. Граф , разделенный пополам , — половина квадрата графа гиперкуба.; 5. Частичный куб , сохраняющий расстояние подграф гиперкуба.; 6. Куб графа $G$ — это мощность графа $G 3$ .; 7. Кубический граф , другое название $3$ -регулярного графа, в котором каждая вершина имеет три инцидентных ребра.; 8. Кубически-связанные циклы — кубический граф, образованный заменой каждой вершины гиперкуба циклом.
резать
набор для резки: Разрез — это разбиение вершин графа на два подмножества или набор (также известный как набор разрезов) ребер, которые охватывают такое разбиение, если это множество непустое. Говорят, что ребро охватывает разбиение, если оно имеет конечные точки в обоих подмножествах. Таким образом, удаление набора разрезов из связного графа отключает его.
точка отсечения: См. точку артикуляции.
вырезать пространство: Пространство разрезов графа представляет собой GF(2) -векторное пространство, элементами которого являются множества разрезов графа, а в качестве операции сложения векторов — симметрическая разность множеств.
цикл: 1. Цикл может быть либо видом графа, либо видом прогулки. Как прогулка он может быть либо замкнутым обходом (также называемым туром), либо, что более типично, замкнутым обходом без повторяющихся вершин и, следовательно, ребер (также называемым простым циклом). В последнем случае он обычно рассматривается как граф, т. е. выбор первой вершины и направления обычно считается неважным; то есть циклические перестановки и развороты обхода производят один и тот же цикл. Важные специальные типы циклов включают гамильтоновы циклы , индуцированные циклы , периферийные циклы и кратчайший цикл, который определяет обхват графа. $K$ -цикл — это цикл длины $k$ ; например, $2$ -цикл — это двуугольник , а $3-$ цикл — это треугольник. Граф-цикл — это граф, который сам по себе является простым циклом; граф-цикл с $n$ вершинами обычно обозначается $C n$ .; 2. Пространство циклов — это векторное пространство, порожденное простыми циклами в графе, часто над полем из 2 элементов, но также и над другими полями.

Д

ДАГ: Сокращение от направленный ациклический граф , ориентированный граф без каких-либо направленных циклов.
палуба: Мультимножество графов, образованное из одного графа $G$ путем удаления одной вершины всеми возможными способами, особенно в контексте гипотезы реконструкции . Колода ребер формируется таким же образом путем удаления одного ребра всеми возможными способами. Графы в колоде также называются картами . См. также критические (графы, обладающие свойством, которого нет ни у одной карты) и гипо- (графы, не обладающие свойством, которого нет ни у одной карты).
разложение: См. разложение дерева, разложение пути или разложение ветвей.
вырождаться
вырождение: k -вырожденный граф — это неориентированный граф, в котором каждый индуцированный подграф имеет минимальную степень не более $k$ . Вырожденность графа — это наименьшее $k,$ для которого он является $k$ -вырожденным. Упорядочение вырожденности — это упорядочение вершин, при котором каждая вершина имеет минимальную степень в индуцированном подграфе и всех более поздних вершинах; в упорядочении вырожденности $k$ $-вырожденного$ графа каждая вершина имеет не более $k$ более поздних соседей. Вырожденность также известна как $k$ -ядерное число, ширина и связь, а единица плюс вырожденность также называется числом раскраски или числом Секереша–Вильфа. $k$ -вырожденные графы также называются $k$ -индуктивными графами.
степень: 1. Степень вершины в графе — это число инцидентных ребер. ^[2] Степень графа $G$ (или его максимальная степень) — это максимальная из степеней его вершин, часто обозначаемая $Δ(G)$ ; минимальная степень $G$ — это минимальная из степеней его вершин, часто обозначаемая $δ (G)$ . Степень иногда называется валентностью ; степень $v$ в $G$ может обозначаться $d G (v)$ , $d (G)$ или $deg(v)$ . Общая степень — это сумма степеней всех вершин; по лемме о рукопожатии это четное число. Последовательность степеней — это набор степеней всех вершин, отсортированных от наибольшего к наименьшему. В ориентированном графе можно выделить входную степень (число входящих ребер) и исходящую степень (число исходящих ребер). ^[2]; 2. Степень гомоморфизма графа является синонимом его числа Хадвигера , порядка наибольшего минора клики.
Δ, δ: $Δ(G)$ (используя греческую букву дельта) — максимальная степень вершины в $G$ , а $δ (G)$ — минимальная степень; см. степень.
плотность: В графе из n узлов плотность — это отношение числа ребер графа к числу ребер в полном графе из n узлов. См. плотный граф .
глубина: Глубина узла в корневом дереве — это количество ребер на пути от корня к узлу. Например, глубина корня равна 0, а глубина любого из его смежных узлов равна 1. Это уровень узла минус один. Обратите внимание, однако, что некоторые авторы вместо этого используют глубину как синоним уровня узла . ^[9]
диаметр: Диаметр связного графа — это максимальная длина кратчайшего пути . То есть, это максимальное расстояние между парами вершин в графе. Если граф имеет веса на своих ребрах, то его взвешенный диаметр измеряет длину пути по сумме весов ребер вдоль пути, в то время как невзвешенный диаметр измеряет длину пути по количеству ребер. Для несвязных графов определения различаются: диаметр может быть определен как бесконечный или как наибольший диаметр связного компонента, или он может быть неопределенным.
алмаз: Алмазный граф — это неориентированный граф с четырьмя вершинами и пятью ребрами.
разъединенный: Сильно связанный. (Не путать с разъединенным)
дигон: Двуугольник — это простой цикл длины два в ориентированном графе или мультиграфе. Двуугольники не могут встречаться в простых неориентированных графах, поскольку они требуют повторения одного и того же ребра дважды, что нарушает определение простого .
диграф: Синоним для направленного графа . ^[2]
дипат: См. направленный путь.
прямой предшественник: Хвост направленного ребра, вершиной которого является заданная вершина.
прямой преемник: Голова направленного ребра, хвостом которого является заданная вершина.
направленный: Направленный граф — это граф, в котором ребра имеют выделенное направление, от одной вершины к другой. ^[2] В смешанном графе направленное ребро — это снова то, которое имеет выделенное направление; направленные ребра также могут называться дугами или стрелками.
направленная дуга: См. стрелку.
направленный край: См. стрелку.
направленная линия: См. стрелку.
направленный путь: Путь, в котором все ребра имеют одинаковое направление. Если направленный путь ведет из вершины $x$ в вершину $y$ , $x$ является предшественником $y$ , $y$ является последователем $x$ , и говорят, что $y достижим из$ $x$ .
направление: 1. Асимметричное отношение между двумя соседними вершинами в графе, представленное в виде стрелки.; 2. Асимметричное отношение между двумя вершинами в направленном пути.
отключить: Причина отключения.
отключен: Не подключено.
непересекающийся: 1. Два подграфа не пересекаются по ребрам, если они не имеют общих ребер, и не пересекаются по вершинам, если они не имеют общих вершин.; 2. Непересекающееся объединение двух или более графов — это граф, множества вершин и ребер которого являются непересекающимися объединениями соответствующих множеств.
число диссоциации: Подмножество вершин в графе G называется диссоциацией , если оно индуцирует подграф с максимальной степенью 1.
расстояние: Расстояние между любыми двумя вершинами в графе — это длина кратчайшего пути, конечными точками которого являются эти две вершины .
доматик: Доматическое разбиение графа — это разбиение вершин на доминирующие множества. Доматическое число графа — это максимальное количество доминирующих множеств в таком разбиении.
доминирующий: Доминирующий набор — это набор вершин, который включает или смежно с каждой вершиной в графе; не путать с покрытием вершин, набором вершин, который инцидентен всем ребрам в графе. Важные специальные типы доминирующих наборов включают независимые доминирующие наборы (доминирующие наборы, которые также являются независимыми наборами) и связанные доминирующие наборы (доминирующие наборы, которые индуцируют связанные подграфы). Доминирующий набор с одной вершиной также может называться универсальной вершиной. Число доминирования графа — это количество вершин в наименьшем доминирующем наборе.
двойной: Двойственный граф плоского графа $G$ — это граф , имеющий вершину для каждой грани $G.$

Э

Э: $E (G)$ — множество рёбер графа $G$ ; см. множество рёбер.
ухо: Ухо графа — это путь, конечные точки которого могут совпадать, но в котором нет повторений вершин или ребер.
разложение уха: Разложение на ухо — это разбиение ребер графа на последовательность ушей, каждая из конечных точек которых (после первой) принадлежит предыдущему уху, а каждая из внутренних точек не принадлежит ни одному предыдущему уху. Открытое ухо — это простой путь (ухо без повторяющихся вершин), а разложение на открытое ухо — это разложение на ухо, в котором каждое ухо после первого открыто; граф имеет разложение на открытое ухо тогда и только тогда, когда он двусвязен. Ухо нечетно, если у него нечетное число ребер, а разложение на нечетное ухо — это разложение на ухо, в котором каждое ухо нечетно; граф имеет разложение на нечетное ухо тогда и только тогда, когда он факторно-критичен.
эксцентриситет: Эксцентриситет вершины — это наибольшее расстояние от нее до любой другой вершины.
край: Ребро (вместе с вершинами) является одной из двух основных единиц, из которых строятся графы. Каждое ребро имеет две (или в гиперграфах больше) вершины, к которым оно прикреплено, называемые его конечными точками. Ребра могут быть направленными или ненаправленными; ненаправленные ребра также называются линиями, а направленные ребра также называются дугами или стрелками. В ненаправленном простом графе ребро может быть представлено как множество его вершин, а в направленном простом графе оно может быть представлено как упорядоченная пара его вершин. Ребро, соединяющее вершины $x$ и $y,$ иногда записывается $как xy$ .
обрезанный край: Набор ребер, удаление которых разъединяет граф. Разрез с одним ребром называется мостом, перешейком или ребром разреза.
набор кромок: Множество рёбер данного графа $G$ , иногда обозначаемое как $E (G)$ .
безграничный граф: Граф без рёбер или полностью несвязный граф на заданном наборе вершин — это граф, который не имеет рёбер. Иногда его называют пустым графом, но этот термин может также относиться к графу без вершин.
встраивание: Вложение графа — это топологическое представление графа как подмножества топологического пространства, в котором каждая вершина представлена точкой, каждое ребро представлено кривой, имеющей концы ребра в качестве концов кривой, и нет других пересечений между вершинами или ребрами. Планарный граф — это граф, который имеет такое вложение на евклидовой плоскости, а тороидальный граф — это граф, который имеет такое вложение на торе. Род графа — это минимально возможный род двумерного многообразия , в которое он может быть вложен.
пустой график: 1. Граф без рёбер на непустом множестве вершин.; 2. Граф нулевого порядка — граф без вершин и ребер.
конец: Конец бесконечного графа — это класс эквивалентности лучей, где два луча эквивалентны, если существует третий луч, включающий бесконечно много вершин из них обоих.
конечная точка: Одна из двух вершин, соединенных данным ребром, или одна из первых или последних вершин пути, тропы или пути. Первая конечная точка данного направленного ребра называется хвостом , а вторая конечная точка называется головой .
перечисление: Перечисление графов — это проблема подсчета графов в заданном классе графов в зависимости от их порядка. В более общем смысле, проблемы перечисления могут относиться либо к проблемам подсчета определенного класса комбинаторных объектов (таких как клики, независимые множества, раскраски или остовные деревья), либо к алгоритмическому перечислению всех таких объектов.
Эйлеров: Эйлеров путь — это обход, который использует каждое ребро графа ровно один раз. Эйлеров контур (также называемый эйлеровым циклом или эйлеровым туром) — это замкнутый обход, который использует каждое ребро ровно один раз. Эйлеров граф — это граф, имеющий эйлеров контур. Для неориентированного графа это означает, что граф связен и каждая вершина имеет четную степень. Для ориентированного графа это означает, что граф сильно связен и каждая вершина имеет входную степень, равную исходной степени. В некоторых случаях требование связности ослабляется, и граф, отвечающий только требованиям степени, называется эйлеровым.
даже: Делится на два; например, четный цикл — это цикл, длина которого четна.
расширитель: Граф -экспандер — это граф, у которого расширение ребер, расширение вершин или спектральное расширение ограничено нулем.
расширение: 1. Расширение ребер, изопериметрическое число или константа Чигера графа $G$ — это минимальное отношение (по подмножествам $S$ , состоящим не более чем из половины вершин $G$ ) числа ребер, выходящих из $S,$ к числу вершин в $S.$; 2. Расширение вершин, изопериметрическое число вершин или увеличение графа $G$ — это минимальное отношение (по подмножествам $S$ , состоящим не более чем из половины вершин $G$ ) числа вершин вне S, но смежных с $ним,$ к числу вершин в $S.$; 3. Расширение уникального соседа графа $G$ — это минимальное отношение (по подмножествам, состоящим не более чем из половины вершин $G$ ) числа вершин, находящихся вне $S,$ но смежных с уникальной вершиной в $S,$ к числу вершин в $S.$; 4. Спектральное расширение $d$ -регулярного графа $G$ — это спектральный зазор между наибольшим собственным значением $d$ его матрицы смежности и вторым по величине собственным значением.; 5. Семейство графов имеет ограниченное расширение , если все его $r$ -неглубокие миноры имеют отношение ребер к вершинам, ограниченное функцией от $r$ , и полиномиальное расширение, если функция от $r$ является полиномом.

Ф

лицо: В плоском графе или графовом вложении — связный компонент подмножества плоскости или поверхности вложения, который не пересекается с графом. Для вложения в плоскость все грани, кроме одной, будут ограничены; одна исключительная грань, которая простирается до бесконечности, называется внешней гранью.
фактор: Фактор графа — это остовной подграф: подграф, включающий все вершины графа. Этот термин в основном используется в контексте регулярных подграфов: $k$ -фактор — это фактор, который является $k$ -регулярным. В частности, $1$ -фактор — это то же самое, что и идеальное паросочетание. Факторно-критический граф — это граф, для которого удаление любой одной вершины приводит к графу с $1-$ фактором.
факторизация: Факторизация графа — это разбиение ребер графа на множители; $k$ -факторизация — это разбиение на $k$ -множители. Например, $1-$ факторизация — это раскраска ребер с дополнительным свойством, что каждая вершина инцидентна ребру каждого цвета.
семья: Синоним слова «класс».
конечный: Граф конечен, если он имеет конечное число вершин и конечное число ребер. Многие источники предполагают, что все графы конечны, не говоря об этом явно. Граф локально конечен, если каждая вершина имеет конечное число инцидентных ребер. Бесконечный граф — это граф, который не является конечным: он имеет бесконечно много вершин, бесконечно много ребер или и то, и другое.
первый заказ: Логика первого порядка графов — это форма логики, в которой переменные представляют вершины графа, и существует бинарный предикат для проверки того, являются ли две вершины смежными. Следует отличать от логики второго порядка, в которой переменные также могут представлять наборы вершин или ребер.
-лоскут: Для набора вершин $X$ X -лоскут — это связный компонент индуцированного подграфа, образованного удалением $X.$ Терминология лоскута обычно используется в контексте убежищ , функций, которые отображают небольшие наборы вершин в их лоскуты. См. также мост цикла, который является либо лоскутом вершин цикла $,$ либо хордой цикла.
запрещенный: Характеристика запрещенного графа — это характеристика семейства графов как графов, которые не имеют определенных других графов в качестве подграфов, индуцированных подграфов или миноров. Если $H$ — один из графов, который не встречается как подграф, индуцированный подграф или минор, то говорят, что $H запрещен.$
форсирование графика: Форсирующий граф — это граф $H,$ такой что оценка плотности подграфов $H$ в графах последовательности графов $G(n)$ достаточна для проверки того, является ли эта последовательность квазислучайной.
лес: Лес — это неориентированный граф без циклов (несвязное объединение некорневых деревьев) или ориентированный граф, образованный как несвязное объединение корневых деревьев.
Фрукт: 1. Роберт Фрухт; 2. Граф Фрухта , один из двух наименьших кубических графов без нетривиальных симметрий.; 3. Теорема Фрухта о том, что каждая конечная группа является группой симметрий конечного графа.
полный: Синоним слова «индуцированный».
функциональный график: Функциональный граф — это ориентированный граф, в котором каждая вершина имеет исходящую степень. Эквивалентно, функциональный граф — это максимальный направленный псевдолес.

Г

Г: Переменная, часто используемая для обозначения графика.
род: Род графа — это минимальный род поверхности, на которую он может быть вложен; см. вложение.
геодезический: Как существительное, геодезический является синонимом кратчайшего пути . При использовании в качестве прилагательного, он означает относящийся к кратчайшим путям или кратчайшим расстояниям пути.
гигант: В теории случайных графов гигантский компонент — это связный компонент, содержащий постоянную долю вершин графа. В стандартных моделях случайных графов обычно имеется не более одного гигантского компонента.
обхват: Обхват графа — это длина его самого короткого цикла.
график: Основной объект изучения в теории графов, система вершин, соединенных попарно ребрами. Часто подразделяется на ориентированные графы или неориентированные графы в зависимости от того, имеют ли ребра ориентацию или нет. Смешанные графы включают оба типа ребер.
жадный: Произведено жадным алгоритмом . Например, жадная раскраска графа — это раскраска, полученная путем рассмотрения вершин в некоторой последовательности и назначения каждой вершине первого доступного цвета.
Грётч: 1. Герберт Грётч; 2. Граф Грётша — наименьший граф без треугольников, требующий четырёх цветов при любой правильной раскраске.; 3. Теорема Грётша о том, что планарные графы без треугольников всегда можно раскрасить максимум тремя цветами.
Число Гранди: 1. Число Гранди графа — это максимальное количество цветов, получаемых при жадной раскраске с плохо выбранным порядком вершин.

ЧАС

ЧАС: Переменная, часто используемая для обозначения графа, особенно когда другой граф уже обозначен как $G.$
H- окраска: $H$ - раскраска графа $G$ ( где $H$ также является графом) — это гомоморфизм из $H$ в $G.$
H -свободный: Граф является $H$ -свободным, если он не имеет индуцированного подграфа, изоморфного $H$ , то есть если $H$ является запрещенным индуцированным подграфом. $H$ -свободные графы являются семейством всех графов (или, часто, всех конечных графов), которые являются $H$ -свободными. ^[10] Например, графы без треугольников являются графами, которые не имеют графа треугольников в качестве подграфа. Свойство быть $H$ -свободным всегда наследственно. Граф является $H$ -свободным от миноров, если он не имеет минора, изоморфного $H$ .
Хадвигер: 1. Хьюго Хадвигер; 2. Число Хадвигера графа — это порядок наибольшего полного минора графа. Его также называют числом клики сжатия или степенью гомоморфизма.; 3. Гипотеза Хадвигера — это гипотеза о том, что число Хадвигера никогда не меньше хроматического числа.
Гамильтониан: Гамильтонов путь или гамильтонов цикл — это простой остовной путь или простой остовной цикл: он охватывает все вершины графа ровно один раз. Граф является гамильтоновым, если он содержит гамильтонов цикл, и трассируемым, если он содержит гамильтонов путь.
убежище: K $-$ убежище — это функция, которая отображает каждое множество $X$ из менее чем $k$ вершин в один из его лоскутов, часто удовлетворяя дополнительным условиям согласованности. Порядок убежища — это число $k$ . Убежища можно использовать для характеристики ширины дерева конечных графов, а также концов и чисел Хадвигера бесконечных графов.
высота: 1. Высота узла в корневом дереве — это число ребер в самом длинном пути, идущем от корня (т.е. его узлы имеют строго возрастающую глубину), который начинается в этом узле и заканчивается в листе.; 2. Высота корневого дерева — это высота его корня. То есть, высота дерева — это количество ребер в максимально длинном возможном пути, идущем от корня, который начинается в корне и заканчивается в листе.; 3. Высота ориентированного ациклического графа — это максимальная длина ориентированного пути в этом графе.
наследственный: Наследственное свойство графов — это свойство, которое замкнуто относительно индуцированных подграфов: если $G$ имеет наследственное свойство, то оно должно быть и у каждого индуцированного подграфа $G.$ Сравните монотонный (замкнутый относительно всех подграфов) или минорно-замкнутый (замкнутый относительно миноров).
шестиугольник: Простой цикл, состоящий ровно из шести ребер и шести вершин.
дыра: Дыра — это индуцированный цикл длины четыре или более. Нечетная дыра — это дыра нечетной длины. Антидыра — это индуцированный подграф порядка четыре, дополнением которого является цикл; эквивалентно, это дыра в графе дополнения. Эта терминология в основном используется в контексте совершенных графов, которые характеризуются сильной теоремой о совершенном графе как графы без нечетных дыр или нечетных антидыр. Графы без дыр — это то же самое, что и хордовые графы .
гомоморфная эквивалентность: Два графа гомоморфно эквивалентны , если существуют два гомоморфизма, по одному из каждого графа в другой граф.
гомоморфизм: 1. Гомоморфизм графа — это отображение множества вершин одного графа на множество вершин другого графа, которое отображает смежные вершины на смежные вершины. Этот тип отображения между графами наиболее часто используется в теоретико-категорных подходах к теории графов. Правильная раскраска графа может быть эквивалентно описана как гомоморфизм в полный граф.; 2. Степень гомоморфизма графа является синонимом его числа Хадвигера , порядка наибольшего минора клики.
гипердуга: Направленное гиперребро, имеющее исходный и целевой наборы.
гиперэдж: Ребро в гиперграфе, имеющее любое количество конечных точек, в отличие от требования, чтобы ребра графов имели ровно две конечные точки.
гиперкуб: Граф гиперкуба — это граф, образованный вершинами и рёбрами геометрического гиперкуба .
гиперграф: Гиперграф — это обобщение графа, в котором каждое ребро (в данном контексте называемое гиперребром) может иметь более двух конечных точек.
гипо-: Этот префикс в сочетании со свойством графа указывает на граф, который не имеет свойства, но такой, что каждый подграф, образованный удалением одной вершины, имеет свойство. Например, гипогамильтонов граф — это граф, который не имеет гамильтонова цикла, но для которого каждое удаление одной вершины создает гамильтонов подграф. Compare critical, используется для графов, которые имеют свойство, но для которых каждое удаление одной вершины не создает. ^[11]

я

в степени: Число входящих рёбер в ориентированном графе; см. степень.
заболеваемость: Инцидентность в графе — это пара вершина-ребро , такая, что вершина является конечной точкой ребра.
матрица инцидентности: Матрица инцидентности графа — это матрица, строки которой индексируются вершинами графа, а столбцы — ребрами, при этом в ячейке для строки $i$ и столбца $j$ содержится единица, когда вершина $i$ и ребро $j$ инцидентны, и ноль в противном случае.
инцидент: Связь между ребром и одной из его конечных точек. ^[2]
несравнимость: Граф несравнимости является дополнением графа сравнимости ; см. сравнимость.
независимый: 1. Независимое множество — это множество вершин, которое порождает подграф без рёбер. Его также можно назвать стабильным множеством или кокликой. Число независимости $α (G)$ — это размер максимального независимого множества .; 2. В графическом матроиде графа подмножество ребер независимо, если соответствующий подграф является деревом или лесом. В бициклическом матроиде подмножество ребер независимо, если соответствующий подграф является псевдолесом .
безразличие: График безразличия — это другое название правильного интервального графика или графика единичных интервалов; см. правильный.
индуцированный: Индуцированный подграф или полный подграф графа — это подграф, образованный из подмножества вершин и из всех ребер, которые имеют обе конечные точки в подмножестве. Особые случаи включают индуцированные пути и индуцированные циклы , индуцированные подграфы, которые являются путями или циклами.
индуктивный: Синоним слова «дегенерат».
бесконечный: Бесконечный граф — это граф, который не является конечным; см. конечный.
внутренний: Вершина пути или дерева является внутренней, если она не является листом; то есть, если ее степень больше единицы. Два пути являются внутренне непересекающимися (некоторые называют это независимыми ), если они не имеют ни одной общей вершины, кроме первой и последней.
пересечение: 1. Пересечение двух графов — это их наибольший общий подграф, граф, образованный вершинами и ребрами, принадлежащими обоим графам.; 2. Граф пересечений — это граф, вершины которого соответствуют множествам или геометрическим объектам, с ребром между двумя вершинами именно тогда, когда соответствующие два множества или объекта имеют непустое пересечение. Несколько классов графов могут быть определены как графы пересечений определенных типов объектов, например, хордовые графы (графы пересечений поддеревьев дерева), круговые графы (графы пересечений хорд окружности), интервальные графы (графы пересечений интервалов прямой), линейные графы (графы пересечений ребер графа) и кликовые графы (графы пересечений максимальных клик графа). Каждый граф является графом пересечений для некоторого семейства множеств, и это семейство называется представлением пересечений графа. Число пересечений графа $G$ — это минимальное общее число элементов в любом представлении пересечений графа $G$ .
интервал: 1. Интервальный граф — это граф пересечения интервалов прямой .; 2. Интервал $[u, v]$ в графе представляет собой объединение всех кратчайших путей от $u$ до $v$ .; 3. Толщина интервала является синонимом ширины пути.
инвариантный: Синоним слова «собственность».
перевернутая стрелка: Стрелка с противоположным направлением по сравнению с другой стрелкой. Стрелка $(y, x)$ является перевернутой стрелкой стрелки $(x, y)$ .
изолированный: Изолированная вершина графа — это вершина, степень которой равна нулю, то есть вершина, не имеющая инцидентных ребер. ^[2]
изоморфный: Два графа изоморфны, если между ними существует изоморфизм; см. изоморфизм.
изоморфизм: Изоморфизм графов — это взаимно-однозначное соответствие вершин и ребер одного графа вершинам и ребрам другого графа, сохраняющее инцидентность. Два графа, связанные таким образом, называются изоморфными.
изопериметрический: См. расширение.
перешеек: Синоним слова «мост» в значении ребра, удаление которого разрывает граф.

Дж.

присоединиться: Объединение двух графов образуется из их несвязного объединения путем добавления ребра из каждой вершины одного графа в каждую вершину другого. Эквивалентно, это дополнение несвязного объединения дополнений .

К

К: Обозначения для полных графов, полных двудольных графов и полных многодольных графов см. в разделе Complete.
к: $κ (G)$ (используя греческую букву каппа) может относиться к $связности$ вершин Gили к числу клик $G$ .
ядро: Ядро ориентированного графа — это набор вершин, который является одновременно устойчивым и поглощающим.
узел: Неизбежный участок ориентированного графа. См. узел (математика) и теория узлов .

Л

Л: $L (G)$ — линейный график G $; см .$ линию.
этикетка: 1. Информация, связанная с вершиной или ребром графа. Помеченный граф — это граф, вершины или ребра которого имеют метки. Термины «помеченный вершиной» или «помеченный ребром» могут использоваться для указания того, какие объекты графа имеют метки. Маркировка графа относится к нескольким различным проблемам назначения меток графам, подчиняющимся определенным ограничениям. См. также раскраска графа , в которой метки интерпретируются как цвета.; 2. В контексте перечисления графов вершины графа называются помеченными, если все они различимы друг от друга. Например, это можно сделать истинным, зафиксировав однозначное соответствие между вершинами и целыми числами от 1 до порядка графа. Когда вершины помечены, графы, которые изоморфны друг другу (но с разным порядком вершин), считаются отдельными объектами. Напротив, когда вершины не помечены, графы, которые изоморфны друг другу, не считаются отдельно.
лист: 1. Листовая вершина или висячая вершина (особенно в дереве) — это вершина, степень которой равна $1.$ Листовое ребро или висячее ребро — это ребро, соединяющее листовую вершину с ее единственным соседом.; 2. Мощность листьев дерева — это граф, вершинами которого являются листья дерева, а ребра соединяют листья, расстояние между которыми в дереве не превышает заданного порогового значения.
длина: В невзвешенном графе длина цикла, пути или обхода — это количество используемых им ребер. Во взвешенном графе это может быть сумма весов используемых им ребер. Длина используется для определения кратчайшего пути , обхвата (кратчайшей длины цикла) и длиннейшего пути между двумя вершинами в графе.
уровень: 1. Это глубина узла плюс 1, хотя некоторые ^[12] определяют его как синоним глубины . Уровень узла в корневом дереве — это количество узлов на пути от корня к узлу. Например, корень имеет уровень 1, а любой из его смежных узлов — уровень 2.; 2. Набор всех узлов, имеющих одинаковый уровень или глубину. ^[12]
линия: Синоним ненаправленного ребра. Линейный граф $L (G)$ графа $G$ — это граф с вершиной для каждого ребра $G$ и ребром для каждой пары ребер, имеющих общую конечную точку в $G$ .
связь: Синоним вырождения.
список: 1. Список смежности — это компьютерное представление графов для использования в графовых алгоритмах.; 2. Раскраска списком — это разновидность раскраски графа, в которой каждая вершина имеет список доступных цветов.
местный: Локальное свойство графа — это свойство, которое определяется только окрестностями вершин в графе. Например, граф локально конечен, если все его окрестности конечны.
петля: Петля или самопетля — это ребро, обе конечные точки которого являются одной и той же вершиной. Оно образует цикл длины 1. $Они$ не допускаются в простых графах.

М

увеличение: Синоним расширения вершин.
соответствие: Сопоставление — это набор ребер, в котором никакие два не имеют общих вершин. Вершина сопоставлена или насыщена, если она является одной из конечных точек ребра в сопоставлении. Идеальное сопоставление или полное сопоставление — это сопоставление, которое соответствует каждой вершине; его также можно назвать 1-фактором, и оно может существовать только при четном порядке. Почти идеальное сопоставление в графе с нечетным порядком — это сопоставление, которое насыщает все вершины, кроме одной. Максимальное сопоставление — это сопоставление, которое использует как можно больше ребер; число сопоставлений $α'(G)$ графа $G$ — это количество ребер в максимальном сопоставлении. Максимальное сопоставление — это сопоставление, к которому нельзя добавить никаких дополнительных ребер.
максимальный: 1. Подграф данного графа $G$ является максимальным для определенного свойства, если он обладает этим свойством, но никакой другой его надграф, который также является подграфом $G$ , также не обладает тем же свойством. То есть, он является максимальным элементом подграфов с этим свойством. Например, максимальная клика — это полный подграф, который не может быть расширен до большего полного подграфа. Слово «максимальный» следует отличать от слова «максимальный»: максимальный подграф всегда является максимальным, но не обязательно наоборот.; 2. Простой граф с заданным свойством является максимальным для этого свойства, если невозможно добавить к нему больше ребер (оставив набор вершин неизменным), сохраняя при этом как простоту графа, так и свойство. Таким образом, например, максимальный планарный граф — это планарный граф, такой что добавление к нему большего количества ребер создаст непланарный граф.
максимум: Подграф данного графа $G$ является максимальным для определенного свойства, если он является наибольшим подграфом (по порядку или размеру) среди всех подграфов с этим свойством. Например, максимальная клика — это любая из наибольших клик в данном графе.
медиана: 1. Медиана тройки вершин, вершина, которая принадлежит кратчайшим путям между всеми парами вершин, особенно в медианных графах и модулярных графах .; 2. Медианный граф — это граф, в котором каждые три вершины имеют уникальную медиану.
Мейниел: 1. Анри Мейниль, французский теоретик графов.; 2. Граф Мейниэля — это граф, в котором каждый нечетный цикл длины пять или более имеет по крайней мере две хорды.
минимальный: Подграф данного графа является минимальным для конкретного свойства, если он имеет это свойство, но ни один его собственный подграф также не имеет того же свойства. То есть, он является минимальным элементом подграфов со свойством.
минимальный разрез: Разрез, множество разрезов которого имеет минимальный общий вес, возможно, ограниченный разрезами, которые разделяют указанную пару вершин; они характеризуются теоремой о максимальном потоке и минимальном разрезе .
незначительный: Граф $H$ является минором другого графа $G,$ если $H$ может быть получен путем удаления ребер или вершин из $G$ и стягивания ребер в $G. Он является неглубоким минором, если его можно сформировать как минор таким образом, что подграфы G, которые были стянуты для формирования вершин H, все имеют малый диаметр. H является топологическим минором G$ $,$ если G имеет $подграф$ , $который$ является $подразделением$ H. Граф является H $-$ минор - свободным , $если$ он не имеет $H$ в качестве минора. Семейство графов является минорно-замкнутым, если оно замкнуто относительно миноров; $теорема$ Робертсона–Сеймура характеризует минорно-замкнутые семейства как имеющие конечное множество запрещенных миноров.
смешанный: Смешанный граф — это граф, который может включать как направленные, так и ненаправленные ребра.
модульный: 1. Модульный граф — граф, в котором каждая тройка вершин имеет по крайней мере одну срединную вершину, которая принадлежит кратчайшим путям между всеми парами тройки.; 2. Модульная декомпозиция — разложение графа на подграфы, в которых все вершины соединены с остальной частью графа одинаковым образом.; 3. Модульность кластеризации графа, отличие числа кросс-кластерных ребер от его ожидаемого значения.
монотонный: Монотонное свойство графов — это свойство, замкнутое относительно подграфов: если $G$ обладает монотонным свойством, то таковым должен обладать каждый подграф $G.$ Сравните наследственный (замкнутый относительно индуцированных подграфов) или минорно-замкнутый (замкнутый относительно миноров).
Граф Мура: Граф Мура — это регулярный граф, для которого граница Мура выполняется точно. Граница Мура — это неравенство, связывающее степень, диаметр и порядок графа, доказанное Эдвардом Ф. Муром . Каждый граф Мура — это клетка.
мультиграф: Мультиграф — это граф, допускающий множественные смежности (и часто самозамкнутые циклы); граф, который не обязан быть простым.
множественная смежность: Множественная смежность или множественное ребро — это набор из более чем одного ребра, которые имеют одни и те же конечные точки (в одном направлении, в случае направленных графов). Граф с несколькими ребрами часто называют мультиграфом.
множественность: Кратность ребра — это число ребер в кратной смежности. Кратность графа — это максимальная кратность любого из его ребер.

Н

Н: 1. Для обозначения открытых и закрытых окрестностей см. раздел Соседство.; 2. Строчная буква $n$ часто используется (особенно в информатике) для обозначения количества вершин в данном графе.
сосед
сосед: Вершина, смежная с данной вершиной.
район
район: Открытое соседство (или окрестность) вершины $v$ — это подграф, порождённый всеми вершинами, смежными с $v$ . Закрытое соседство определяется таким же образом, но также включает в себя сам $v . Открытое соседство$ $v$ в $G$ может быть обозначено как $NG$ $($ $v$ $)$ или $N$ $($ $v$ $)$ , а закрытое соседство может быть обозначено как $NG [$ $v$ $]$ $или$ $N$ $[$ v $]$ $.$ $Когда$ $открытость$ или замкнутость соседства не указана, оно считается открытым.
сеть: Граф, в котором атрибуты (например, имена) связаны с узлами и/или ребрами.
узел: Синоним вершины.
не-край: Неребро или антиребро — это пара вершин, которые не являются смежными; ребра дополнительного графа.
нулевой график: См. пустой график.

О

странный: 1. Нечетный цикл — это цикл, длина которого нечетна. Нечетный обхват недвудольного графа — это длина его кратчайшего нечетного цикла. Нечетная дыра — это частный случай нечетного цикла: тот, который индуцирован и имеет четыре или более вершин.; 2. Нечетная вершина — это вершина, степень которой нечетна. По лемме о рукопожатии каждый конечный неориентированный граф имеет четное число нечетных вершин.; 3. Нечетное ухо — это простой путь или простой цикл с нечетным числом ребер, используемый в разложениях на нечетные уши факторно-критических графов; см. ухо.; 4. Нечетная хорда — это ребро, соединяющее две вершины, находящиеся на нечетном расстоянии друг от друга в четном цикле. Нечетные хорды используются для определения сильно хордовых графов .; 5. Нечетный граф является частным случаем графа Кнезера , имеющим одну вершину для каждого $(n - 1)$ -элементного подмножества $(2n - 1)$ -элементного множества и ребро, соединяющее два подмножества, когда их соответствующие множества не пересекаются.
открыть: 1. Посмотрите район.; 2. См. «прогулка».
заказ: 1. Порядок графа $G$ — это число его вершин, $| V (G)|$ . Для этой величины часто используется переменная $n$ . См. также размер, число ребер.; 2. Тип логики графов ; см. первый порядок и второй порядок.; 3. Порядок или упорядочение графа — это расположение его вершин в последовательности, особенно в контексте топологического упорядочения (порядка направленного ациклического графа, в котором каждое ребро идет от более ранней вершины к более поздней вершине в порядке) и упорядочения вырожденности (порядка, в котором каждая вершина имеет минимальную степень в индуцированном ею подграфе и всех более поздних вершинах).; 4. Для заказа убежища или ежевики см. убежище и ежевика.
ориентация
ориентированный: 1. Ориентация неориентированного графа — это назначение направлений его ребрам, что делает его ориентированным графом. Ориентированный граф — это граф, которому назначена ориентация. Так, например, полидерево — это ориентированное дерево; оно отличается от ориентированного дерева (древовидной структуры) тем, что не требует согласованности направлений его ребер. Другие специальные типы ориентации включают турниры , ориентации полных графов; сильные ориентации , ориентации, которые сильно связаны; ациклические ориентации , ориентации, которые являются ациклическими; эйлеровы ориентации , ориентации, которые являются эйлеровыми; и транзитивные ориентации , ориентации, которые транзитивно замкнуты.; 2. Ориентированный граф, используемый некоторыми авторами как синоним направленного графа .
внестепенной: См. степень.
внешний: Смотри лицо.
внешнепланарный: Внешнепланарный граф — это граф, который можно вложить в плоскость (без пересечений) так, чтобы все вершины находились на внешней грани графа.

П

родитель: В корневом дереве родитель вершины $v$ является соседом $v$ по входящему ребру, направленному к корню.
путь: Путь может быть либо обходом , либо обходом без повторяющихся вершин и, следовательно, ребер (также называемым простым путем), в зависимости от источника. Важные особые случаи включают индуцированные пути и кратчайшие пути .
разложение пути: Путевое разложение графа $G$ — это древовидное разложение, базовое дерево которого является путем. Его ширина определяется так же, как и для древовидных разложений, как единица меньше размера наибольшего мешка. Минимальная ширина любого путевого разложения $G$ — это путевая ширина $G$ .
ширина пути: Ширина пути графа $G$ — это минимальная ширина путевого разложения $G.$ Она также может быть определена в терминах числа клик интервального завершения $G.$ Она всегда находится между пропускной способностью и шириной дерева $G.$ Она также известна как толщина интервала, число разделения вершин или число поиска узлов.
кулон: См. лист.
идеальный: 1. Совершенный граф — это граф, в котором в каждом индуцированном подграфе хроматическое число равно числу клики. Теорема о совершенном графе и сильная теорема о совершенном графе — это две теоремы о совершенных графах, первая из которых доказывает, что их дополнения также совершенны, а вторая — что они являются в точности графами без нечетных дыр или антидыр.; 2. Совершенно упорядочиваемый граф — это граф, вершины которого можно упорядочить таким образом, что жадный алгоритм раскраски с этим порядком оптимально раскрасит каждый индуцированный подграф. Совершенно упорядочиваемые графы являются подклассом совершенных графов.; 3. Идеальное паросочетание — это паросочетание, которое насыщает каждую вершину; см. паросочетание.; 4. Совершенная 1-факторизация — это разбиение ребер графа на совершенные паросочетания таким образом, что каждые два паросочетания образуют гамильтонов цикл.
периферийный: 1. Периферический цикл или неразделяющий цикл — это цикл с максимум одним мостом.; 2. Периферийная вершина — вершина, эксцентриситет которой максимален. В дереве это должен быть лист.
Петерсен: 1. Юлиус Петерсен (1839–1910), датский теоретик графов.; 2. Граф Петерсена — граф с 10 вершинами и 15 рёбрами, часто используемый в качестве контрпримера.; 3. Теорема Петерсена о том, что любой кубический граф без мостов имеет совершенное паросочетание.
плоский: Планарный граф — это граф, имеющий вложение на евклидовой плоскости. Плоский граф — это планарный граф, для которого определенное вложение уже зафиксировано. $K$ -планарный граф — это граф, который можно нарисовать на плоскости с максимум $k$ пересечениями на ребро.
полидерево: Полидерево — это ориентированное дерево; эквивалентно, направленный ациклический граф, базовый неориентированный граф которого является деревом.
власть: 1. Мощность графа $G k$ графа $G$ — это другой граф на том же множестве вершин; две вершины смежны в $G k$ , когда они находятся на расстоянии не более $k$ в $G$ . Мощность листа — это тесно связанное понятие, выведенное из мощности дерева путем взятия подграфа, индуцированного листьями дерева.; 2. Анализ графа мощности — это метод анализа сложных сетей путем выявления клик, биклик и звезд внутри сети.; 3. Степенные законы в распределениях степеней безмасштабных сетей представляют собой явление, при котором число вершин данной степени пропорционально мощности степени.
предшественник: Вершина, предшествующая заданной вершине на направленном пути.
основной: 1. Граф простых чисел определяется из алгебраической группы с вершиной для каждого простого числа , которое делит порядок группы.; 2. В теории модульного разложения простой граф — это граф без каких-либо нетривиальных модулей.; 3. В теории расщеплений , разрезов, множество разрезов которых является полным двудольным графом, простой граф — это граф без каких-либо расщеплений. Каждый фактор-граф максимального разложения по расщеплениям является простым графом, звездой или полным графом.; 4. Граф простых чисел для декартова произведения графов — это связный граф, который сам по себе не является произведением. Каждый связный граф может быть однозначно разложен на декартово произведение простых графов.
правильный: 1. Собственный подграф — это подграф, который удаляет по крайней мере одну вершину или ребро относительно всего графа; для конечных графов собственные подграфы никогда не изоморфны всему графу, но для бесконечных графов они могут быть изоморфны.; 2. Правильная раскраска — это назначение цветов вершинам графа (раскраска), при котором конечным точкам каждого ребра назначаются разные цвета; см. цвет.; 3. Правильный интервальный граф или правильный круговой дуговой граф — это граф пересечения набора интервалов или круговых дуг (соответственно), такой, что ни один интервал или дуга не содержит другой интервал или дугу. Правильные интервальные графы также называются единичными интервальными графами (потому что они всегда могут быть представлены единичными интервалами) или безразличными графами.
свойство: Свойство графа — это то, что может быть истинным для некоторых графов и ложным для других, и это зависит только от структуры графа, а не от случайной информации, такой как метки. Свойства графа могут быть эквивалентно описаны в терминах классов графов (графов, которые имеют данное свойство). В более общем смысле свойство графа может также быть функцией графов, которая снова независима от случайной информации, такой как размер, порядок или последовательность степеней графа; это более общее определение свойства также называется инвариантом графа.
псевдолес: Псевдолес — это неориентированный граф, в котором каждый связный компонент имеет не более одного цикла, или ориентированный граф, в котором каждая вершина имеет не более одного исходящего ребра.
псевдограф: Псевдограф — это граф или мультиграф, допускающий самозамкнутые циклы.

В

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

Р

радиус: Радиус графа — это минимальный эксцентриситет любой вершины.
Рамануджан: Граф Рамануджана — это граф, спектральное расширение которого максимально возможно. То есть, это $d$ -регулярный граф, такой, что второе по величине собственное значение его матрицы смежности не превышает . $2{\sqrt {d-1}}$
луч: Луч в бесконечном графе — это бесконечный простой путь с ровно одной конечной точкой. Концы графа — это классы эквивалентности лучей.
достижимость: Возможность перехода из одной вершины в другую внутри графа.
достижимый: Имеет утвердительную достижимость. Вершина $y$ называется достижимой из вершины $x$ , если существует путь из $x$ в $y$ .
узнаваемый: В контексте гипотезы реконструкции свойство графа распознаваемо, если его истинность может быть определена из колоды графа. Известно, что многие свойства графа распознаваемы. Если гипотеза реконструкции верна, все свойства графа распознаваемы.
реконструкция: Гипотеза реконструкции утверждает, что каждый неориентированный граф $G$ однозначно определяется своей колодой , мультимножеством графов, образованных путем удаления одной вершины из $G$ всеми возможными способами. В этом контексте реконструкция — это формирование графа из его колоды.
прямоугольник: Простой цикл, состоящий ровно из четырех ребер и четырех вершин.
обычный: Граф является $d$ -регулярным, когда все его вершины имеют степень $d$ . Регулярный граф — это граф, который является $d$ -регулярным для некоторого $d$ .
регулярный турнир: Обычный турнир — это турнир, в котором для всех вершин степень захода равна степени исхода.
обеспечить регресс: См. транспонирование.
корень: 1. Обозначенная вершина в графе, особенно в ориентированных деревьях и корневых графах .; 2. Обратная операция к степени графа : корень степени $k$ графа $G$ — это другой граф на том же множестве вершин, такой, что две вершины являются смежными в $G$ тогда и только тогда, когда они имеют расстояние не более $k$ в корне.

С

насыщенный: Смотрите соответствие.
поисковый номер: Число узлов поиска является синонимом ширины пути.
второй порядок: Логика второго порядка графов — это форма логики, в которой переменные могут представлять вершины, ребра, множества вершин и (иногда) множества ребер. Эта логика включает предикаты для проверки того, являются ли вершина и ребро инцидентными, а также принадлежат ли вершина или ребро множеству. Следует отличать от логики первого порядка, в которой переменные могут представлять только вершины.
самостоятельная петля: Синоним слова «петля».
разделяющая вершина: См. точку артикуляции.
номер разделения: Число разделительных вершин является синонимом ширины пути.
брат или сестра: В корневом дереве родственным узлом вершины $v$ является вершина, имеющая ту же родительскую вершину, что и $v$ .
простой: 1. Простой граф — это граф без петель и без множественных смежностей. То есть каждое ребро соединяет две различные конечные точки, и никакие два ребра не имеют одинаковых конечных точек. Простое ребро — это ребро, которое не является частью множественной смежности. Во многих случаях графы считаются простыми, если не указано иное.; 2. Простой путь или простой цикл — это путь или цикл, который не имеет повторяющихся вершин и, следовательно, повторяющихся ребер.
раковина: Сток в ориентированном графе — это вершина, не имеющая исходящих ребер (степень исхода равна 0).
размер: Размер графа $G$ — это число его ребер, $| E (G)|$ . ^[13] Для этой величины часто используется переменная $m . См. также$ order , число вершин.
сеть малого мира: Сеть малого мира — это граф, в котором большинство узлов не являются соседями друг друга, но большинство узлов могут быть достигнуты из любого другого узла за небольшое количество переходов или шагов. В частности, сеть малого мира определяется как граф, в котором типичное расстояние L между двумя случайно выбранными узлами (количество требуемых шагов) растет пропорционально логарифму числа узлов N в сети ^[14]
сарказм: Снарк — это простой, связный, безмостовый кубический граф с хроматическим индексом, равным 4.
источник: Источник в ориентированном графе — это вершина, не имеющая входящих ребер (степень вхождения равна 0).
космос: В алгебраической теории графов несколько векторных пространств над бинарным полем могут быть связаны с графом. Каждое из них имеет наборы ребер или вершин для своих векторов и симметричную разность множеств в качестве операции векторной суммы. Пространство ребер — это пространство всех наборов ребер, а пространство вершин — это пространство всех наборов вершин. Пространство разрезов — это подпространство пространства ребер, элементами которого являются множества разрезов графа. Пространство циклов имеет в качестве своих элементов эйлеровы остовные подграфы.
гаечный ключ: Остов — это (обычно разреженный) граф, кратчайшие расстояния которого приближаются к расстояниям в плотном графе или другом метрическом пространстве. Вариации включают геометрические остовы , графы, вершины которых являются точками в геометрическом пространстве; остовы деревьев , остовные деревья графа, расстояния которых приближаются к расстояниям графа, и остовы графов, разреженные подграфы плотного графа, расстояния которых приближаются к расстояниям исходного графа. Жадный остов — это остов графа, построенный с помощью жадного алгоритма, обычно того, который рассматривает все ребра от самого короткого до самого длинного и сохраняет те, которые необходимы для сохранения приближения расстояния.
охватывающий: Подграф является охватывающим, когда он включает все вершины данного графа. Важные случаи включают охватывающие деревья , охватывающие подграфы, которые являются деревьями, и совершенные паросочетания , охватывающие подграфы, которые являются паросочетаниями. Охватывающий подграф также может быть назван фактором , особенно (но не только), когда он является регулярным.
редкий: Разреженный граф — это граф, имеющий мало ребер относительно числа вершин. В некоторых определениях то же свойство должно быть верным для всех подграфов данного графа.
спектральный
спектр: Спектр графа — это набор собственных значений его матрицы смежности. Спектральная теория графов — это раздел теории графов, который использует спектры для анализа графов. См. также спектральное расширение.
расколоть: 1. Расщепленный граф — это граф, вершины которого можно разбить на клику и независимое множество. Связанный класс графов, двойные расщепленные графы, используются в доказательстве сильной теоремы о совершенном графе.; 2. Разбиение произвольного графа — это разбиение его вершин на два непустых подмножества, такое, что ребра, охватывающие это разрез, образуют полный двудольный подграф. Разбиения графа могут быть представлены древовидной структурой, называемой его разбиением на разбиения . Разбиение называется сильным разбиением, если оно не пересекается никаким другим разбиением. Разбиение называется нетривиальным, если обе его стороны имеют более одной вершины. Граф называется простым, если он не имеет нетривиальных разбиений.; 3. Разделение вершин (иногда называемое расщеплением вершин) — это элементарная операция графа, которая разделяет вершину на две, где эти две новые вершины являются смежными с вершинами, с которыми была смежна исходная вершина. Обратной операцией разделения вершин является стягивание вершин.
квадрат: 1. Квадрат графа $G$ — это мощность графа $G 2$ ; в обратном направлении $G$ — это квадратный корень из $G 2$ . Половина квадрата двудольного графа — это подграф его квадрата, индуцированный одной стороной двудольного графа.; 2. Квадратный граф — это планарный граф, который можно нарисовать так, чтобы все ограниченные грани были 4-циклами, а все вершины степени ≤ 3 принадлежали внешней грани.; 3. Граф квадратной сетки — это решетчатый граф, определяемый точками на плоскости с целочисленными координатами, соединенными ребрами единичной длины.
стабильный: Устойчивый набор — синоним независимого набора.
звезда: Звезда — это дерево с одной внутренней вершиной; эквивалентно, это полный двудольный граф $K 1, n$ для некоторого $n \geq 2.$ Частный случай звезды с тремя листьями называется клешней.
сила: Сила графа — это минимальное отношение числа удаленных из графа ребер к числу созданных компонентов по всем возможным удалениям; она аналогична прочности, основанной на удалениях вершин.
сильный: 1. Для сильной связности и сильно связанных компонентов направленных графов см. связанный и компонент. Сильная ориентация — это ориентация, которая сильно связана; см. ориентация.; 2. Для сильной теоремы о совершенном графе см. perfect.; 3. Сильно регулярный граф — это регулярный граф, в котором каждые две смежные вершины имеют одинаковое количество общих соседей и каждые две несмежные вершины имеют одинаковое количество общих соседей.; 4. Сильно хордальный граф — это хордовый граф, в котором каждый четный цикл длины шесть или более имеет нечетную хорду.; 5. Сильно совершенный граф — это граф, в котором каждый индуцированный подграф имеет независимое множество, встречающееся со всеми максимальными кликами. Графы Мейниэля также называются «очень сильно совершенными графами», потому что в них каждая вершина принадлежит такому независимому множеству.
подлесок: Подграф леса.
подграф: Подграф графа $G$ — это другой граф, образованный из подмножества вершин и ребер $G.$ Подмножество вершин должно включать все конечные точки подмножества ребер, но может также включать дополнительные вершины. Остовной подграф — это тот, который включает все вершины графа; индуцированный подграф — это тот, который включает все ребра, конечные точки которых принадлежат подмножеству вершин.
поддерево: Поддерево — это связный подграф дерева. Иногда для корневых деревьев поддеревья определяются как особый тип связного подграфа, образованного всеми вершинами и ребрами, достижимыми из выбранной вершины.
преемник: Вершина, следующая за заданной вершиной в направленном пути.
суперконцентратор: Суперконцентратор — это граф с двумя обозначенными и равными по размеру подмножествами вершин $I$ и $O$ , такой, что для каждых двух равных по размеру подмножеств $S$ из $I$ и $T$ $O$ существует семейство непересекающихся путей, соединяющих каждую вершину из $S$ с вершиной из $T.$ Некоторые источники дополнительно требуют, чтобы суперконцентратор был направленным ациклическим графом с $I$ в качестве его источников и $O$ в качестве его стоков.
суперграф: Граф, образованный добавлением вершин, ребер или того и другого к данному графу. Если H $является$ подграфом $G$ , то $G$ является суперграфом $H.$

Т

тета: 1. Тета-граф — это объединение трех внутренне непересекающихся (простых) путей, имеющих одни и те же две различные конечные вершины. ^[15]; 2. Тета-граф набора точек на евклидовой плоскости строится путем построения системы конусов, окружающих каждую точку, и добавления одного ребра на конус к точке, проекция которой на центральный луч конуса наименьшая.; 3. Число Ловаса или тета-функция Ловаса графа — это инвариант графа, связанный с числом клик и хроматическим числом, который может быть вычислен за полиномиальное время с помощью полуопределенного программирования.
Граф Томсена: Граф Томсена — это название полного двудольного графа . $К_{3,3}$
топологический: 1. Топологический граф — это представление вершин и ребер графа точками и кривыми на плоскости (не обязательно без пересечений).; 2. Топологическая теория графов изучает вложения графов.; 3. Топологическая сортировка — это алгоритмическая задача упорядочения ориентированного ациклического графа в топологический порядок, последовательность вершин, в которой каждое ребро идет от более ранней вершины к более поздней вершине в последовательности.
полностью отключен: Синоним слова «безграничный».
тур: Замкнутый путь, прогулка, которая начинается и заканчивается в одной и той же вершине и не имеет повторяющихся ребер. Эйлеровы туры — это туры, которые используют все ребра графа; см. Эйлеров.
турнир: Турнир — это ориентация полного графа; то есть это направленный граф, в котором каждые две вершины соединены ровно одним направленным ребром (проходящим только в одном из двух направлений между двумя вершинами) .
прослеживаемый: Трассируемый граф — это граф, содержащий гамильтонов путь.
тащить: Прогулка без повторяющихся граней.
переходный: Имеющий отношение к транзитивному свойству . Транзитивное замыкание данного ориентированного графа — это граф на том же множестве вершин, который имеет ребро из одной вершины в другую всякий раз, когда исходный граф имеет путь, соединяющий те же две вершины. Транзитивное сокращение графа — это минимальный граф, имеющий то же транзитивное замыкание; ориентированные ациклические графы имеют уникальное транзитивное сокращение. Транзитивная ориентация — это ориентация графа, которая является своим собственным транзитивным замыканием; она существует только для графов сравнимости .
транспонировать: Транспонированный граф данного ориентированного графа — это граф на тех же вершинах, в котором каждое ребро обращено по направлению. Его также можно назвать обратным или инверсным графом.
дерево: 1. Дерево — это неориентированный граф, который является одновременно связным и ациклическим, или ориентированный граф, в котором существует единственный путь от одной вершины (корня дерева) до всех оставшихся вершин.; 2. $K$ -дерево — это граф, образованный склеиванием $(k + 1)$ -клик вместе по общим $k$ -кликам. Дерево в обычном смысле — это $1$ -дерево согласно этому определению.
разложение дерева: Древовидная декомпозиция графа $G$ — это дерево, узлы которого помечены множествами вершин $G$ ; эти множества называются сумками. Для каждой вершины $v$ сумки, содержащие $v ,$ должны порождать поддерево дерева, а для каждого ребра $uv$ должен существовать сумка, содержащий как $u ,$ так и $v$ . Ширина древовидной декомпозиции на единицу меньше максимального числа вершин в любой из ее сумок; древовидная ширина $G$ — это минимальная ширина любой древовидной декомпозиции $G$ .
ширина дерева: Древесная ширина графа G $—$ это минимальная ширина древовидной декомпозиции графа $G.$ Она также может быть определена в терминах кликового числа хордового завершения графа $G$ , порядка убежища графа $G$ или порядка ежевики графа $G.$
треугольник: Цикл длины три в графе. Граф без треугольников — это неориентированный граф, не имеющий подграфов треугольников.
тривиальный: Тривиальный граф — это граф с 0 или 1 вершиной. ^[16] Граф с 0 вершинами также называется нулевым графом .
Туран: 1. Пал Туран; 2. Граф Турана — это сбалансированный полный многодольный граф.; 3. Теорема Турана утверждает, что графы Турана имеют максимальное количество ребер среди всех графов без клик заданного порядка.; 4. Задача Турана о кирпичном заводе требует нахождения минимального числа пересечений на рисунке полного двудольного графа.
близнец: Две вершины $u,v$ являются истинными близнецами, если они имеют одинаковую замкнутую окрестность: $N G [u] = N G [v]$ (это означает, что $u$ и $v$ являются соседями), и они являются ложными близнецами, если они имеют одинаковую открытую окрестность: $N G (u) = N G (v))$ (это означает, что $u$ и $v$ не являются соседями).

У

унарная вершина: В корневом дереве унарная вершина — это вершина, имеющая ровно одну дочернюю вершину.
ненаправленный: Неориентированный граф — это граф, в котором две конечные точки каждого ребра неотличимы друг от друга. См. также направленный и смешанный . В смешанном графе неориентированное ребро — это снова то, в котором конечные точки неотличимы друг от друга.
униформа: Гиперграф является $k$ -однородным, когда все его ребра имеют $k$ конечных точек, и однородным, когда он является $k$ -однородным для некоторого $k$ . Например, обычные графы — это то же самое, что и $2$ -однородные гиперграфы.
универсальный: 1. Универсальный граф — это граф, содержащий в качестве подграфов все графы в заданном семействе графов или все графы заданного размера или порядка в заданном семействе графов.; 2. Универсальная вершина (также называемая вершиной или доминирующей вершиной) — это вершина, которая смежна с каждой другой вершиной в графе. Например, графы-колеса и связные пороговые графы всегда имеют универсальную вершину.; 3. В логике графов вершина, которая универсально квантифицирована в формуле, может быть названа универсальной вершиной для этой формулы.
невзвешенный график: Граф, вершинам и рёбрам которого не назначены веса; противоположность взвешенному графу.
график полезности: Граф полезности — это название полного двудольного графа . $К_{3,3}$

В

В: См . множество вершин .
валентность: Синоним слова степень .
вершина: Вершина (множественное число вершин) — (вместе с ребрами) одна из двух основных единиц, из которых строятся графы. Вершины графов часто рассматриваются как атомарные объекты, не имеющие внутренней структуры.
вершинный срез
разделительный набор: Набор вершин, удаление которых разъединяет граф. Разрез с одной вершиной называется точкой сочленения или вершиной разреза.
набор вершин: Множество вершин данного графа $G$ , иногда обозначаемое как $V (G)$ .
вершины: См . вершина .
Визинг: 1. Вадим Григорьевич Визинг; 2. Теорема Визинга о том, что хроматический индекс не более чем на единицу больше максимальной степени.; 3. Гипотеза Визинга о доминирующем числе декартовых произведений графов.
объем: Сумма степеней множества вершин.

Вт

$Вт$: Буква $W$ используется в обозначениях графов «колесо» и «мельница» . Обозначение не стандартизировано.
Вагнер: 1. Клаус Вагнер; 2. Граф Вагнера , лестница Мёбиуса с восемью вершинами.; 3. Теорема Вагнера, характеризующая планарные графы их запрещенными минорами.; 4. Теорема Вагнера, характеризующая графы, свободные $от K 5$ -миноров.
ходить: Маршрут — это конечная или бесконечная последовательность ребер , которая соединяет последовательность вершин . Маршруты также иногда называют цепями . ^[17] Маршрут открыт , если его первая и последняя вершины различны, и закрыт , если они повторяются.
слабо связанный: Ориентированный граф называется слабосвязным, если замена всех его ориентированных ребер неориентированными ребрами дает связный (неориентированный) граф.
масса: Числовое значение, назначенное в качестве метки вершине или ребру графа. Вес подграфа — это сумма весов вершин или ребер внутри этого подграфа.
взвешенный график: Граф, вершинам или ребрам которого назначены веса. Граф с весами вершин имеет веса на своих вершинах, а граф с весами ребер имеет веса на своих ребрах.
хорошо окрашенный: Хорошо раскрашенный граф — это граф, все жадные раскраски которого используют одинаковое количество цветов.
хорошо укрытый: Хорошо покрытый граф — это граф, все максимальные независимые множества которого имеют одинаковый размер.
колесо: Граф -колесо — это граф, образованный путем добавления универсальной вершины к простому циклу.
ширина: 1. Синоним вырождения.; 2. Для других инвариантов графа, известных как ширина, см. пропускную способность, ширину ветви, ширину клики, ширину пути и ширину дерева.; 3. Ширина разложения дерева или разложения пути на единицу меньше максимального размера одного из его мешков и может использоваться для определения ширины дерева и ширины пути.; 4. Ширина направленного ациклического графа — это максимальная мощность антицепи.
ветряная мельница: Граф «ветряная мельница» представляет собой объединение набора клик, все из которых имеют одинаковый порядок, при этом одна общая вершина принадлежит всем кликам, а все остальные вершины и ребра различны.

Смотрите также

Ссылки

^ Фарбер, М.; Хан, Г.; Хелл, П.; Миллер, DJ (1986), «Относительно ахроматического числа графов», Журнал комбинаторной теории, Серия B , 40 (1): 21–39, doi : 10.1016/0095-8956(86)90062-6.
^ abcdefgh Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стайн, Клиффорд (2001), «Графы B.4», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 1080–1084.
^ Грюнбаум, Б. (1973), «Ациклические раскраски планарных графов», Израильский журнал математики , 14 (4): 390–408, doi : 10.1007/BF02764716.
^ Кормен и др. (2001), с. 529.
^ Дистель, Рейнхард (2017), "1.1 Графы", Теория графов , Graduate Texts in Mathematics, т. 173 (5-е изд.), Берлин, Нью-Йорк: Springer-Verlag, стр. 3, doi : 10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6.
^ Woodall, DR (1973), «Связующее число графа и его число Андерсона», J. Combin. Theory Ser. B , 15 (3): 225–255, doi : 10.1016/0095-8956(73)90038-5
^ ван дер Хольст, Хайн (март 2009 г.), «Алгоритм полиномиального времени для поиска вложения графа без ссылок», Журнал комбинаторной теории, Серия B , 99 (2), Elsevier BV: 512–530, doi : 10.1016/j.jctb.2008.10.002
^ Судаков, Бенни; Волек, Ян (2017), «Правильно раскрашенные и радужные копии графов с несколькими вишенками», Журнал комбинаторной теории, Серия B , 122 (1): 391–416, arXiv : 1504.06176 , doi : 10.1016/j.jctb.2016.07.001.
^ глубина, NIST
^ Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), «Глава 7: Запрещенный подграф», Классы графов: Обзор, Монографии SIAM по дискретной математике и приложениям, стр. 105–121, ISBN 978-0-89871-432-6
^ Митчем, Джон (1969), «Гипо-свойства в графах», The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, т. 110, Springer, стр. 223–230, doi :10.1007/BFb0060121, ISBN 978-3-540-04629-5, МР 0253932.
^ уровень ab , NIST
^ Харрис, Джон М. (2000), Комбинаторика и теория графов, Нью-Йорк: Springer-Verlag, стр. 5, ISBN 978-0-387-98736-1
^ Уоттс, Дункан Дж.; Строгац, Стивен Х. (июнь 1998 г.), «Коллективная динамика сетей «малого мира»», Nature , 393 (6684): 440–442, Bibcode : 1998Natur.393..440W, doi : 10.1038/30918, PMID 9623998, S2CID 4429113
^ Бонди, JA (1972), «Теория графов» греческого алфавита», Теория графов и ее приложения (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; посвящается памяти Дж. У. Т. Янга) , Lecture Notes in Mathematics, т. 303, Springer, стр. 43–54, doi :10.1007/BFb0067356, ISBN 978-3-540-06096-3, МР 0335362
^ Дистель, Рейнхард (2017), Теория графов, Graduate Texts in Mathematics, т. 173, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 2, doi : 10.1007/978-3-662-53622-3, ISBN 978-3-662-53621-6
^ "Цепь - теория графов", britannica.com , получено 25 марта 2018 г.

Найдите Приложение: Глоссарий теории графов в Викисловаре, бесплатном словаре.