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

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

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

Символы

Квадратные скобки [ ]: $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$
анти-край: Синоним non-edge — пары несмежных вершин.
антитреугольник: Трехвершинное независимое множество, дополнение треугольника.
вершина: 1. Вершинный граф — это граф, в котором можно удалить одну вершину, оставив планарный подграф. Удаленная вершина называется вершиной. Граф с $k$ -вершиной — это граф, который можно сделать плоским, удалив $k$ вершин.; 2. Синоним универсальной вершины , вершины, смежной со всеми остальными вершинами.
древовидность: Синоним укорененного и направленного дерева; увидеть дерево.
дуга: См. край.
стрелка: Упорядоченная пара вершин, например ребро ориентированного графа. Стрелка $(x, y)$ имеет хвост $x$ , головку $y$ и направление $от x к y$ ; Говорят, что $y$ является прямым преемником $x$ , а $x$ - прямым предшественником $y$ . Стрелка $(y, x)$ — это перевернутая стрелка $(x, y)$ .
точка артикуляции: Вершина связного графа, удаление которой приведет к отключению графа.
-ари: k -арное дерево — это корневое дерево, в котором каждая внутренняя вершина имеет не более $k$ дочерних элементов. Одномерное дерево — это просто путь. 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. Особенно в контексте проверки планарности мост цикла — это максимальный подграф, который не пересекается с циклом и в котором каждые два ребра принадлежат пути, который внутренне не пересекается с циклом. Аккорд – это односторонний мост. Периферический цикл — это цикл не более чем с одним мостом; это должно быть лицо в любом плоском вложении своего графа.; 3. Мостом цикла может также означать путь, соединяющий две вершины цикла, но короче любого из путей в цикле, соединяющих те же две вершины. Мостовой граф — это граф, в котором каждый цикл из четырех и более вершин имеет мост.
без моста: Граф без мостов — это граф, в котором нет мостовых ребер; то есть 2-реберно-связный граф .
бабочка: 1. Граф-бабочка имеет пять вершин и шесть ребер; он образован двумя треугольниками, имеющими общую вершину.; 2. Сеть-бабочка — это граф, используемый в качестве сетевой архитектуры в распределенных вычислениях, тесно связанный с циклами, связанными с кубом .

С

