Глоссарий терминов теории графов - Glossary of graph theory terms

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

Символы

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

А

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

B

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

C

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

D

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

E

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

F

лицо: В плоский график или же вложение графа, связная компонента подмножества плоскости или поверхности вложения, не пересекающаяся с графом. Для вложения в плоскость все грани, кроме одной, будут ограниченными; единственная исключительная грань, простирающаяся до бесконечности, называется внешней гранью.
фактор: Фактор графа - это остовный подграф: подграф, который включает все вершины графа. Этот термин в основном используется в контексте обычных подграфов: $k$ -фактор - это фактор, который $k$ -обычный. В частности, $1$ -factor - это то же самое, что и идеальное соответствие. А факторно-критический граф является графом, для которого удаление любой одной вершины дает граф с $1$ -фактор.
факторизация: А факторизация графа - разбиение ребер графа на множители; а $k$ -факторизация - это разделение на $k$ -факторы. Например, $1$ -факторизация - это раскраска ребер с дополнительным свойством, что каждая вершина инцидентна ребру каждого цвета.
семья: Синоним для учебный класс.
конечный: Граф конечен, если он имеет конечное число вершин и конечное число ребер. Многие источники предполагают, что все графы конечны, не говоря об этом явно. Граф является локально конечным, если каждая вершина имеет конечное число инцидентных ребер. Бесконечный граф - это граф, который не является конечным: у него бесконечно много вершин, бесконечно много ребер или и то, и другое.
первый заказ: Первый заказ логика графиков - это форма логики, в которой переменные представляют вершины графа, и существует бинарный предикат для проверки, являются ли две вершины смежными. Следует отличать от логики второго порядка, в которой переменные также могут представлять наборы вершин или ребер.
-крышка: Для набора вершин $Икс$ , $Икс$ -flap - связный компонент индуцированного подграфа, образованный удалением $Икс$ . Терминология лоскута обычно используется в контексте убежища, функции, которые отображают небольшие наборы вершин на свои закрылки. См. Также мост цикла, который является либо лоскутом вершин цикла, либо хордой цикла.
запрещенный: А характеристика запрещенного графа - это характеристика семейства графов как графов, не имеющих некоторых других графов в качестве подграфов, индуцированных подграфов или миноров. Если $ЧАС$ является одним из графов, который не встречается как подграф, индуцированный подграф или второстепенный, то $ЧАС$ говорят, что это запрещено.
лес: А лес является неориентированным графом без циклов (несвязанное объединение некорневых деревьев) или ориентированным графом, образованным как несвязное объединение корневых деревьев.
Frucht: 1. Роберт Фрухт; 2. Программа Граф Фрухта, один из двух наименьших кубических графов без нетривиальных симметрий.; 3. Теорема Фрухта что каждая конечная группа является группой симметрий конечного графа.
полный: Синоним для индуцированный.
функциональный график: А функциональный график ориентированный граф, в котором каждая вершина имеет степень один. Эквивалентно функциональный граф - это максимально направленный псевдолес.

грамм

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

ЧАС

