Гамма-алгоритм

Гамма-алгоритм — это алгоритм плоской укладки графа и попутной проверки его на планарность.

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

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

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

Октамино — восьмиклеточные полимино, то есть плоские фигуры, состоящие из восьми равных квадратов, соединённых сторонами. С фигурами октамино, как со всеми полимино, связано много задач занимательной математики.

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

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

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

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

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

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

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

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

Задача Рамсея, задача о знакомствах среди шести человек — это математическая теорема в теории Рамсея, частный случай теоремы Рамсея.

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

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

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

Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса (иногда называемого оптимальным ветвлением).

Гептамино — семиклеточное полимино, то есть плоская фигура, состоящая из семи равных квадратов, соединённых сторонами. С фигурами гептамино, как со всеми полимино, связано много задач занимательной математики.

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

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

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

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

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

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

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

Рисование под прямыми углами (РПУ=right angle crossing, RAC) графа — это рисование, при котором вершины представлены точками, а рёбра представлены отрезками или ломаными, не более двух рёбер пересекаются в одной точке, и если два ребра пересекаются, они должны пересекаться под прямыми углами.

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

Набор плиток с самозамощением (англ. setiset) порядка n — это набор из n фигур, обычно плоских, каждая из которых допускает замощение меньшими копиями тех же n фигур. Более точно, n фигур могут быть собраны n различными способами, дающими большие копии фигур из того же набора, и коэффициент увеличения один и тот же. Рисунок 1 показывает пример для n = 4 с использованием декамино различной формы. Концепцию можно обобщить и использовать фигуры большей размерности. Название setisets дал Ли Сэллоус (англ...

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

Куб принца Руперта (англ. Prince Rupert’s cube) — самый большой куб, который может пройти через отверстие, вырезанное в единичном кубе (то есть через куб, рёбра которого имеют размер 1). Ребро куба Руперта приблизительно на 6 % длиннее, чем ребро куба, через который он проходит. Задача поиска такого куба тесно связана с задачей поиска самого большего квадрата, который полностью расположен в пределах единичного куба, и имеет аналогичное решение.

Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.

Усечённый кубооктаэдр, усечённый кубоктаэдр — полуправильный многогранник (архимедово тело) с 12 квадратными гранями, 8 гранями в виде правильного шестиугольника, 6 гранями в виде правильного восьмиугольника, 48 вершинами и 72 рёбрами. Поскольку каждая из граней многогранника имеет центральную симметрию (что эквивалентно повороту на 180°), усечённый кубооктаэдр является зоноэдром.

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

Пра́вильный двадцатичетырёхъяче́йник, или просто двадцатичетырёхъяче́йник, или икоситетрахор (от др.-греч. εἴκοσι — «двадцать», τέτταρες — «четыре» и χώρος — «место, пространство»), — один из правильных многоячейников в четырёхмерном пространстве.

Подробнее: Двадцатичетырёхъячейник

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

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

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

Граф C является накрывающим графом другого графа G, если имеется накрывающее отображение из множества вершин C в множество вершин G. Накрывающее отображение f является сюръекцией и локальным изоморфизмом — окрестность вершины v в C отображается биективно в окрестность f(v) в G.

Периферийный цикл в неориентированном графе является, интуитивно, циклом, который не отделяет любую часть графа от любой другой части. Периферийные циклы (или, как они сначала назывались, периферийные многоугольники, поскольку Тат называл циклы «многоугольниками»), первым изучал Тат и они играют важную роль в описании планарных графов и в образовании циклических пространств непланарных графов.

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

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

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

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

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

Оператор Кэнни (детектор границ Кэнни, алгоритм Кэнни) в дисциплине компьютерного зрения — оператор обнаружения границ изображения. Был разработан в 1986 году Джоном Кэнни (англ. John F. Canny) и использует многоступенчатый алгоритм для обнаружения широкого спектра границ в изображениях.

В геометрии тороидальный многогранник — это многогранник, который является также тороидом (тор с g дырами), имеющий топологический род, g, равный 1 или выше.

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

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

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

Подробнее: Центральная прямая

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

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

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

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

Подробнее: Циркулянтный граф

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