Содержание
37 отношения: Клика (теория графов), Кограф, Колесо (теория графов), Путевая ширина, Птолемеев граф, Премия Фалкерсона, Порождённый путь, Порождённый подграф, Однозначно раскрашиваемый граф, Рёберный граф, Расщепляемый граф, Раскраска графов, Трапецеидальный граф, Тривиально совершенный граф, Теорема Кёнига (комбинаторика), Теорема о совершенных графах, Теорема Дилуорса, Характеризация запрещёнными графами, Хордальный граф, Цикл (теория графов), Интервальный граф, Индифферентный граф, Блоковый граф, Вполне упорядочиваемый граф, Граф сравнимости, Граф Франклина, Граф Хершеля, Граф без клешней, Граф дуг окружности, Граф перестановки, Граф Мёбиуса — Кантора, Граф единичных кругов, Граф Голднера — Харари, Гипотеза Эрдёша — Хайналя, Двудольный граф, Дистанционно-наследуемый граф, Ладейный граф.
Клика (теория графов)
Граф с 23 кликами, содержащими 1 вершину (вершины графа), 42 кликами, состоящими из 2 вершин (рёбра графа), 19 кликами, состоящими из 3 вершин (закрашенные треугольники) и двумя кликами, состоящими из 4 вершин (тёмно-синие области).Шесть рёбер не входят ни в один треугольник и 11 светло-голубых треугольников образуют максимальные клики.Две тёмно-синие 4-клики являются как наибольшими, так и максимальными, и кликовое число графа равно 4.
Посмотреть Совершенный граф и Клика (теория графов)
Кограф
Граф Турана ''T''(13,4) как пример кографа В теории графов кограф, или дополнительно сводимый граф, или свободный от P4 граф — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов.
Посмотреть Совершенный граф и Кограф
Колесо (теория графов)
В теории графов колесом Wn называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла.
Посмотреть Совершенный граф и Колесо (теория графов)
Путевая ширина
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён.
Посмотреть Совершенный граф и Путевая ширина
Птолемеев граф
Птолемеев граф Граф-''изумруд'' (или 3-веер) не птолемеев. Блоковый граф, специальный вид птолемеевых графов Три операции, с помощью которых может быть построен любой дистанционно-наследуемый граф.
Посмотреть Совершенный граф и Птолемеев граф
Премия Фалкерсона
Премия Фалкерсона вручается за выдающиеся научные статьи в области дискретной математики и спонсируется совместно (MOS) и Американским математическим обществом (AMS).
Посмотреть Совершенный граф и Премия Фалкерсона
Порождённый путь
snake-in-the-box. В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G.
Посмотреть Совершенный граф и Порождённый путь
Порождённый подграф
Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
Посмотреть Совершенный граф и Порождённый подграф
Однозначно раскрашиваемый граф
Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) ''k''-раскраску (с точностью до перестановки цветов).
Посмотреть Совершенный граф и Однозначно раскрашиваемый граф
Рёберный граф
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G. Понятие рёберного графа для данного графа настолько естественно, что независимо было введено многими авторами.
Посмотреть Совершенный граф и Рёберный граф
Расщепляемый граф
Расщепляемый граф, разделённый на клику и независимое множество. В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество.
Посмотреть Совершенный граф и Расщепляемый граф
Раскраска графов
Корректная раскраска вершин графа наименьшим набором цветов — тремя. В теории графов раскраска графов является частным случаем.
Посмотреть Совершенный граф и Раскраска графов
Трапецеидальный граф
В теории графов трапецеидальными графами называются графы пересечений трапеций, все параллельные стороны которых лежат на двух прямых.
Посмотреть Совершенный граф и Трапецеидальный граф
Тривиально совершенный граф
Построение тривиально совершенного графа из вложенных интервалов и из отношения достижимости в дереве Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик.
Посмотреть Совершенный граф и Тривиально совершенный граф
Теорема Кёнига (комбинаторика)
Пример двудольного графа с наибольшим паросочетанием (выделено голубым) и наименьшим вершинным покрытием (выделено красным), оба имеют размер шесть. В теории графов теорема Кёнига, доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах.
Посмотреть Совершенный граф и Теорема Кёнига (комбинаторика)
Теорема о совершенных графах
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно.
Посмотреть Совершенный граф и Теорема о совершенных графах
Теорема Дилуорса
Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств.
Посмотреть Совершенный граф и Теорема Дилуорса
Характеризация запрещёнными графами
Характеризация запрещёнными графами — это метод описания семейства графов или гиперграфов путём указания подструктур, которым запрещено появляться внутри любого графа в семействе.
Посмотреть Совершенный граф и Характеризация запрещёнными графами
Хордальный граф
Цикл (чёрный) с двумя хордами (зелёные). Граф хордален. Удаление любого зелёного ребра приведёт к потере хордальности. В этом случае оставшееся зелёное ребро вместе с тремя чёрными рёбрами образует цикл длины четыре без хорд.
Посмотреть Совершенный граф и Хордальный граф
Цикл (теория графов)
Граф с окрашенными рёбрами для иллюстрации пути H-A-B, замкнутого пути или обхода с повторением вершин B-D-E-F-D-C-B и цикла без повторения рёбер или вершин H-D-G-H В теории графов два типа объектов обычно называются циклами.
Посмотреть Совершенный граф и Цикл (теория графов)
Интервальный граф
Семь интервалов на прямой и соответствующий интервальный граф с семью вершинами. Интервальный граф — граф пересечений мультимножества интервалов на прямой.
Посмотреть Совершенный граф и Интервальный граф
Индифферентный граф
Индифферентный граф, образованный на множестве точек на вещественной прямой путём соединения пар, расстояние между которыми не превосходит единицы Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицу.
Посмотреть Совершенный граф и Индифферентный граф
Блоковый граф
Блоковый граф Блоковый граф (кликовое дерево) — вид неориентированного графа, в котором каждая компонента двусвязности (блок) является кликой.
Посмотреть Совершенный граф и Блоковый граф
Вполне упорядочиваемый граф
В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа.
Посмотреть Совершенный граф и Вполне упорядочиваемый граф
Граф сравнимости
В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы в некотором частичном порядке.
Посмотреть Совершенный граф и Граф сравнимости
Граф Франклина
В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.
Посмотреть Совершенный граф и Граф Франклина
Граф Хершеля
В теории графов граф Хершеля — это двудольный неориентированный граф с 11 вершинами и 18 рёбрами, наименьший негамильтонов полиэдральный граф.
Посмотреть Совершенный граф и Граф Хершеля
Граф без клешней
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
Посмотреть Совершенный граф и Граф без клешней
Граф дуг окружности
Граф дуг окружности (слева) и соответствующая модель дуг (справа). В теории графов графом дуг окружности называется граф пересечений множества дуг окружности.
Посмотреть Совершенный граф и Граф дуг окружности
Граф перестановки
В теории графов граф перестановки — это граф, вершины которого соответствуют элементам перестановки, а рёбра представляют пары элементов, следование которых стало обратным после перестановки.
Посмотреть Совершенный граф и Граф перестановки
Граф Мёбиуса — Кантора
Граф Мёбиуса — Кантора — симметричный двудольный кубический граф с 16 вершинами и 24 рёбрами, названный в честь Августа Фердинанда Мёбиуса и Зелигмана Кантора (1857—1903).
Посмотреть Совершенный граф и Граф Мёбиуса — Кантора
Граф единичных кругов
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости.
Посмотреть Совершенный граф и Граф единичных кругов
Граф Голднера — Харари
В теории графов Граф Голднера — Харари — это простой неориентированный граф с 11 вершинами и 27 рёбрами.
Посмотреть Совершенный граф и Граф Голднера — Харари
Гипотеза Эрдёша — Хайналя
Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества.
Посмотреть Совершенный граф и Гипотеза Эрдёша — Хайналя
Двудольный граф
Двудольный граф Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
Посмотреть Совершенный граф и Двудольный граф
Дистанционно-наследуемый граф
В теории графов дистанционно-наследуемый граф (или вполне сепарабельный граф) — это граф, в котором расстояния в любом связном порождённом подграфе те же самые, что и в исходном графе.
Посмотреть Совершенный граф и Дистанционно-наследуемый граф
Ладейный граф
В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы.
Посмотреть Совершенный граф и Ладейный граф