Более быстрый доступ, чем браузер!
43 отношения: Annals of Mathematics, Кактус (теория графов), Кограф, Параллельно-последовательный граф, Планарный граф, Пороговый граф, Порождённый подграф, Полный граф, Петерсеново семейство графов, Алгоритм, Алмаз (теория графов), Незацепленное вложение графа, Рёберный граф, Рёберный граф гиперграфа, Расщепляемый граф, Стягивание ребра, Совершенный граф, Тривиально совершенный граф, Теория графов, Теорема Робертсона — Сеймура, Хордальный граф, Цикл (теория графов), Минор графа, Задача Заранкиевича, Временная сложность алгоритма, Вложение графа, Внешнепланарный граф, Верхушечный граф, Граф (математика), Граф сравнимости, Граф без треугольников, Граф без клешней, Граф-звезда, Гипотеза Эрдёша — Хайналя, Глоссарий общей топологии, Гомеоморфизм графов, Древесная ширина (теория графов), Двудольный граф, Дополнение графа, Дерево (теория графов), Декомпозиция графа на ветви, Лестница (теория графов), 1-планарный граф.
Annals of Mathematics
Annals of Mathematics — выходящий раз в два месяца математический журнал, выпускаемый Принстонским университетом и Институтом перспективных исследований.
Новый!!: Характеризация запрещёнными графами и Annals of Mathematics · Узнать больше »
Кактус (теория графов)
Пример кактуса В теории графов «кактус» (иногда используется название кактусовое дерево) — это связный граф, в котором любые два простых цикла имеют не более одной общей вершины.
Новый!!: Характеризация запрещёнными графами и Кактус (теория графов) · Узнать больше »
Кограф
Граф Турана ''T''(13,4) как пример кографа В теории графов кограф, или дополнительно сводимый граф, или свободный от P4 граф — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов.
Новый!!: Характеризация запрещёнными графами и Кограф · Узнать больше »
Параллельно-последовательный граф
Операции последовательного и параллельного соединения в последовательно-параллельных графах. В теории графов параллельно-последовательные графы — это графы с двумя различными вершинами, которые называются терминальными, образованные рекурсивно с помощью двух простых операций.
Новый!!: Характеризация запрещёнными графами и Параллельно-последовательный граф · Узнать больше »
Планарный граф
Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер.
Новый!!: Характеризация запрещёнными графами и Планарный граф · Узнать больше »
Пороговый граф
Пример порогового графа. В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций.
Новый!!: Характеризация запрещёнными графами и Пороговый граф · Узнать больше »
Порождённый подграф
Порождённый подграф графа — это другой граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества.
Новый!!: Характеризация запрещёнными графами и Порождённый подграф · Узнать больше »
Полный граф
По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.
Новый!!: Характеризация запрещёнными графами и Полный граф · Узнать больше »
Петерсеново семейство графов
Петерсеново семейство. ''K''6 вверху рисунка и граф Петерсена внизу. Синие связи показывают Δ-Y или Y-Δ преобразования графов семейства. В теории графов петерсеново семейство графов — это набор из семи неориентированных графов, включающий граф Петерсена и полный граф K6.
Новый!!: Характеризация запрещёнными графами и Петерсеново семейство графов · Узнать больше »
Алгоритм
Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.
Новый!!: Характеризация запрещёнными графами и Алгоритм · Узнать больше »
Алмаз (теория графов)
Алмаз — это планарный неориентированный граф с 4 вершинами и 5 рёбрами.
Новый!!: Характеризация запрещёнными графами и Алмаз (теория графов) · Узнать больше »
Незацепленное вложение графа
Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления.
Новый!!: Характеризация запрещёнными графами и Незацепленное вложение графа · Узнать больше »
Рёберный граф
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G. Понятие рёберного графа для данного графа настолько естественно, что независимо было введено многими авторами.
Новый!!: Характеризация запрещёнными графами и Рёберный граф · Узнать больше »
Рёберный граф гиперграфа
Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение.
Новый!!: Характеризация запрещёнными графами и Рёберный граф гиперграфа · Узнать больше »
Расщепляемый граф
Расщепляемый граф, разделённый на клику и независимое множество. В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество.
Новый!!: Характеризация запрещёнными графами и Расщепляемый граф · Узнать больше »
Стягивание ребра
Стягивание ребра между помеченными вершинами. В теории графов стягивание ребра — это операция, которая удаляет ребро из графа, а до этого связанные ребром вершины сливаются в одну вершину.
Новый!!: Характеризация запрещёнными графами и Стягивание ребра · Узнать больше »
Совершенный граф
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа.
Новый!!: Характеризация запрещёнными графами и Совершенный граф · Узнать больше »
Тривиально совершенный граф
Построение тривиально совершенного графа из вложенных интервалов и из отношения достижимости в дереве Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик.
Новый!!: Характеризация запрещёнными графами и Тривиально совершенный граф · Узнать больше »
Теория графов
Граф с шестью вершинами и семью рёбрами Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов.
Новый!!: Характеризация запрещёнными графами и Теория графов · Узнать больше »
Теорема Робертсона — Сеймура
Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа) утверждает, что неориентированные графы, частично упорядоченные отношением минорности, образуют множество.
Новый!!: Характеризация запрещёнными графами и Теорема Робертсона — Сеймура · Узнать больше »
Хордальный граф
Цикл (чёрный) с двумя хордами (зелёные). Граф хордален. Удаление любого зелёного ребра приведёт к потере хордальности. В этом случае оставшееся зелёное ребро вместе с тремя чёрными рёбрами образует цикл длины четыре без хорд. В теории графов граф называется хордальным, если каждый из его циклов, имеющий четыре и более дуг, имеет хорду, которая является ребром, соединяющим две вершины, не смежные в цикле.
Новый!!: Характеризация запрещёнными графами и Хордальный граф · Узнать больше »
Цикл (теория графов)
Граф с окрашенными рёбрами для иллюстрации пути H-A-B, замкнутого пути или обхода с повторением вершин B-D-E-F-D-C-B и цикла без повторения рёбер или вершин H-D-G-H В теории графов два типа объектов обычно называются циклами.
Новый!!: Характеризация запрещёнными графами и Цикл (теория графов) · Узнать больше »
Минор графа
В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягивания рёбер.
Новый!!: Характеризация запрещёнными графами и Минор графа · Узнать больше »
Задача Заранкиевича
Задача Заранкиевича, открытая проблема в математике, задаёт вопрос о наибольшем возможном числе рёбер в двудольном графе, имеющем заданное число вершин, но не содержащего полных двудольных подграфов заданного размера.
Новый!!: Характеризация запрещёнными графами и Задача Заранкиевича · Узнать больше »
Временная сложность алгоритма
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные.
Новый!!: Характеризация запрещёнными графами и Временная сложность алгоритма · Узнать больше »
Вложение графа
Вложение графа — изучаемое в рамках топологической теории графов представление графа G на заданной поверхности \Sigma, в котором точки \Sigma ассоциируются с вершинами и простые дуги (гомеоморфные образы) ассоциируются с рёбрами таким образом, что.
Новый!!: Характеризация запрещёнными графами и Вложение графа · Узнать больше »
Внешнепланарный граф
Максимальный внешнепланарный граф и его 3-раскраска. Полный граф K4 является наименьшим планарным графом, не являющимся внешнепланарным. В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
Новый!!: Характеризация запрещёнными графами и Внешнепланарный граф · Узнать больше »
Верхушечный граф
планарным. В теории графов верхушечный граф — это граф, который можно сделать планарным удалением одной вершины.
Новый!!: Характеризация запрещёнными графами и Верхушечный граф · Узнать больше »
Граф (математика)
Неориентированный граф с шестью вершинами и семью рёбрами Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
Новый!!: Характеризация запрещёнными графами и Граф (математика) · Узнать больше »
Граф сравнимости
В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы в некотором частичном порядке.
Новый!!: Характеризация запрещёнными графами и Граф сравнимости · Узнать больше »
Граф без треугольников
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер.
Новый!!: Характеризация запрещёнными графами и Граф без треугольников · Узнать больше »
Граф без клешней
В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).
Новый!!: Характеризация запрещёнными графами и Граф без клешней · Узнать больше »
Граф-звезда
Граф-звезда ''S7'' В теории графов граф-звезда Sk — это полный двудольный граф K1,k.
Новый!!: Характеризация запрещёнными графами и Граф-звезда · Узнать больше »
Гипотеза Эрдёша — Хайналя
Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества.
Новый!!: Характеризация запрещёнными графами и Гипотеза Эрдёша — Хайналя · Узнать больше »
Глоссарий общей топологии
В этом глоссарии приведены определения основных терминов, используемых в общей топологии.
Новый!!: Характеризация запрещёнными графами и Глоссарий общей топологии · Узнать больше »
Гомеоморфизм графов
Два графа G и G' гомеоморфны, если существует изоморфизм некоторого подразделения графа G и некоторого подразделения графа G'.
Новый!!: Характеризация запрещёнными графами и Гомеоморфизм графов · Узнать больше »
Древесная ширина (теория графов)
В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом.
Новый!!: Характеризация запрещёнными графами и Древесная ширина (теория графов) · Узнать больше »
Двудольный граф
Двудольный граф Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
Новый!!: Характеризация запрещёнными графами и Двудольный граф · Узнать больше »
Дополнение графа
Граф Петерсена (слева) и его дополнение (справа). Дополнение графа (обратный граф) — граф G', имеющий то же множество вершин, что и заданный граф G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G. Формально, для простого графа G.
Новый!!: Характеризация запрещёнными графами и Дополнение графа · Узнать больше »
Дерево (теория графов)
Дерево — это связный ациклический граф.
Новый!!: Характеризация запрещёнными графами и Дерево (теория графов) · Узнать больше »
Декомпозиция графа на ветви
решётки. Показано e-разделение. Разделение, декомпозиция, и сам граф имеют ширину три. В теории графов декомпозиция на ветви неориентированного графа G — это иерархическая кластеризация рёбер графа G, представленная некорневым бинарным деревом T с рёбрами из G в качестве листьев.
Новый!!: Характеризация запрещёнными графами и Декомпозиция графа на ветви · Узнать больше »
Лестница (теория графов)
В теории графов лестница Ln — планарный неориентированный граф с 2n вершинами и n+2(n-1) рёбрами.
Новый!!: Характеризация запрещёнными графами и Лестница (теория графов) · Узнать больше »
1-планарный граф
графа Хивуда — шесть рёбер имеют единичные пересечения, а остальные 15 рёбер не пересекаются. В топологической теории графов 1-планарный граф — это граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром.
Новый!!: Характеризация запрещёнными графами и 1-планарный граф · Узнать больше »
Перенаправления здесь:
Характеризация запрещенными графами.
