Тотальная раскраска
В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа.
Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет.
Тотальное хроматическое число χ″(G) графа G — это наименьшее число цветов, необходимых для тотальной раскраски G.
Тотальным графом T = T(G) графа G называется граф, в котором
множество вершин графа T соответствуют вершинам и рёбрам графа G; две вершины в T смежны тогда и только тогда, когда соответствующие элементы либо смежны в G, либо инцидентны.При таком определении тотальная раскраска становится (правильной) вершинной раскраской тотального графа.
Несколько свойств χ″(G):
χ″(G) ≥ Δ(G) + 1.
χ″(G) ≤ Δ(G) + 1026.
χ″(G) ≤ Δ(G) + 8 ln8(Δ(G)) для достаточно большого Δ(G).
χ″(G) ≤ ch′(G) + 2.Здесь Δ(G) — это максимальная степень , а ch′(G) — индекс предписанной раскраски рёбер.
Тотальная раскраска возникает естественным путём, поскольку она является простым смешением вершинной и рёберной раскрасок.
Следующий шаг — это рассмотрение верхних границ тотального хроматического числа в терминах максимальной степени по аналогии с теоремами Брукса или Визинга.
Оказалось, что определение верхних границ тотальной раскраски, как функции от максимальной степени, является сложной задачей и ускользает от математиков вот уже 40 лет.
Наиболее известная догадка выглядит так:
Гипотеза о тотальной раскраске.
χ″(G) ≤ Δ(G) + 2.По всей видимости, термин «тотальная раскраска» и формулировку гипотезы независимо предложили Бехзад и Визинг в многочисленных публикациях между 1964 и 1968 годами (смотри книгу Йенсена и Тофта для деталей).
Известно, что гипотеза справедлива для нескольких важных классов графов, таких как двудольные графы и большинство планарных графов , за исключением графов с максимальной степенью 6.
Случай планарных графов будет решён, если будет доказано, что гипотеза Визинга о планарных графах верна.
Также, если гипотеза о предписанной раскраске рёбер справедлива, то χ″(G) ≤ Δ(G) + 3.
Были получены некоторые результаты относительно тотальной раскраски.
Например, Килакос и Рид доказали, что дробный хроматический индекс тотального графа для графа G не превосходит Δ(G) + 2.
Упомянем также следующую связь рёберного графа и тотального графа:
T(G) является эйлеровым в том и только в том случае, когда L(G) эйлеров .
Источник: Википедия
Связанные понятия
В теории графов двусвязный граф — это связный и неделимый граф, в том смысле, что удаление любой вершины не приведёт к потере связности. Теорема Уитни утверждает, в частности, что граф двусвязен тогда и только тогда, когда между любыми двумя его вершинами есть минимум два реберно непересекающихся пути. Таким образом, двусвязный граф не имеет шарниров.
Теорема Понтрягина — Куратовского, или теорема Куратовского, — теорема в теории графов, дающая необходимое и достаточное условие планарности графа.
Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
Срединный граф — граф, представляющий рёбра смежности внутри граней заданного планарного графа.
Преобразование треугольник-звезда — способ эквивалентного преобразования пассивного участка линейной электрической цепи — «треугольника» (соединения трёх ветвей, которое имеет вид треугольника, сторонами которого являются ветви, а вершинами — узлы), в «звезду» (соединение трёх ветвей, которые имеют один общий узел). Эквивалентность «треугольника» и «звезды» обусловлена тем, что при одинаковых напряжениях между одноименными выводами электрической цепи токи, которые втекают в одноименные выводы, а...
В теории графов рёберно-транзитивным графом называется граф G такой, что для любых двух рёбер e1 и e2 графа G, существует автоморфизм графа G, который отображает e1 в e2.
Подробнее: Рёберно-транзитивный граф
Почти многоугольник — это геометрия инцидентности, предложенная Эрнестом Е. Шультом и Артуром Янушкой в 1980. Шульт и Янушка показали связь между так называемыми тетраэдрально замкнутыми системами прямых в евклидовых пространствах и классом геометрий точка/прямая, которые они назвали почти многоугольниками. Эти структуры обобщают нотацию обобщённых многоугольников, поскольку любой обобщённый 2n-угольник является почти 2n-угольником определённого вида. Почти многоугольники интенсивно изучались, а...
Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик. Тривиально совершенные графы первым изучал Волк, но название дал Голумбик. Голумбик писал, что «это название было выбрано ввиду тривиальности доказательства, что такие графы являются совершенными.» Тривиально совершенные графы известны также как графы сравнимости деревьев, древовидные графы сравнимости и квазипороговые графы...
Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами. Много естественных семейств редких графов имеют ограниченное расширение. Близкое, но более сильное свойство, полиномиальное расширение, эквивалентно существованию теорем разбиения для этих семейств. Семейства с этими свойствами имеют эффективные алгоритмы для задач, в которые входят задача поиска изоморфного подграфа и проверка моделей для теории первого порядка для графов...
Подробнее: Ограниченное расширение графа
Флаг в геометрии многогранников — последовательность граней (различной размерности) абстрактного многогранника, в которой каждая предыдущая грань содержится в последующей и последовательность содержит ровно по одной грани каждой размерности.
Перечисление графов — категория задач перечислительной комбинаторики, в которых нужно пересчитать неориентированные или ориентированные графы определённых типов, как правило, в виде функции от числа вершин графа. Эти задачи могут быть решены либо точно (как задача алгебраического перечисления) или асимптотически.
Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины.
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.
Подробнее: Граф единичных кругов
Бабочка имеет диаметр 2 и обхват 3, радиус 1, хроматическое число 3, хроматический индекс 4 и является как эйлеровым, так и графом единичных расстояний. Граф является вершинно 1-связным графом и рёберно 2-связным.
Лексикографический поиск в ширину (англ. lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа. Алгоритм отличается от алгоритма поиска в ширину и дает более упорядоченную последовательность вершин графа.
Связное доминирующее множество и остовное дерево с максимальной листвой являются двумя тесно связанными структурами, определёнными на неориентированном графе.
В теории графов ежевикой для неориентированного графа G называется семейство связных подграфов графа G, которые касаются друг друга: для любой пары подграфов, не имеющих общих вершин, должно существовать ребро, конечные вершины которого лежат в этих двух подграфах. Порядок ежевики — это наименьший размер множества вершин G, которое имеет непустое пересечение с каждым подграфом ежевики. Ежевики используются для описания древесной ширины графа G.
Подробнее: Ежевика (теория графов)
В теории графов свободный от t-биклик граф — это граф, в котором нет полных двудольных графов с 2t вершинами Kt,t в качестве подграфов. Семейство графов является свободным от биклик, если существует число t, такое, что все графы в семействе свободны от t-биклик. Семейства свободных от бициклов графов образуют одно из наиболее общих типов семейств разреженных графов. Они возникают в задачах инцидентности в комбинаторной геометрии, а также используются в теории параметрической сложности.
Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению...
Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.
(Топологический)
индекс Хосойи , известный также как Z индекс, графа — это полное число паросочетаний на нём. Индекс Хосойи всегда больше либо равен одному, поскольку пустое множество рёбер считается как паросочетание. Эквивалентно, индекс Хосойи — это число непустых паросочетаний плюс один.
В геометрии правильный косой многогранник — это обобщение множества правильных многогранников, которое включает возможность непланарных граней или вершинных фигур. Коксетер рассматривал косые вершинные фигуры, которые создавали новые четырёхмерные правильные многогранники, а много позднее Бранко Грюнбаум рассматривал правильные косые грани.
Гипотезы Вейля — математические гипотезы о локальных дзета-функциях проективных многообразий над конечными полями.
Апейрогон (от др.-греч. ἄπειρος — бесконечный или безграничный и др.-греч. γωνία — угол) — обобщённый многоугольник со счётно-бесконечным числом сторон.
В геометрии
домино замощение области в евклидовой плоскости — это мозаика области плитками домино, образованными объединением двух единичных квадратов, соединённых по ребру. Эквивалентно это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.
Степень трансцендентности расширения поля в общей алгебре — это величина, которая даёт грубую оценку «масштаба» расширения. Другими словами, чем больше степень трансцендентности, тем больше расширенное поле содержит трансцендентных (то есть, неалгебраических по отношению к исходному полю) элементов.
В общей алгебре,
поле k называется совершенным если выполняется одно из следующих эквивалентных условий...
Геометрический род — это базовый бирациональный инвариант pg алгебраических многообразий и комплексных многообразий.
Вну́тренность множества в общей топологии — это совокупность всех внутренних точек. Обычно обозначается Int, вероятно, от англ. Interior. Иногда внутренность множества называют ядром.
Группа Григорчука — первый пример конечнопорождённой группы промежуточного роста (то есть её рост быстрее полиномиального, но медленнее экспоненциального).
Максимальным идеалом коммутативного кольца называется всякий собственный идеал кольца, не содержащийся ни в каком другом собственном идеале.
Подробнее: Максимальный идеал
Область главных идеалов — это область целостности, в которой любой идеал является главным. Более общее понятие — кольцо главных идеалов, от которого не требуется целостности (однако некоторые авторы, например Бурбаки, ссылаются на кольцо главных идеалов как на целостное кольцо).
Теорема о четырёх вершинах утверждает, что функция кривизны простой замкнутой гладкой плоской кривой имеет по меньшей мере четыре локальных экстремума (в частности, по меньшей мере два локальных максимума и по меньшей мере два локальных минимума). Название теоремы отражает соглашение называть экстремальные точки функции кривизны вершинами.
Единичный отрезок — величина, принимаемая за единицу при геометрических построениях. При изображении декартовой системы координат, единичный отрезок обычно отмечается на каждой из осей.
Дискре́тное простра́нство в общей топологии и смежных областях математики — это пространство, все точки которого изолированы друг от друга в некотором смысле.
Синглетон — множество с единственным элементом. Например, множество {0} является синглетоном.
Теорема существования — утверждение, которое устанавливает, при каких условиях существует решение математической задачи или математический объект, например производная, неопределенный интеграл, определенный интеграл, решение уравнения и т. д. При доказательстве теорем существования используются сведения из теории множеств. Теоремы существования играют очень важную роль в различных приложениях математики, например при математическом моделировании различных явлений и процессов. Математическая модель...
Недезаргова плоскость — это проективная плоскость, не удовлетворяющая теореме Дезарга, другими словами, не являющаяся дезарговой. Теорема Дезарга верна во всех проективных пространств размерности, не равной 2, то есть, для всех классических проективных геометрий над полем (или телом), но Гильберт обнаружил, что некоторые проективные плоскости не удовлетворяют теореме.
Направленное множество в математике — непустое множество A с заданным на нем рефлексивным транзитивным отношением ≤ (то есть предпорядком), обладающее дополнительным свойством: у любой пары элементов из A есть верхняя грань в A.
В теории графов
теорема о раскраске дорог, известная до недавнего времени как гипотеза о раскраске дорог, имеет дело с инструкциями синхронизации. Задача ставится в нахождении таких инструкций, чтобы независимо от начального положения объекта можно было бы дойти до пункта назначения в сети (которая может представлять собой улицы города или лабиринт). В реальном мире можно данную задачу представить как набор инструкций для вашего друга, по которым он может добраться до вашего дома независимо от того...
Многогранник, многоугольник или мозаика является изотоксальным или рёберно транзитивным, если его симметрии действуют транзитивно на его рёбрах. Неформально это означает, что имеется только один вид рёбер у объекта — если даны два ребра, существует параллельный перенос, вращение и/или зеркальное отражение, переводящее одно ребро в другое, не меняя область, занимаемую объектом.
Подробнее: Изотоксальная фигура
Аддитивная энергия — численная характеристика подмножества группы, иллюстрирующая структурированность множества относительно групповой операции.
Абсолютная непрерывность — в математическом анализе, свойство функций и мер, состоящее, неформально говоря, в выполнении теоремы Ньютона — Лейбница о связи между интегрированием и дифференцированием.
Лемма о вложенных отрезках , или принцип вложенных отрезков Коши — Кантора, или принцип непрерывности Кантора — фундаментальное утверждение в математическом анализе, связанное с полнотой поля вещественных чисел.
В коммутативной алгебре, дробный идеал — это обобщение понятия идеала целостного кольца, особенно полезное при изучении дедекиндовых колец. Условно говоря, дробные идеалы — это идеалы со знаменателями. В случаях, когда одновременно обсуждаются дробные и обычные идеалы, последние называют целыми идеалами.
В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций...
В теории графов
число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.