Понятия со словом «раскрасить»
Связанные понятия
Теорема Грёча — это утверждение, что любой планарный граф без треугольников может быть раскрашен в три цвета. Согласно теореме о четырёх красках, для любого графа, который может быть нарисован на плоскости без пересечения рёбер, можно раскрасить его вершины не более чем в четыре различных цвета так, что любые два конца любого ребра имеют различные цвета. По теореме же Грёча достаточно лишь три цвета для планарных графов, которые не содержат трёх связанных друг с другом вершин.
Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше Δ соседей, можно раскрасить всего в Δ цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется Δ + 1 цветов.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов. Многочлен считает число раскрасок графа как функции от числа цветов. Многочлен первоначально определил Джордж Дейвид Биркгоф в попытке атаки на проблему четырёх красок. Многочлен обобщили Х. Уитни и У. Т. Тат до многочлена Тата, связав его с моделью Поттса статистической физики.
Треуго́льный парке́т (треугольный паркета́ж) или треугольная мозаика — это замощение плоскости равными правильными треугольниками, расположенными сторона к стороне.
Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Задача Рамсея, задача о знакомствах среди шести человек — это математическая теорема в теории Рамсея, частный случай теоремы Рамсея.
Шестиуго́льный парке́т (шестиугольный паркета́ж) или шестиугольная мозаика — замощение плоскости равными правильными шестиугольниками, расположенными сторона к стороне.
Пифагорова мозаика (замощение двумя квадратами) — замощение евклидовой плоскости квадратами двух различных размеров, в которой каждый квадрат касается четырёх квадратов другого размера своими четырьмя сторонами. Исходя из этой мозаики, можно доказать (наглядно) теорему Пифагора, за что мозаика и получила название пифагоровой. Мозаика часто используется в качестве узора для кафельного пола. В этом контексте мозаика известна также как узор классов.
Группа орнамента (или группа плоской симметрии, или плоская кристаллографическая группа) — это математическая классификация двумерных повторяющихся узоров, основанных на симметриях. Такие узоры часто встречаются в архитектуре и декоративном искусстве. Существует 17 возможных различных групп.
Раскраска графов находит применение и во многих практических областях, а не только в теоретических задачах. Помимо классических типов проблем, различные ограничения могут также быть наложены на граф, на способ присвоения цветов или на сами цвета. Этот метод, например, используется в популярной головоломке Судоку. В этой области всё ещё ведутся активные исследования.
Теорема о четырёх красках — теорема, которая утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке не считаются общей границей для них. Задача раскраски...
В геометрии усечённая квадратная мозаика — это полуправильные мозаики из правильных многоугольников на евклидовой плоскости с одним квадратом и двумя восьмиугольниками в каждой вершине. Это единственная мозаика из правильных выпуклых многоугольников, содержащая соприкасающиеся сторонами восьмиугольники. Символ Шлефли мозаики равен t{4,4}.
Плана́рный граф — граф, который может быть изображён на плоскости без пересечения рёбер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, то есть графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — непересекающиеся кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, так называемая внешняя грань.
В теории графов
хорошо покрытый граф (иногда встречается название хорошо укрытый граф) — это неориентированный граф, в котором любое минимальное вершинное покрытие имеет один и тот же размер (как и любое другое минимальное вершинное покрытие). Хорошо покрытые графы определил и изучал Пламмер.
Однородная мозаика может существовать как на евклидовой плоскости, так и на гиперболической плоскости. Однородные мозаики связаны с конечными однородными многогранниками, которые можно считать однородными замощениями сферы.
Пятиугольный паркет — в геометрии: замощение, составленное из выпуклых пятиугольников. Замощение из правильных пятиугольников в евклидовом пространстве невозможно, поскольку общий угол правильного пятиугольника равен 108° и не делит ни 180°, ни 360°. Однако, ими можно замостить гиперболическую плоскость и сферу.
Гипотеза Хивуда, или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, ....
В геометрии
ромбическая мозаика, кантующиеся блоки, обратимые кубы или кубическая решётка — это мозаика одинаковых ромбов с углом 60° на евклидовой плоскости. Каждый ромб имеет два угла 60° и два 120°. Такие ромбы иногда называют диамондами. Множества из трёх ромбов соприкасаются вершинами с углом 120°, а множества из шести — вершинами с углом 60°.
Теорема Галлаи – Хассе – Роя – Витавера — это вид двойственности между раскрасками вершин заданного неориентированного графа и ориентациями его рёбер. Теорема утверждает, что минимальное число красок, необходимых для правильной раскраски любого графа G, на единицу больше длины максимального пути в ориентации графа G, в которой эта длина пути минимальна. В ориентации, в которых путь максимальной длины имеет минимальную длину, всегда входит по меньшей мере одна ациклическая ориентация.
Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом...
Граф Аполлония — это неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника. Графы Аполлония можно эквивалентно определить как планарные 3-деревья, как максимальные планарные хордальные графы, как однозначно 4-раскрашиваемые планарные графы или как графы блоковых многогранников. Графы названы именем Аполлония Пергского, изучавшего связанные построения упаковки кругов.
Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из групп типа Ли, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью...
Гипотеза Эрдёша — Фабера — Ловаса — это нерешённая проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972. Гипотеза гласит...
Многоугольник Петри для правильного многогранника в размерности n — это пространственный многоугольник, такой что любые (n-1) последовательных ребра (но не n) принадлежат одной (n-1)-мерной грани.
Граф C является накрывающим графом другого графа G, если имеется накрывающее отображение из множества вершин C в множество вершин G. Накрывающее отображение f является сюръекцией и локальным изоморфизмом — окрестность вершины v в C отображается биективно в окрестность f(v) в G.
Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...
Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).
Вложение Татта или барицентричное вложение простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение...
В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...
Подробнее: Корона (теория графов)
Восходящее планарное представление направленного ациклического графа — это вложение графа в евклидово пространство, в котором рёбра представлены как непересекающиеся монотонно возрастающие кривые. То есть, кривая, представляющая любое ребро, должна иметь свойство, что любая горизонтальная прямая пересекает его максимум в одной точке, и никакие два ребра не могут пересекаться, разве что на концах. В этом смысле это идеальный случай для послойного рисования графа, стиля представления графа, в котором...
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытия.
Разметка графа в математике — это назначение меток, которые традиционно представляются целыми числами, рёбрами, вершинами, или рёбрам, и вершинам графа.
Гипотеза Тэйта утверждает, что любой 3-связный планарный кубический граф имеет гамильтонов цикл, проходящий через все его вершины. Гипотезу высказал в 1884 году П.Г. Тэйт и опровёрг в 1946 году У.Т. Татт, построив контрпример с 25 гранями, 69 рёбрами и 46 вершинами. Позднее, в 1988, Холтон и Маккей нашли меньший по размеру контрпример с 21 гранями, 57 рёбрами и 38 вершинами и показали, что этот граф минимален.
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Набор плиток с самозамощением (англ. setiset) порядка n — это набор из n фигур, обычно плоских, каждая из которых допускает замощение меньшими копиями тех же n фигур. Более точно, n фигур могут быть собраны n различными способами, дающими большие копии фигур из того же набора, и коэффициент увеличения один и тот же. Рисунок 1 показывает пример для n = 4 с использованием декамино различной формы. Концепцию можно обобщить и использовать фигуры большей размерности. Название setisets дал Ли Сэллоус (англ...
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
Куб принца Руперта (англ. Prince Rupert’s cube) — самый большой куб, который может пройти через отверстие, вырезанное в единичном кубе (то есть через куб, рёбра которого имеют размер 1). Ребро куба Руперта приблизительно на 6 % длиннее, чем ребро куба, через который он проходит. Задача поиска такого куба тесно связана с задачей поиска самого большего квадрата, который полностью расположен в пределах единичного куба, и имеет аналогичное решение.
Нигде не нулевой поток в теории графов — специальный вид сетевого потока, который связан (двойственностью) с раскраской планарных графов.
В теории графов круговой граф — это граф пересечений множества хорд окружности. То есть это неориентированный граф, вершины которого можно отождествить с хордами окружности, и эти вершины смежны тогда и только тогда, когда соответствующие хорды пересекаются.
Задача Нелсона — Эрдёша — Хадвигера — задача комбинаторной геометрии, первоначально поставленная как задача о раскраске или хроматическом числе евклидова пространства.
Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. (По теореме Визинга хроматический индекс кубического графа равен 3 или 4.) Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.
Мозаика Пенроуза, плитки Пенроуза — общее название трёх типов непериодического разбиения плоскости. Названы в честь английского математика Роджера Пенроуза, который исследовал эти разбиения в 70-х годах XX века.
Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.
В математике
абстрактный многогранник, неформально говоря, это структура, которая учитывает только комбинаторные свойства традиционных многогранников и игнорирует много других их свойств, таких как углы, длины рёбер и т. д. При этом не требуется наличие какого-либо содержащего многогранник пространства, такого как евклидово пространство. Абстрактная формулировка реализует комбинаторные свойства как частично упорядоченное множество («посет»).
В теории графов обобщёнными графами Петерсена называется семейство кубических графов, образованное соединением вершин правильного многоугольника с соответствующими вершинами звезды. В семейство входит граф Петерсена и обобщает один из путей построения графа Петерсена. Семейство обобщённых графов Петерсена ввёл в рассмотрение в 1950 году Коксетер и этим графам дал имя в 1969 году Марк Воткинс.
Подробнее: Обобщённый граф Петерсена
В теории графов нечётные графы On — это семейство симметричных графов с высоким нечётным обхватом, определённых на некоторых семействах множеств. Они включают и обобщают графы Петерсена.
Подробнее: Нечётный граф