С: $Cn —$ граф циклов с $n$ -вершинами; см. цикл.
кактус: Граф кактуса , дерево кактуса, кактус или дерево Хусими — это связный граф, в котором каждое ребро принадлежит не более чем одному циклу. Его блоки представляют собой циклы или отдельные ребра. Если при этом каждая вершина принадлежит не более чем двум блокам, то он называется рождественским кактусом.
клетка: Клетка представляет собой регулярный граф с наименьшим возможным порядком обхвата.
канонический
канонизация: Каноническая форма графа — это такой инвариант, что два графа имеют равные инварианты тогда и только тогда, когда они изоморфны. Канонические формы также могут называться каноническими инвариантами или полными инвариантами и иногда определяются только для графов внутри определенного семейства графов. Канонизация графа — это процесс вычисления канонической формы.
карта: Граф, образованный из заданного графа путем удаления одной вершины, особенно в контексте гипотезы реконструкции . См. также колоду, мультинабор всех карт графа.
ширина резьбы: Ширина вырезания — это понятие ширины графа, аналогичное ширине ветвей, но с использованием иерархической кластеризации вершин вместо иерархической кластеризации ребер.
гусеница: Дерево -гусеница или гусеница — это дерево, в котором внутренние узлы образуют путь.
центр: Центр графа — это множество вершин минимального эксцентриситета.
цепь: 1. Синоним прогулки.; 2. При применении методов алгебраической топологии к графам используется элемент цепного комплекса , а именно набор вершин или набор ребер.
Константа Чигера: См. расширение.
вишня: Вишня — это путь на трёх вершинах. ^[8]
х: $χ (G)$ (с использованием греческой буквы chi) — хроматическое число $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. См. также biclique, полный двудольный подграф.
дерево клики: Синоним блочного графа.
ширина клики: Ширина клики графа $G$ — это минимальное количество различных меток, необходимое для построения $G$ с помощью операций, которые создают помеченную вершину, образуют непересекающееся объединение двух помеченных графов, добавляют ребро, соединяющее все пары вершин с заданными метками, или переименовывают все вершины с заданной меткой. Графы кликовой ширины не более $2$ являются в точности кографами .
закрыто: 1. Замкнутая окрестность — это окрестность, включающая свою центральную вершину; увидеть окрестности.; 2. Замкнутый маршрут — это маршрут, который начинается и заканчивается в одной и той же вершине; см. прогулка.; 3. Граф транзитивно замкнут, если он равен своему собственному транзитивному замыканию; см. переходный.; 4. Свойство графа является замкнутым при некоторой операции над графами, если всякий раз, когда аргумент или аргументы операции обладают этим свойством, то же самое делает и результат. Например, наследственные свойства замкнуты относительно индуцированных подграфов; монотонные свойства замкнуты относительно подграфов; и объекты, закрытые для несовершеннолетних, закрываются для несовершеннолетних.
закрытие: 1. О транзитивном замыкании ориентированного графа см. транзитив.; 2. Замыканием ориентированного графа называется множество вершин, не имеющих выходящих ребер в вершины вне замыкания. Например, сток — это замыкание с одной вершиной. Проблема замыкания — это проблема нахождения замыкания минимального или максимального веса.
со-: Этот префикс имеет различные значения, обычно связанные с графами дополнения . Например, кограф — это граф, созданный с помощью операций, включающих дополнение; раскраска — это раскраска , в которой каждая вершина индуцирует либо независимое множество (как в правильной раскраске), либо клику (как в раскраске дополнения).
цвет
раскраска: 1. Раскраска графа — это разметка вершин графа элементами заданного набора цветов или, что то же самое, разбиение вершин на подмножества, называемые «цветовыми классами», каждому из которых соответствует один из цветов.; 2. Некоторые авторы без оговорок используют термин «раскраска» для обозначения правильной раскраски, которая присваивает разные цвета концам каждого ребра. Цель раскраски графа — найти правильную раскраску, в которой используется как можно меньше цветов; например, двудольные графы — это графы, которые раскрашены только в два цвета, а теорема о четырех цветах утверждает, что каждый плоский граф можно раскрасить не более чем в четыре цвета. Граф называется $k$ -цветным, если он (должным образом) раскрашен в $k$ цветов, а также $k$ -раскрашиваемым или $k$ -хроматическим, если это возможно.; 3. Было изучено множество вариантов раскраски, включая раскраску ребер (раскраска ребер так, чтобы никакие два ребра с одинаковой конечной точкой не имели один и тот же цвет), раскраску списка (правильная раскраска, при которой каждая вершина ограничена подмножеством доступных цветов), ациклическая раскраска. (каждый двухцветный подграф ацикличен), совместная раскраска (каждый цветовой класс порождает независимое множество или клику), полная раскраска (каждые два цветовых класса имеют общее ребро) и полная раскраска (окрашены как ребра, так и вершины).; 4. Число раскраски графа равно единице плюс вырожденность . Он назван так потому, что при применении жадного алгоритма раскраски к упорядочиванию графа по вырождению используется не более указанного количества цветов.
сопоставимость: Неориентированный граф называется графом сравнимости , если его вершины являются элементами частично упорядоченного множества , а две вершины смежны, когда они сравнимы в частичном порядке. Аналогично, граф сравнимости — это граф, имеющий транзитивную ориентацию. Многие другие классы графов можно определить как графы сравнимости специальных типов частичного порядка.
дополнять: Граф дополнений простого графа $G$ — это другой граф на том же множестве вершин, что и $G$ , с ребром для каждых двух вершин, которые не являются соседними в $G.$ ${\bar {G}}$
полный: 1. Полный граф — это тот, в котором каждые две вершины смежны: все ребра, которые могли существовать, присутствуют. Полный граф с $n$ $вершинами$ часто обозначается $Kn$ . Полный двудольный граф — это такой граф, в котором каждые две вершины на противоположных сторонах разбиения вершин смежны. Полный двудольный граф с $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-фактор) для каждого удаления вершин, но (поскольку он имеет нечетное количество вершин) сам не имеет идеального паросочетания. Сравните гипо- , используемый для графов, у которых нет свойства, но для которых оно есть при каждом удалении одной вершины.
куб
кубический: 1. Граф куба , восьмивершинный граф вершин и ребер куба.; 2. Граф гиперкуба , многомерное обобщение графа куба.; 3. Граф свернутого куба , образованный из гиперкуба путем добавления паросочетания, соединяющего противоположные вершины.; 4. Граф половинного куба , полуквадрат графа гиперкуба.; 5. Частичный куб — сохраняющий расстояние подграф гиперкуба.; 6. Куб графа $G$ – это степень графа $G 3$ .; 7. Кубический граф , другое название $3$ -регулярного графа, в котором каждая вершина имеет три инцидентных ребра.; 8. Кубосвязные циклы — кубический граф, образованный заменой каждой вершины гиперкуба циклом.
резать
набор вырезок: Разрез — это разбиение вершин графа на два подмножества или набор (также известный как набор разрезов) ребер, которые охватывают такое разбиение, если это множество непусто . Говорят, что ребро охватывает раздел, если оно имеет конечные точки в обоих подмножествах. Таким образом, удаление разреза из связного графа разъединяет его.
точка разреза: См. точку артикуляции.
вырезать пространство: Пространство разреза графа представляет собой векторное пространство GF(2) , имеющее разрезные множества графа в качестве своих элементов и симметричную разность множеств в качестве операции сложения векторов.
цикл: 1. Цикл может быть либо разновидностью графа, либо разновидностью прогулки. В качестве обхода это может быть либо замкнутый обход (также называемый обходом), либо, чаще всего, замкнутый обход без повторяющихся вершин и, следовательно, ребер (также называемый простым циклом). В последнем случае его обычно рассматривают как граф, т. е. выбор первой вершины и направления обычно считают неважным; то есть циклические перестановки и обращения обхода создают один и тот же цикл. Важные специальные типы цикла включают гамильтоновы циклы , индуцированные циклы , периферийные циклы и кратчайший цикл, который определяет обхват графа. k $-$ цикл — это цикл длины $k$ ; например, $2$ -цикл — это двуугольник , а $3$ -цикл — треугольник. Граф циклов — это граф, который сам по себе является простым циклом; граф циклов с $n$ вершинами обычно обозначается $C n$ .; 2. Пространство циклов — это векторное пространство , созданное простыми циклами в графе, часто над полем из двух элементов, но также и над другими полями.