ЧАС: Переменная, часто используемая для обозначения графа, особенно когда другой граф уже обозначен $грамм$ .
ЧАС-крашивание: An $ЧАС$ -раскрашивание графика $грамм$ (куда $ЧАС$ также граф) является гомоморфизмом из $ЧАС$ к $грамм$ .
ЧАС-свободный: График $ЧАС$ -свободным, если в нем нет индуцированного подграфа, изоморфного $ЧАС$ , то есть если $ЧАС$ - запрещенный индуцированный подграф. В $ЧАС$ -свободные графы - это семейство всех графов (или, часто, всех конечных графов), которые $ЧАС$ -свободный.^[9] Например, графы без треугольников графы, не имеющие треугольный график как подграф. Свойство быть $ЧАС$ -free всегда передается по наследству. График $ЧАС$ -минор-свободный, если он не имеет минорного изоморфного $ЧАС$ .
Hadwiger: 1. Хьюго Хадвигер; 2. Программа Число Хадвигера графа - это порядок наибольшего полного минора графа. Его также называют сжимающим кликовым числом или степенью гомоморфизма.; 3. В Гипотеза Хадвигера - это гипотеза о том, что число Хадвигера никогда не меньше хроматического числа.
Гамильтониан: А Гамильтонов путь или гамильтонов цикл - это простой остовный путь или простой остовный цикл: он покрывает все вершины в графе ровно один раз. Граф является гамильтоновым, если он содержит гамильтонов цикл, и отслеживаемым, если он содержит гамильтонов путь.
убежище: А $k$ -убежище это функция, которая отображает каждый набор $Икс$ менее чем $k$ вершины к одной из его створок, часто удовлетворяющие дополнительным условиям согласованности. Порядок убежища - это число $k$ . Гавани можно использовать для характеристики древовидной ширины конечных графов и концов и чисел Хадвигера бесконечных графов.
высота: 1. В высота узла в корневом дереве - это количество ребер в максимальном пути, отходящем от корня (то есть его узлы имеют строго возрастающую глубину), которое начинается в этом узле и заканчивается на листе.; 2. Программа высота корневого дерева - это высота его корня. Это высота дерева - это количество ребер в максимально длинном пути, отходящем от корня, который начинается с корня и заканчивается на листе.; 3. В высота из ориентированный ациклический граф - максимальная длина ориентированного пути в этом графе.
наследственный: А наследственная собственность графов - свойство, замкнутое относительно индуцированных подграфов: если $грамм$ обладает наследственным свойством, то каждый индуцированный подграф графа $грамм$ . Сравнивать монотонный (закрыто по всем подпунктам) или минор-закрыто (закрыто для несовершеннолетних).
шестиугольник: Простой цикл, состоящий ровно из шести ребер и шести вершин.
дыра: Отверстие - это индуцированный цикл длиной четыре или более. Нечетная дыра - это дыра нечетной длины. Антидырка - это индуцированный подграф четвертого порядка, дополнением которого является цикл; эквивалентно, это дыра в дополнительном графе. Эта терминология в основном используется в контексте идеальных графов, которые характеризуются сильная теорема о совершенном графе как графики без нечетных дырок или нечетных анти-дырок. Графики без дырок такие же, как хордовые графы.
гомоморфная эквивалентность: Два графика гомоморфно эквивалентный если существует два гомоморфизма, по одному от каждого графа к другому графу.
гомоморфизм: 1. А гомоморфизм графов - это отображение множества вершин одного графа на множество вершин другого графа, которое отображает смежные вершины на соседние вершины. Этот тип отображения между графами наиболее часто используется в теоретико-категориальных подходах к теории графов. Правильная раскраска графа может быть описана как гомоморфизм полного графа.; 2. Степень гомоморфизма графа является синонимом его Число Хадвигера, порядок наибольшей клики минор.
гиперребро: Край в гиперграф, имеющий любое количество конечных точек, в отличие от требования, чтобы ребра графов имели ровно две конечные точки.
гиперкуб: А граф гиперкуба - граф, образованный из вершин и ребер геометрического гиперкуб.
гиперграф: А гиперграф является обобщением графа, в котором каждое ребро (называемое в данном контексте гиперребром) может иметь более двух конечных точек.
гипо-: Этот префикс в сочетании со свойством графа указывает на граф, который не имеет этого свойства, но такой, что каждый подграф, сформированный путем удаления одной вершины, имеет это свойство. Например, гипогамильтонов граф - это цикл, который не имеет гамильтонова цикла, но для которого каждое удаление одной вершины дает гамильтонов подграф. Сравнивать критический, используется для графов, у которых есть свойство, но у которых нет удаления каждой одной вершины.^[10]

я

