Содержание
101 отношения: NP-полная задача, Кубический граф, Кривая моментов, Кликовая ширина, Книжное вложение, Кнезеровский граф, Кограф, Конфигурация прямых, Псевдолес, Путевая ширина, Прямое произведение графов, Практическое применение раскраски графов, Построение Хайоша, Полная раскраска, Ограниченное расширение графа, Однозначно раскрашиваемый граф, Окрестность (теория графов), Ациклическая ориентация, Алгоритм Брона — Кербоша, Алгебраическая теория графов, Нигде не нулевой поток, Незацепленное вложение графа, Нейронная сеть Кохонена, Расщепляемый граф, Разбиение графа, Степень графа, Слабая раскраска, Снарк «Цветок», Снарк Секереша, Снарк Уоткинса, Снарк Блануши, Трёхцветная раскраска (теория узлов), Тривиально совершенный граф, Теорема Курселя, Теорема Шнайдера, Теорема де Брёйна — Эрдёша (теория графов), Теорема о совершенных графах, Теорема о раскраске дорог, Теорема Брукса, Теорема Галлаи — Хассе — Роя — Витавера, Теорема Дилуорса, Удовлетворение ограничений, Фактор-критический граф, Хроматический многочлен, Число Хадвигера, Число очередей графа, Число Ловаса, Яннакакис, Михалис, Марков, Александр Александрович (математик), Минор графа, ... Развернуть индекс (51 больше) »
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Посмотреть Раскраска графов и NP-полная задача
Кубический граф
Граф Петерсена является кубическим. Полный двудольный граф K_3,3 является примером бикубического графа Кубический граф — граф, в котором все вершины имеют степень три.
Посмотреть Раскраска графов и Кубический граф
Кривая моментов
Кривая моментов — это алгебраическая кривая в d-мерном евклидовом пространстве, заданная множеством точек с декартовыми координатами На евклидовой плоскости кривая моментов — это парабола, а в трёхмерном пространстве —.
Посмотреть Раскраска графов и Кривая моментов
Кликовая ширина
дистанционно-наследуемуего графа кликовой ширины 3 путём несвязного объединения, переименования вершин и объединения меток. Метки вершин показаны цветом. В теории графов кликовая ширина графа G — это параметр, который описывает структурную сложность графа.
Посмотреть Раскраска графов и Кликовая ширина
Книжное вложение
планарен, его невозможно вложить без пересечения в меньшее число страниц, так что книжная толщина графа равна трём. В теории графов книжное вложение является обобщением планарного вложения графа до вложения в книгу, набор полуплоскостей, имеющих одну и ту же прямую в качестве границы.
Посмотреть Раскраска графов и Книжное вложение
Кнезеровский граф
Кнезеровский граф KG_ — это неориентированный граф, описывающий отношение непересекаемости k-элементных подмножеств n-элементного множества друг с другом.
Посмотреть Раскраска графов и Кнезеровский граф
Кограф
Граф Турана ''T''(13,4) как пример кографа В теории графов кограф, или дополнительно сводимый граф, или свободный от P4 граф — это граф, который можно получить из графа с единственной вершиной K1 путём операций дополнения и объединения графов.
Посмотреть Раскраска графов и Кограф
Конфигурация прямых
Симплициальная конфигурация прямых (слева) и простая конфигурация прямых (справа). Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.
Посмотреть Раскраска графов и Конфигурация прямых
Псевдолес
1-лес (максимальный псевдолес), образованный тремя 1-деревьями В теории графов псевдолес — это неориентированный граф Неориентированные графы, рассматриваемые здесь, являются мультиграфами или псевдографами, а не простыми графами.
Посмотреть Раскраска графов и Псевдолес
Путевая ширина
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён.
Посмотреть Раскраска графов и Путевая ширина
Прямое произведение графов
Декартово произведение графов. Декартово произведение или прямое произведение G \square H графов G и H — это граф, такой, что.
Посмотреть Раскраска графов и Прямое произведение графов
Практическое применение раскраски графов
Раскраска графов практически применяется (постановка задачи различных раскрасок здесь обсуждаться не будет) для.
Посмотреть Раскраска графов и Практическое применение раскраски графов
Построение Хайоша
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Посмотреть Раскраска графов и Построение Хайоша
Полная раскраска
графа Клебша восемью цветами. Каждая пара цветов появляется по меньшей мере на одном ребре. Никаких полных раскрасок с большим числом цветов не существует — при любой раскраске в 9 цветов некоторые цвета могут появиться только на одной вершине, и соседних вершин не хватит, чтобы вовлечь все пары цветов.
Посмотреть Раскраска графов и Полная раскраска
Ограниченное расширение графа
Говорят, что семейство графов имеет ограниченное расширение, если все его миноры ограниченной глубины являются редкими графами.
Посмотреть Раскраска графов и Ограниченное расширение графа
Однозначно раскрашиваемый граф
Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) ''k''-раскраску (с точностью до перестановки цветов).
Посмотреть Раскраска графов и Однозначно раскрашиваемый граф
Окрестность (теория графов)
В теории графов смежной вершиной вершины v называется вершина, соединённая с v ребром.
Посмотреть Раскраска графов и Окрестность (теория графов)
Ациклическая ориентация
ацикличен. Две ориентации на рисунке смежны, если отличаются лишь одним ребром. Ациклическая ориентация неориентированного графа — это назначение направлений каждому ребру, при которой не образуется какого-либо ориентированного цикла, а потому такая ориентация превращает граф в направленный ациклический граф.
Посмотреть Раскраска графов и Ациклическая ориентация
Алгоритм Брона — Кербоша
Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа.
Посмотреть Раскраска графов и Алгоритм Брона — Кербоша
Алгебраическая теория графов
симметрической группой S_5. Алгебраическая теория графов — это ветвь математики, в которой применяются алгебраические методы к задачам с графами.
Посмотреть Раскраска графов и Алгебраическая теория графов
Нигде не нулевой поток
Нигде не нулевой поток в теории графов — специальный вид сетевого потока, который связан (двойственностью) с раскраской планарных графов.
Посмотреть Раскраска графов и Нигде не нулевой поток
Незацепленное вложение графа
Незацепленное вложение графа — вложение неориентированного графа в евклидово пространство, при котором никакие два цикла графа не имеют ненулевой коэффициент зацепления.
Посмотреть Раскраска графов и Незацепленное вложение графа
Нейронная сеть Кохонена
Нейронные сети Кохонена — класс нейронных сетей, основным элементом которых является слой Кохонена.
Посмотреть Раскраска графов и Нейронная сеть Кохонена
Расщепляемый граф
Расщепляемый граф, разделённый на клику и независимое множество. В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество.
Посмотреть Раскраска графов и Расщепляемый граф
Разбиение графа
параллельных вершин Разбиение графа на подграфы (Graph partition) (иногда в литературе также употребляется термин разрезание графа) — представление исходного графа G.
Посмотреть Раскраска графов и Разбиение графа
Степень графа
Квадрат графа Степень k (записывается Gk) неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k.
Посмотреть Раскраска графов и Степень графа
Слабая раскраска
Слабая 2-раскраска. Слабая раскраска — это специальный вид разметки графа.
Посмотреть Раскраска графов и Слабая раскраска
Снарк «Цветок»
В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.
Посмотреть Раскраска графов и Снарк «Цветок»
Снарк Секереша
Снарк Секереша — снарк с 50 вершинами и 75 рёбрами, пятый известный снарк.
Посмотреть Раскраска графов и Снарк Секереша
Снарк Уоткинса
В теории графов снарк Уоткинса — снарк с 50 вершинами и 75 рёбрами.
Посмотреть Раскраска графов и Снарк Уоткинса
Снарк Блануши
Снарк Блануши — 3-регулярный граф с 18 вершинами и 27 рёбрами.
Посмотреть Раскраска графов и Снарк Блануши
Трёхцветная раскраска (теория узлов)
трилистник. В теории узлов раскрашиваемость в три цвета узла — это возможность раскрасить узел в три цвета, придерживаясь определённых правил.
Посмотреть Раскраска графов и Трёхцветная раскраска (теория узлов)
Тривиально совершенный граф
Построение тривиально совершенного графа из вложенных интервалов и из отношения достижимости в дереве Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального (по размеру) независимого множества равен числу максимальных клик.
Посмотреть Раскраска графов и Тривиально совершенный граф
Теорема Курселя
Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в второго порядка, может быть установлено за линейное время на графах с ограниченной древесной шириной.
Посмотреть Раскраска графов и Теорема Курселя
Теорема Шнайдера
Теорема Шнайдера — это описание планарных графов в терминах его.
Посмотреть Раскраска графов и Теорема Шнайдера
Теорема де Брёйна — Эрдёша (теория графов)
Теорема де Брёйна — Эрдёша, которую доказали Пол Эрдёш и Николаас де Брёйн, утверждает, что хроматическое число бесконечного графа, если это число конечно, равно наибольшему хроматическому числу среди всех его конечных подграфов.
Посмотреть Раскраска графов и Теорема де Брёйна — Эрдёша (теория графов)
Теорема о совершенных графах
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно.
Посмотреть Раскраска графов и Теорема о совершенных графах
Теорема о раскраске дорог
В теории графов теорема о раскраске дорог, известная до недавнего времени как гипотеза о раскраске дорог, имеет дело с инструкциями синхронизации.
Посмотреть Раскраска графов и Теорема о раскраске дорог
Теорема Брукса
полных графов требуется на единицу больше цветов, чем их максимальная степень. Эти графы и нечётные циклы являются единственными исключениями для теоремы Брукса. Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом.
Посмотреть Раскраска графов и Теорема Брукса
Теорема Галлаи — Хассе — Роя — Витавера
Orientation (graph theory) цикла с 5 вершинами, показывающие максимальные ацикличные подграфы каждой ориентации (сплошные дуги) и раскраска вершин по длине максимального входящего пути в этом подграфе.
Посмотреть Раскраска графов и Теорема Галлаи — Хассе — Роя — Витавера
Теорема Дилуорса
Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств.
Посмотреть Раскраска графов и Теорема Дилуорса
Удовлетворение ограничений
Одной из важных задач искусственного интеллекта (ИИ) является задача удовлетворения ограничений (УО) (constraint satisfaction problem).
Посмотреть Раскраска графов и Удовлетворение ограничений
Фактор-критический граф
наибольшими паросочетаниями подграфов, полученных удалением одной из вершин. Фактор-критический граф (или почти сочетаемый граф.) — это граф с вершинами, в котором каждый подграф с вершинами имеет совершенное паросочетание.
Посмотреть Раскраска графов и Фактор-критический граф
Хроматический многочлен
Все неизоморфные графы с 3 вершинами и их хроматические многочлены, по часовой стрелке сверху. Независимое 3-множество: k^3. Ребро и одна вершина: k^2(k-1). 3-путь: k(k-1)^2. 3-клика: k(k-1)(k-2).
Посмотреть Раскраска графов и Хроматический многочлен
Число Хадвигера
теореме Вагнера граф не имеет пятивершинного полного минора, так что число Хадвигераэтого графа равно четырём. В теории графов число Хадвигера неориентированного графа G — это размер наибольшего полного графа, который может быть получен стягиванием рёбер графа G.
Посмотреть Раскраска графов и Число Хадвигера
Число очередей графа
Граф де Брёйна. Для приведённого упорядочения деление рёбер на два множества, идущих слева и справа от вершин, является схемой 2 очередей этого графа. Число очередей графа — это инвариант графа, определённый аналогично стэковому числу (толщине книги) и использующий упорядочение FIFO (первый вошёл, первый вышел, очередь) вместо упорядочения LIFO (последним вошёл, первым вышел, стэк).
Посмотреть Раскраска графов и Число очередей графа
Число Ловаса
Число Ловаса графа — вещественное число, которое является верхней границей графа.
Посмотреть Раскраска графов и Число Ловаса
Яннакакис, Михалис
Миха́лис Яннака́кис (Μιχάλης Γιαννακάκης, Mihalis Yannakakis; род. 13 сентября 1953, Афины, Греция) — греческий учёный в области компьютерных наук, профессор Колумбийского университета (Нью-Йорк, США).
Посмотреть Раскраска графов и Яннакакис, Михалис
Марков, Александр Александрович (математик)
Александр Александрович Марков (24 марта 1937, Горький — 23 октября 1994, Нижний Новгород) — советский, российский; доктор физико-математических наук, профессор; специалист в области теории кодирования, автор теории алфавитного кодирования, учитывающей структурные модели языков сообщений.
Посмотреть Раскраска графов и Марков, Александр Александрович (математик)
Минор графа
В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягивания рёбер.
Посмотреть Раскраска графов и Минор графа
Многочлен Тата
bull graph. Красная линия показывает пересечение с плоскостью y.
Посмотреть Раскраска графов и Многочлен Тата
Многодольный граф
k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (доль).
Посмотреть Раскраска графов и Многодольный граф
Мельница (теория графов)
В теории графов «мельница» Wd(k,n) — это неориентированный граф, построенный для k ≥ 2 и n ≥ 2 путём объединения n копий полных графов Kk в одной общей вершине.
Посмотреть Раскраска графов и Мельница (теория графов)
Индифферентный граф
Индифферентный граф, образованный на множестве точек на вещественной прямой путём соединения пар, расстояние между которыми не превосходит единицы Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицу.
Посмотреть Раскраска графов и Индифферентный граф
Жадный алгоритм
Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.
Посмотреть Раскраска графов и Жадный алгоритм
Жадная раскраска
''n'' вершинами, который можно раскрасить в два цвета, может быть раскрашен жадным алгоритмом в n/2 цветов. Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет.
Посмотреть Раскраска графов и Жадная раскраска
Задача о самом длинном пути
Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе.
Посмотреть Раскраска графов и Задача о самом длинном пути
Задача о картинной галерее
Задача о картинной галерее или музейная задача — это хорошо изученная (просматриваемости) в вычислительной геометрии.
Посмотреть Раскраска графов и Задача о картинной галерее
Задача о кликовом покрытии
Задача о кликовом покрытии — вычислительная задача, заключающаяся в определении возможности разбить вершины графа k клик.
Посмотреть Раскраска графов и Задача о кликовом покрытии
Звёздная раскраска
графа Дика равно 4, в то время как его хроматическое число равно 2. Звёздная раскраска в теории графов — (правильная) раскраска вершин, в которой любой путь из четырёх вершин использует как минимум три различных цвета.
Посмотреть Раскраска графов и Звёздная раскраска
Вырожденность (теория графов)
2-Вырожденный граф — каждая вершина имеет не более двух соседей слева, так что самая правая вершина любого подграфа имеет степень два и менее. Его 2-ядро, подграф, остающийся после удаления вершин со степенью, меньшей двух, выделено цветом.
Посмотреть Раскраска графов и Вырожденность (теория графов)
Временная сложность алгоритма
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные.
Посмотреть Раскраска графов и Временная сложность алгоритма
Внешнепланарный граф
Максимальный внешнепланарный граф и его 3-раскраска. Полный граф K4 является наименьшим планарным графом, не являющимся внешнепланарным. В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
Посмотреть Раскраска графов и Внешнепланарный граф
Верхушечный граф
планарным. В теории графов верхушечный граф — это граф, который можно сделать планарным удалением одной вершины.
Посмотреть Раскраска графов и Верхушечный граф
Вероятностный метод
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами.
Посмотреть Раскраска графов и Вероятностный метод
Веретено Мозера
Веретено Мозера (веретено Мозеров, граф Мозера) — неориентированный граф, названный в честь математиков и его брата Вильяма, имеющий семь вершин и одиннадцать рёбер.
Посмотреть Раскраска графов и Веретено Мозера
Граф сравнимости
В теории графов граф сравнимости — это неориентированный граф, в котором пары элементов соединены ребром, если эти элементы в некотором частичном порядке.
Посмотреть Раскраска графов и Граф сравнимости
Граф Коксетера
Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.
Посмотреть Раскраска графов и Граф Коксетера
Граф Паппа
В теории графов графом Паппа называется двудольный 3-регулярный неориентированный граф с 18 вершинами и 27 рёбрами, являющийся графом Леви конфигурации Паппа.
Посмотреть Раскраска графов и Граф Паппа
Граф Петерсена
Граф Петерсена — это неориентированный граф с 10 вершинами и 15 рёбрами.
Посмотреть Раскраска графов и Граф Петерсена
Граф Аполлония
Граф Аполлония Граф Голднера–Харари, негамильтонов граф Аполлония Граф Аполлония — это неориентированный граф, образованный рекурсивным процессом подразделения треугольника на три меньших треугольника.
Посмотреть Раскраска графов и Граф Аполлония
Граф Науру
В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами.
Посмотреть Раскраска графов и Граф Науру
Граф Татта
Граф Татта — 3-регулярный с 46 вершинами и 69 рёбрами, названный по имени математика Уильяма Татта, построившего его в 1946 году.
Посмотреть Раскраска графов и Граф Татта
Граф Татта — Коксетера
Граф Татта — Коксетера (также 8-клетка Татта) — 3-регулярный граф с 30 вершинами и 45 рёбрами.
Посмотреть Раскраска графов и Граф Татта — Коксетера
Граф Титце
ленты Мёбиуса на шесть взаимно соприкасающихся областей. Вершины и рёбра разбиения образуют вложение графа Титце в ленту. В теории графов граф Титце — это неориентированный кубический граф с 12 вершинами и 18 рёбрами.
Посмотреть Раскраска графов и Граф Титце
Граф Фостера
Граф Фостера — это двудольный 3-регулярный граф с 90 вершинами и 135 рёбрами.
Посмотреть Раскраска графов и Граф Фостера
Граф Хэнсона
Граф Хэнсона — это неориентированный бесконечный граф, единственный счётный однородный граф, не содержащий клики с вершинами, но содержащий в качестве подграфов все свободные от графы.
Посмотреть Раскраска графов и Граф Хэнсона
Граф Эллингема — Хортона
Графы Эллингема — Хортона — это два 3-регулярных графа с 54 и 78 вершинами — 54-граф Эллингема — Хортона и 78-граф Эллингема — Хортона.
Посмотреть Раскраска графов и Граф Эллингема — Хортона
Граф гиперкуба
В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине.
Посмотреть Раскраска графов и Граф гиперкуба
Граф дружеских отношений
Графы дружеских отношений ''F''2, ''F''3 и ''F''4. Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
Посмотреть Раскраска графов и Граф дружеских отношений
Граф единичных кругов
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости.
Посмотреть Раскраска графов и Граф единичных кругов
Граф Бигса — Смита
Граф Бигса — Смита — 3-регулярный граф с 102 вершинами и 153 рёбрами.
Посмотреть Раскраска графов и Граф Бигса — Смита
Граф Вагнера
Граф Вагнера — это 3-регулярный граф с 8 вершинами и 12 рёбрами, является 8-вершинной лестницей Мёбиуса.
Посмотреть Раскраска графов и Граф Вагнера
Граф Грея
Граф Грея — двудольный неориентированный граф с 54 вершинами и 81 рёбрами.
Посмотреть Раскраска графов и Граф Грея
Граф Дика
Граф Дика — это 3-регулярный граф с 32 вершинами и 48 рёбрами, назван в честь.
Посмотреть Раскраска графов и Граф Дика
Граф Дезарга
Граф Дезарга — дистанционно-транзитивный кубический граф с 20 вершинами и 30 рёбрами.
Посмотреть Раскраска графов и Граф Дезарга
Гармоническая раскраска
Гармоническая раскраска 7-дерева с тремя уровнями с использованием 12 цветов. Гармоническое хроматическое число этого графа равно 12, поскольку он имеет 57 рёбер число пар цветов равно ncolor*(ncolor-1)/2 >.
Посмотреть Раскраска графов и Гармоническая раскраска
Гипотеза Албертсона
Гипотеза Албертсона — это недоказанная связь между числом пересечением и хроматическим числом графа.
Посмотреть Раскраска графов и Гипотеза Албертсона
Гипотеза Самнера
Дэвид Самнер (специалист в теории графов из университета Южной Каролины) в 1971 высказал гипотезу, что турниры являются универсальными графами для (ориентированных деревьев).
Посмотреть Раскраска графов и Гипотеза Самнера
Гипотеза Хивуда
Гипотеза Хивуда, или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом.
Посмотреть Раскраска графов и Гипотеза Хивуда
Гипотеза Эрдёша — Фабера — Ловаса
Случай гипотезы Эрдёша — Фаюера — Ловеса — граф, образованный из клик, в каждом, по четыре вершины в каждой, любые две из которых пересекаются в одной вершине, может быть раскрашен в три цвета.
Посмотреть Раскраска графов и Гипотеза Эрдёша — Фабера — Ловаса
Гипотеза об экспоненциальном времени
Гипотеза об экспоненциальном времени — это недоказанное, которое сформулировали Импальяццо и Патури.
Посмотреть Раскраска графов и Гипотеза об экспоненциальном времени
Гипотеза Барнетта
Гипотеза Барнетта — это нерешённый вопрос в теории графов о существовании гамильтоновых циклов в графах.
Посмотреть Раскраска графов и Гипотеза Барнетта
Глубина дерева (теория графов)
В теории графов глубина дерева связного неориентированного графа G — это числовой инвариант G, минимальная высота дерева Тремо для суперграфа графа G. Этот инвариант и близкие понятия встречаются под различными именами в литературе, включая число ранжирования вершин, упорядоченное хроматическое число и минимальная высота исключения дерева.
Посмотреть Раскраска графов и Глубина дерева (теория графов)
Древесная ширина (теория графов)
В теории графов древесная ширина неориентированного графа — это число, ассоциированное с графом.
Посмотреть Раскраска графов и Древесная ширина (теория графов)
Дистанционно-наследуемый граф
В теории графов дистанционно-наследуемый граф (или вполне сепарабельный граф) — это граф, в котором расстояния в любом связном порождённом подграфе те же самые, что и в исходном графе.
Посмотреть Раскраска графов и Дистанционно-наследуемый граф
Ладейный граф
В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы.
Посмотреть Раскраска графов и Ладейный граф
Лестница Мёбиуса
Два представления лестницы Мёбиуса M_16. Анимация преобразования одного вида в другой Представление лестницы Мёбиуса ''M''16 в виде ленты Мёбиуса. Ле́стница Мёбиуса M_n — кубический циркулянтный граф с чётным числом вершин n, образованный из цикла с n вершинами путём добавления рёбер (называемых «перекладинами»), соединяющих противоположные пары вершин цикла.
Посмотреть Раскраска графов и Лестница Мёбиуса
Лексикографический поиск в ширину
Лексикографический поиск в ширину (lexicographic breadth-first search, LBFS or Lex-BFS) — алгоритм упорядочивания вершин графа.
Посмотреть Раскраска графов и Лексикографический поиск в ширину
1-планарный граф
графа Хивуда — шесть рёбер имеют единичные пересечения, а остальные 15 рёбер не пересекаются. В топологической теории графов 1-планарный граф — это граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром.
Посмотреть Раскраска графов и 1-планарный граф
10-Клетка Балабана
10-Клетка Балабана или балабанова (3,10)-клетка — это 3-регулярный граф с 70 вершинами и 105 рёбрами, названный именем химика румынского происхождения.
Посмотреть Раскраска графов и 10-Клетка Балабана
Также известен как Раскраска графа.