Д

ДАГ: Аббревиатура от ориентированного ациклического графа — ориентированного графа без ориентированных циклов.
палуба: Мультимножество графов формируется из одного графа $G$ путем удаления единственной вершины всеми возможными способами, особенно в контексте гипотезы реконструкции . Edge-дека формируется аналогичным образом путем удаления одного ребра всеми возможными способами. Графики в колоде также называются картами . См. также критические (графики, обладающие свойством, которым не обладает ни одна карта) и гипо- (графики, не обладающие свойством, которым обладают все карты).
разложение: См. декомпозицию дерева, декомпозицию путей или декомпозицию ветвей.
вырождаться
вырождение: k $-вырожденный$ граф — это неориентированный граф, в котором каждый индуцированный подграф имеет минимальную степень не выше $k$ . Вырожденность графа — это наименьшее $k$ , при котором он $k$ -вырожден. Упорядочение вырождения — это такое упорядочение вершин, при котором каждая вершина имеет минимальную степень в индуцированном подграфе ее и всех последующих вершин; в порядке вырождения $k$ -вырожденного графа каждая вершина имеет не более $k$ последующих соседей. Вырождение также известно как число $k$ -ядра, ширина и сцепление, а единица плюс вырождение также называется числом раскраски или числом Секереса-Вильфа. $k$ -вырожденные графы также называются $k$ -индуктивными графами.
степень: 1. Степень вершины графа — это количество инцидентных ей ребер. ^[2] Степень графа $G$ (или его максимальная степень) — это максимальная из степеней его вершин, часто обозначаемая $Δ(G)$ ; минимальная степень $G$ — это минимальная степень ее вершин, часто обозначаемая $δ (G)$ . Степень иногда называют валентностью ; степень $v$ в $G$ может обозначаться $dG (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$ , к числу вершин в S по подмножествам $S$ $,$ состоящим не более чем из половины вершин графа $G.$; 2. Расширение вершин, изопериметрическое число вершин или увеличение графа $G$ — это минимальное отношение по подмножествам $S$ , состоящим не более чем из половины вершин графа $G$ , числа вершин снаружи, но смежных с $S$ , к числу вершин в графе G. $С.$ _; 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. Гипотеза Хадвигера — это гипотеза о том, что число Хадвигера никогда не бывает меньше хроматического числа.
гамильтониан: Гамильтонов путь или гамильтонов цикл — это простой остовный путь или простой остовный цикл: он покрывает все вершины графа ровно один раз. Граф является гамильтоновым, если он содержит гамильтонов цикл, и отслеживаемым, если он содержит гамильтонов путь.
убежище: A $k$ - Haven — это функция, которая отображает каждое множество $X$ , содержащее менее $k$ вершин, в одну из своих створок, часто удовлетворяя дополнительным условиям согласованности. Порядок убежища — это число $k$ . Гавани можно использовать для характеристики ширины дерева конечных графов, а также концов и чисел Хадвигера бесконечных графов.
высота: 1. Высота узла корневого дерева — это количество ребер наибольшего пути, исходящего от корня (т. е. его узлы имеют строго возрастающую глубину), который начинается в этом узле и заканчивается листом.; 2. Высота дерева с корнями равна высоте его корня. То есть высота дерева — это количество ребер на максимально длинном пути, идущем от корня, который начинается у корня и заканчивается листом.; 3. Высота ориентированного ациклического графа — это максимальная длина ориентированного пути в этом графе.
наследственный: Наследственное свойство графов — это свойство, замкнутое относительно индуцированных подграфов: если $G$ обладает наследственным свойством, то то же самое должно быть и с каждым индуцированным подграфом $G$ . Сравните монотонные (замкнутые по всем подграфам) или минорно-закрытые (замкнутые по минорам).
шестиугольник: Простой цикл, состоящий ровно из шести ребер и шести вершин.
дыра: Дырка — это индуцированный цикл длиной четыре и более. Нечетное отверстие – это отверстие нечетной длины. Антидырка — это индуцированный подграф четвертого порядка, дополнением которого является цикл; эквивалентно, это дыра в графе дополнений. Эта терминология в основном используется в контексте идеальных графов, которые характеризуются сильной теоремой об идеальных графах как графы без нечетных дыр или нечетных антидыр. Графы без дырок аналогичны хордальным графам .
гомоморфная эквивалентность: Два графа гомоморфно эквивалентны, если существуют два гомоморфизма, по одному от каждого графа к другому графу.
гомоморфизм: 1. Гомоморфизм графа — это отображение множества вершин одного графа на множество вершин другого графа, которое отображает смежные вершины в соседние вершины. Этот тип отображения между графами чаще всего используется в теоретико-категорных подходах к теории графов. Правильную раскраску графа можно эквивалентно описать как гомоморфизм полного графа.; 2. Степень гомоморфизма графа является синонимом его числа Хадвигера — порядка наибольшего минора клики.
гипердуга: Направленное гиперребро, имеющее исходный и целевой набор.
гиперкрай: Ребро в гиперграфе, имеющее любое количество концов, в отличие от требования, чтобы ребра графа имели ровно две конечные точки.
гиперкуб: Граф гиперкуба — это граф, образованный из вершин и ребер геометрического гиперкуба .
гиперграф: Гиперграф — это обобщение графа, в котором каждое ребро (в данном контексте называемое гиперребром) может иметь более двух конечных точек.
гипо-: Этот префикс в сочетании со свойством графа указывает на граф, который не обладает этим свойством, но такой, что каждый подграф, образованный удалением одной вершины, обладает этим свойством. Например, гипогамильтонов граф — это граф, который не имеет гамильтонова цикла, но для которого каждое удаление одной вершины создает гамильтонов подграф. Сравните критический, используемый для графов, у которых есть свойство, но для которых нет каждого удаления одной вершины. ^[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$ ; см. клику.
ядро: Ядро ориентированного графа — это набор вершин, который является одновременно устойчивым и поглощающим.
морской узел: Неизбежный участок ориентированного графа. См. узел (математика) и теория узлов .

л

л: $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)$ -элементного подмножества $(2 n - 1)$ -элементного набора и ребро, соединяющее два подмножества, когда их соответствующие множества равны непересекающиеся.
открыть: 1. Увидеть окрестности.; 2. См. прогулку.
заказ: 1. Порядок графа $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. Правильный граф интервалов или правильный граф дуг окружности — это граф пересечений набора интервалов или дуг окружности (соответственно), такой, что ни один интервал или дуга не содержит другой интервал или дугу. Графы собственных интервалов также называются графами единичных интервалов (поскольку они всегда могут быть представлены единичными интервалами) или графиками безразличия.
свойство: Свойство графа — это то, что может быть истинным для некоторых графов и ложным для других, и это зависит только от структуры графа, а не от случайной информации, такой как метки. Свойства графов могут быть эквивалентным образом описаны в терминах классов графов (графов, обладающих заданным свойством). В более общем смысле, свойство графа также может быть функцией графа, которая снова не зависит от вспомогательной информации, такой как размер, порядок или последовательность степеней графа; это более общее определение свойства также называется инвариантом графа.
псевдолес: Псевдолес — это неориентированный граф, в котором каждый компонент связности имеет не более одного цикла, или ориентированный граф, в котором каждая вершина имеет не более одного исходящего ребра.
псевдограф: Псевдограф — это граф или мультиграф, допускающий циклы.

вопрос

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

р

радиус: Радиус графа — это минимальный эксцентриситет любой вершины.
Рамануджан: Граф Рамануджана — это граф, спектральное расширение которого максимально велико. То есть это $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$ — это количество его ребер, $| Е (Г) |$ . ^[13] Для этой величины часто используется переменная $m$ . См. также порядок , количество вершин.
сеть маленького мира: Сеть маленького мира — это граф, в котором большинство узлов не являются соседями друг друга, но к большинству узлов можно добраться из любого другого узла за небольшое количество переходов или шагов. В частности, сеть маленького мира определяется как граф, в котором типичное расстояние L между двумя случайно выбранными узлами (количество необходимых шагов) растет пропорционально логарифму количества узлов N в сети ^[14]
язвить: Снарк — это простой связный кубический граф без мостов с хроматическим индексом, равным 4 .
источник: Источником в ориентированном графе является вершина, не имеющая входящих ребер (входящая степень равна 0).
космос: В алгебраической теории графов с графом могут быть связаны несколько векторных пространств над бинарным полем . Каждый из них имеет наборы ребер или вершин для своих векторов, а также симметричную разность наборов в качестве операции суммирования векторов. Пространство ребер — это пространство всех наборов ребер, а пространство вершин — это пространство всех наборов вершин. Пространство разреза — это подпространство реберного пространства, элементами которого являются множества разрезов графа. Пространство циклов имеет в качестве элементов эйлеровы остовные подграфы.
гаечный ключ: Ключ — это (обычно разреженный) граф, кратчайшие расстояния которого приближаются к расстояниям в плотном графе или другом метрическом пространстве. Вариации включают геометрические гаечные ключи , графы, вершины которых являются точками в геометрическом пространстве; остовные деревья графа, расстояния которых приближаются к расстояниям графа, и остовные деревья графа, разреженные подграфы плотного графа, расстояния которых приближаются к расстояниям исходного графа. Жадный гаечный ключ — это графовый гаечный ключ, построенный с помощью жадного алгоритма, который обычно учитывает все ребра от самых коротких до самых длинных и сохраняет те, которые необходимы для сохранения аппроксимации расстояния.
охватывающий: Подграф является охватывающим, если он включает в себя все вершины данного графа. Важные случаи включают остовные деревья , охватывающие подграфы, которые являются деревьями, и идеальные паросочетания , охватывающие подграфы, которые являются сопоставлениями. Охватывающий подграф также можно назвать фактором , особенно (но не только), когда он регулярен.
редкий: Разреженный граф — это граф, у которого меньше ребер по сравнению с количеством вершин. В некоторых определениях это же свойство должно быть справедливым и для всех подграфов данного графа.
спектральный
спектр: Спектр графа — это совокупность собственных значений его матрицы смежности. Спектральная теория графов — это раздел теории графов, который использует спектры для анализа графов. См. также спектральное расширение.
расколоть: 1. Расщепляемый граф — это граф, вершины которого можно разбить на клику и независимое множество. Родственный класс графов, графы двойного расщепления, используется в доказательстве теоремы о сильном совершенном графе.; 2. Разбиением произвольного графа называется разбиение его вершин на два непустых подмножества такое, что ребра, охватывающие этот разрез, образуют полный двудольный подграф. Разбиения графа могут быть представлены древовидной структурой, называемой расщепленной декомпозицией . Раскол называется сильным расколом, если он не пересекается никаким другим расколом. Разбиение называется нетривиальным, если обе его стороны имеют более одной вершины. Граф называется простым, если он не имеет нетривиальных разбиений.
квадрат: 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$ с вершиной в $Т.$ _ Некоторые источники дополнительно требуют, чтобы суперконцентратор был ориентированным ациклическим графом с $I$ в качестве источников и $O$ в качестве приемников.
суперграф: Граф, образованный добавлением вершин, ребер или того и другого к данному графу. Если $H$ — подграф $G$ , то $G$ — суперграф $H.$

Т

тэта: 1. Тета-граф — это объединение трех внутренне непересекающихся (простых) путей, имеющих две одинаковые конечные вершины. ^[15]; 2. Тета-граф набора точек евклидовой плоскости строится путем построения системы конусов, окружающей каждую точку, и добавления одного ребра на каждый конус к точке, проекция которой на центральный луч конуса наименьшая.; 3. Число Ловаса или тета-функция Ловаса графа — это инвариант графа, связанный с кликовым числом и хроматическим числом, который можно вычислить за полиномиальное время с помощью полуопределенного программирования.
Граф Томсена: Граф Томсена — это название полного двудольного графа . $K_{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$ являются истинными близнецами, если они имеют одинаковую замкнутую окрестность: $NG$ $[u] = NG [v]$ (это означает, что $u$ и $v являются соседями), и они являются ложными близнецами, если у$ $них$ одинаковая открытая окрестность: $NG (u) = NG (v))$ (это означает, что $u$ $и$ $v$ не $являются$ соседями).

ты

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

В

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

Вт

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

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

Символы

А

Б

С

Д

Э

Ф

г

ЧАС

я

К

л

М

Н

О

п

вопрос

р

С

Т

ты

В

Вт

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

Рекомендации