в степени: Количество входящих ребер в ориентированном графе; видеть степень.
заболеваемость: An заболеваемость в графе - это пара вершина-ребро, такая что вершина является конечной точкой ребра.
матрица инцидентности: В матрица инцидентности графа - это матрица, строки которой индексируются вершинами графа, а столбцы - ребрами, с единицей в ячейке для строки $я$ и столбец $j$ когда вершина $я$ и край $j$ инцидентны, и ноль в противном случае.
инцидент: Связь между ребром и одной из его конечных точек.^[2]
несравнимость: Граф несравнимости - это дополнение к график сопоставимости; видеть сопоставимость.
независимый: 1. An независимый набор набор вершин, порождающий безреберный подграф. Его также можно назвать стабильным множеством или кокликой. В число независимости $α (грамм)$ это размер максимальный независимый набор.; 2. В графический матроид графа подмножество ребер является независимым, если соответствующий подграф является деревом или лесом. в двукруглый матроид, подмножество ребер является независимым, если соответствующий подграф является псевдолес.
равнодушие: An граф безразличия - другое название правильного графа интервалов или графа единичных интервалов; видеть правильный.
индуцированный: An индуцированный подграф или полный подграф графа - это подграф, сформированный из подмножества вершин и из всех ребер, которые имеют обе конечные точки в подмножестве. Особые случаи включают индуцированные пути и индуцированные циклы, индуцированные подграфы, которые являются путями или циклами.
индуктивный: Синоним для выродиться.
бесконечный: Бесконечный граф - это граф, который не является конечным; видеть конечный.
внутренний: Вершина пути или дерева является внутренней, если это не лист; то есть, если его степень больше единицы. Два пути внутренне не пересекаются (некоторые называют это независимый), если у них нет ни одной общей вершины, кроме первой и последней.
пересечение: 1. Пересечение двух графов - это их самый большой общий подграф, граф, образованный вершинами и ребрами, принадлежащими обоим графам.; 2. An граф пересечений - граф, вершины которого соответствуют множествам или геометрическим объектам, с ребром между двумя вершинами точно тогда, когда соответствующие два множества или объекта имеют непустое пересечение. Несколько классов графов могут быть определены как графы пересечений определенных типов объектов, например хордовые графы (графы пересечений поддеревьев дерева), круговые графики (графики пересечений хорд окружности), интервальные графики (графики пересечений отрезков прямой), линейные графики (графы пересечений ребер графа) и кликовые графы (графы пересечений максимальных клик графа). Каждый граф является графом пересечений для некоторого семейства множеств, и это семейство называется представлением пересечения графа. В номер перекрестка графа $грамм$ - минимальное общее количество элементов в любом представлении пересечения $грамм$ .
интервал: An интервальный график является граф пересечений из интервалы строки.
толщина интервала: Синоним для ширина пути.
инвариантный: Синоним ширина пути.
перевернутая стрелка: An стрелка с противоположным направление по сравнению с другой стрелкой. Стрелка $(у, Икс)$ это перевернутая стрелка стрелки $(Икс, у)$ .
изолированные: Изолированная вершина графа - это вершина с нулевой степенью, то есть вершина без инцидентных ребер.^[2]
изоморфный: Два графа изоморфны, если между ними существует изоморфизм; видеть изоморфизм.
изоморфизм: А изоморфизм графов является взаимно однозначной инцидентностью, сохраняющей соответствие вершин и ребер одного графа вершинам и ребрам другого графа. Два связанных таким образом графа называются изоморфными.
изопериметрический: Видеть расширение.
перешеек: Синоним для мост, в смысле ребра, удаление которого разъединяет граф.

K

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

L

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

M

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

N

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

О

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

п

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

Q

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

р

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

S

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

Т

