Рамочный граф

В теории графов рамочным графом называется вид неориентированного графа, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани.

Источник: Википедия

Связанные понятия

В теории графов медианным графом называется неориентированный граф, в котором любые три вершины a, b, и c имеют единственную медиану — вершину m(a,b,c), которая принадлежит кратчайшим путям между каждой парой вершин a, b и c.

Подробнее: Медианный граф

В теории графов псевдолес — это неориентированный граф , в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.

Кографы открывались независимо несколькими авторами, начиная с 1970-х годов. Самые ранние упоминания можно найти у Янга, Лерчса, Зайнше и Самнера. Эти графы назывались D*-графами, наследственными графами Дейси (после работы Джеймса Дейси об ортомодулярных решётках. Смотрите работу Самнера) и графы с двумя потомками Барлета и Ури.

Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

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

Гамильто́нов граф — математический объект теории графов. Представляет собой граф (набор точек и соединяющих их линий), который содержит гамильтонов цикл. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу.

Интервальный граф — граф пересечений мультимножества интервалов на прямой. Имеет по одной вершине для каждого интервала в множестве и по ребру между каждой парой вершин, если соответствующие интервалы пересекаются.

Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.

Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое число.

Шарниром в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «точка сочленения».

Граф Аполлония — это неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.

Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.

Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.

Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.

Биполярная ориентация или st-ориентация неориентированного графа — это назначение ориентации каждому ребру (ориентации), что превращает граф в направленный ациклический граф с единственным источником s и единственном стоком t, а st-нумерация графа — это топологическая сортировка полученного ориентированного ациклического графа.

Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости.

Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования.

В теории графов графом без клешней называется граф, который не содержит порождённых подграфов, изоморфных K1,3 (клешней).

Подробнее: Граф без клешней

Число очередей графа — это инвариант графа, определённый аналогично стэковому числу (толщине книги) и использующий упорядочение FIFO (первый вошёл, первый вышел, очередь) вместо упорядочения LIFO (последним вошёл, первым вышел, стэк).

Перечислены связные 3-регулярные (кубические) простые графы с малым числом вершин.

Подробнее: Таблица простых кубических графов

Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки.

В топологической теории графов 1-планарный граф — граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром.

st-Планарный граф — это биполярная ориентация планарного графа, для которого как источник, так и сток ориентации находятся на внешней грани графа. То есть это ориентированный граф, нарисованный без пересечений на плоскости таким образом, что не имеется ориентированных циклов в графе, точно одна вершина графа не имеет входных дуг, точно одна вершина графа не имеет исходящих дуг, и обе эти две специальные вершины лежат на внешней грани графа.

В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.

Подробнее: Нечётный граф

Структурная теорема графов — это главный результат в области теории графов. Результат устанавливает глубокую и фундаментальную связь между теорией миноров графов и топологическими вложениями. Теорема была сформулирована в семнадцати статьях из серии из 23 статей Нейла Робертсона и Пола Сеймура. Доказательство теоремы очень длинно и запутано. Каварабайаши и Мохар и Ловаш провели обзор теоремы в доступном для неспециалистов виде, описав теорему и её следствия.

Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом...

В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.

Подробнее: Граф единичных кругов

Мост — ребро в теории графов, удаление которого увеличивает число компонент связности. Такие рёбра также известны как разрезающие рёбра, разрезающие дуги или перешейки. Эквивалентное определение — ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.

Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что...

В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.

Подробнее: Гипогамильтонов граф

Два-графы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».

В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева. Понятие близко также к таким понятиям, как циклический ранг ориентированных графов и высота итерации языка регулярных языков ; . Интуитивно, если древесная ширина...

В теории графов граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью).

Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в логике графов второго порядка, может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан Брюно Курселем в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.

Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.

Гипотеза Эрдёша — Фабера — Ловаса — это нерешённая проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972. Гипотеза гласит...

В вычислительной геометрии и планировании движений роботов граф видимости — это граф взаимной видимости точек пространства, обычно для множества точек и преград на евклидовой плоскости. Любая вершина в графе представляет точку пространства, а любое ребро представляет прямую видимость между точками. То есть, если отрезок прямой, соединяющий две точки пространства, не проходит через какую-либо преграду, в графе будет нарисовано ребро. Если множество точек пространства лежит на прямой, их можно понимать...

Подробнее: Граф видимости

Вложение Татта или барицентричное вложение простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение...

В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.

Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...

Алгоритм сжатия цветков (англ. Blossom algorithm) — это алгоритм в теории графов для построения наибольших паросочетаний на графах. Алгоритм разработал Джек Эдмондс в 1961 году и опубликовал в 1965 году. Если дан граф G=(V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и M максимально. Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа. В отличие от двудольного...

Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.

Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 1973 году и до сих пор является одним из самых эффективных алгоритмов поиска клик.

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.

Одновременное вложение графов — это техника визуализации двух и более различных графов на одном и том же множестве помеченных вершин, при которой избегается пересечения рёбер в каждом из графов. Пересечения между рёбрами разных графов разрешаются, не разрешается только пересечение рёбер одного графа.

В теории графов графами Пэли (названы в честь Раймонда Пэли) называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный вычет. Графы Пэли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пэли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства...

Подробнее: Граф Пэли

В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...

Подробнее: Корона (теория графов)

Панциклический граф — ориентированный или неориентированный граф, который содержит циклы всех возможных длин от трёх до числа вершин графа. Панциклические графы являются обобщением гамильтоновых графов, графов, которые имеют циклы максимальной возможной длины.

Медиана — вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.

В теории графов хорошо покрытый граф (иногда встречается название хорошо укрытый граф) — это неориентированный граф, в котором любое минимальное вершинное покрытие имеет один и тот же размер (как и любое другое минимальное вершинное покрытие). Хорошо покрытые графы определил и изучал Пламмер.

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я