тета: 1. Тета-граф - это объединение трех внутренне непересекающихся (простых) путей, которые имеют две одинаковые различные конечные вершины.^[14]; 2. Программа тета-график набора точек на евклидовой плоскости строится путем построения системы конусов, окружающих каждую точку, и добавления одного ребра на конус к точке, проекция которой на центральный луч конуса наименьшая.; 3. В Число Ловаса или тета-функция Ловаса графа - это инвариант графа, связанный с кликовым и хроматическим числом, который может быть вычислен за полиномиальное время с помощью полуопределенного программирования.
топологический: 1. А топологический граф представляет собой представление вершин и ребер графа точками и кривыми на плоскости (не обязательно избегая пересечений).; 2. Топологическая теория графов является изучением вложения графов.; 3. Топологическая сортировка - это алгоритмическая проблема упорядочивания ориентированного ациклического графа в топологический порядок, последовательность вершин так, что каждое ребро переходит от более ранней вершины к более поздней вершине в последовательности.
полностью отключен: Синоним для безграничный.
тур: Закрытая тропа, ходить который начинается и заканчивается в одной вершине и не имеет повторяющихся ребер. Эйлеровы туры - это туры, в которых используются все ребра графа; видеть Эйлеров.
турнир: А турнир - ориентация полного графа; то есть это ориентированный граф, в котором каждые две вершины соединены ровно одним направленным ребром (идущим только в одном из двух направлений между двумя вершинами).
прослеживаемый: А прослеживаемый граф - граф, содержащий гамильтонов путь.
тащить: А ходить без повторяющихся краев.
переходный: Имея дело с переходное свойство. В переходное закрытие данного ориентированного графа - это граф на том же наборе вершин, который имеет ребро от одной вершины к другой, если в исходном графе есть путь, соединяющий те же две вершины. А переходная редукция графа - это минимальный граф, имеющий такое же транзитивное замыкание; ориентированные ациклические графы имеют единственную транзитивную редукцию. А переходная ориентация ориентация графа, являющаяся его собственным транзитивным замыканием; он существует только для графики сопоставимости.
транспонировать: В транспонировать график данного ориентированного графа - это граф с теми же вершинами, каждое ребро которого перевернуто по направлению. Его также можно назвать обратным или обратным графику.
дерево: 1. А дерево является неориентированным графом, который одновременно является связным и ациклическим, или ориентированным графом, в котором существует единственный переход от одной вершины (корня дерева) ко всем остальным вершинам.; 2. А $k$ -дерево это граф, образованный склейкой $(k + 1)$ -клики вместе на общих $k$ -клики. Дерево в обычном понимании - это $1$ -дерево согласно этому определению.
разложение дерева: А разложение дерева графа $грамм$ дерево, узлы которого помечены наборами вершин $грамм$ ; эти наборы называются сумками. Для каждой вершины $v$ , пакеты, содержащие $v$ должен порождать поддерево дерева, и для каждого ребра $УФ$ должен существовать мешок, содержащий оба $ты$ и $v$ . Ширина разбиения дерева на единицу меньше максимального числа вершин в любом из его мешков; ширина дерева $грамм$ минимальная ширина любого дерева разложения $грамм$ .
ширина дерева: В ширина дерева графа $грамм$ - минимальная ширина дерева разложения $грамм$ . Его также можно определить в терминах кликового числа хордовое завершение из $грамм$ , порядок убежище из $грамм$ , или порядок ежевика из $грамм$ .
треугольник: Цикл длины три в графе. А граф без треугольников является неориентированным графом, не имеющим подграфов треугольников.
Туран: 1. Пал Туран; 2. А График Турана является сбалансированным полным многодольным графом.; 3. Теорема Турана утверждает, что графы Турана имеют максимальное количество ребер среди всех безкликовых графов данного порядка.; 4. Проблема кирпичного завода Турана запрашивает минимальное количество пересечений на чертеже полного двудольного графа.

U

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

V

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

W

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

Глоссарий терминов теории графов - Glossary of graph theory terms

Символы

А

B

C

D

E

F

грамм

ЧАС

я

K

L

M

N

О

п

Q

р

S

Т

U

V

W

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

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