Более быстрый доступ, чем браузер!
56 отношения: Acta mathematica, American Mathematical Monthly, APX, CW-комплекс, Journal of Combinatorial Theory, LCF-нотация, NP-полная задача, Путевая ширина, Приближенная схема полиномиального времени, Паросочетание, Полиэдральный граф, Полный граф, Автоморфизм, Аппроксимационный алгоритм, Раскраска графов, Равенство классов P и NP, Регулярный граф, Степень вершины (теория графов), Симметричный граф, Снарк (теория графов), Снарк «Цветок», Снарк Уоткинса, Снарк Блануши, Тэт, Питер Гатри, Тат, Уильям Томас, Топология, Теорема Кёнига (комбинаторика), Теорема Брукса, Теорема Визинга, Флаг (геометрия), Фостер, Рональд, Число пересечений (теория графов), Эйлер, Леонард, Максимальный разрез графа, Многогранник, Мост (теория графов), Задача коммивояжёра, Задача о вершинном покрытии, Задача о независимом множестве, Вычислительная сложность, Визуализация графов, Вложение графа, Граф (математика), Граф Коксетера, Граф Науру, Граф Титце, Граф Фрухта, Гамильтонов граф, Гипотеза Тэйта, Гипотеза Барнетта, ..., Динамическое программирование, Домики и колодцы, Доминирующее множество, Ловас, Ласло, Лемма о рукопожатиях, 1932 год в науке. Развернуть индекс (6 больше) »
Acta mathematica
Acta Mathematica — один из крупнейших рецензируемых научных журналов, освещающих исследования во всех областях математики.
Новый!!: Кубический граф и Acta mathematica · Узнать больше »
American Mathematical Monthly
American Mathematical Monthly — математический журнал, основанный Бенджамином Финкелом в 1894 году.
Новый!!: Кубический граф и American Mathematical Monthly · Узнать больше »
APX
APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом аппроксимации.
Новый!!: Кубический граф и APX · Узнать больше »
CW-комплекс
CW-комплекс — тип топологического пространства с дополнительной структурой (разбиением на клетки), введённый Уайтхедом для удовлетворения нужд теории гомотопий.
Новый!!: Кубический граф и CW-комплекс · Узнать больше »
Journal of Combinatorial Theory
Journal of Combinatorial Theory, Series A и Series B — математические журналы, специализирующиеся на комбинаторике и связанных областях.
Новый!!: Кубический граф и Journal of Combinatorial Theory · Узнать больше »
LCF-нотация
date.
Новый!!: Кубический граф и LCF-нотация · Узнать больше »
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Новый!!: Кубический граф и NP-полная задача · Узнать больше »
Путевая ширина
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён.
Новый!!: Кубический граф и Путевая ширина · Узнать больше »
Приближенная схема полиномиального времени
В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач.
Новый!!: Кубический граф и Приближенная схема полиномиального времени · Узнать больше »
Паросочетание
В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
Новый!!: Кубический граф и Паросочетание · Узнать больше »
Полиэдральный граф
правильного додекаэдра. Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.
Новый!!: Кубический граф и Полиэдральный граф · Узнать больше »
Полный граф
По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.
Новый!!: Кубический граф и Полный граф · Узнать больше »
Автоморфизм
Автоморфизм алгебраической системы — изоморфизм, отображающий алгебраическую систему на себя.
Новый!!: Кубический граф и Автоморфизм · Узнать больше »
Аппроксимационный алгоритм
В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
Новый!!: Кубический граф и Аппроксимационный алгоритм · Узнать больше »
Раскраска графов
Корректная раскраска вершин графа наименьшим набором цветов — тремя. В теории графов раскраска графов является частным случаем.
Новый!!: Кубический граф и Раскраска графов · Узнать больше »
Равенство классов P и NP
Вопрос о равенстве классов сложности ''P'' и ''NP'' (в русских источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий.
Новый!!: Кубический граф и Равенство классов P и NP · Узнать больше »
Регулярный граф
Регуля́рный (одноро́дный) граф — граф, степени всех вершин которого равны, то есть каждая вершина имеет одинаковое количество соседей.
Новый!!: Кубический граф и Регулярный граф · Узнать больше »
Степень вершины (теория графов)
Рис. 1. Граф, на вершинах которого отмечены степени. Степень или валентность вершины графа — количество рёбер графа G, инцидентных вершине x. При подсчёте степени ребро-петля учитывается дважды.
Новый!!: Кубический граф и Степень вершины (теория графов) · Узнать больше »
Симметричный граф
автоморфизмом, поскольку любое кольцо из пяти вершин можно перевести в любое такое же. Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм: такой, что: Другими словами, граф симметричен, если его группа автоморфизмов действует транзитивно на упорядоченных парах смежных вершин (таким образом, на всех рёбрах, как если бы они имели ориентацию).
Новый!!: Кубический граф и Симметричный граф · Узнать больше »
Снарк (теория графов)
Снарк «Цветок» J5 — один из шести снарков с 20 вершинами. Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4.
Новый!!: Кубический граф и Снарк (теория графов) · Узнать больше »
Снарк «Цветок»
В теории графов снарки «Цветы» образуют бесконечное семейство снарков, введённых Айзексом Руфусом в 1975 году.
Новый!!: Кубический граф и Снарк «Цветок» · Узнать больше »
Снарк Уоткинса
В теории графов снарк Уоткинса — снарк с 50 вершинами и 75 рёбрами.
Новый!!: Кубический граф и Снарк Уоткинса · Узнать больше »
Снарк Блануши
Снарк Блануши — 3-регулярный граф с 18 вершинами и 27 рёбрами.
Новый!!: Кубический граф и Снарк Блануши · Узнать больше »
Тэт, Питер Гатри
Питер Гатри Тэт (Тэйт) (Peter Guthrie Tait; 28 апреля 1831, Далкит — 4 июля 1901, Эдинбург) — шотландский и. Член Эдинбургского королевского общества (1861).
Новый!!: Кубический граф и Тэт, Питер Гатри · Узнать больше »
Тат, Уильям Томас
Уильям Томас Тат (William Thomas Tutte; —) — британский, позднее канадский криптограф и. Во время Второй Мировой Войны внёс значительный вклад в расшифровку шифра Лоренца, главной немецкой шифровальной системы, использовавшейся для секретных коммуникаций главнокомандующими вермахта.
Новый!!: Кубический граф и Тат, Уильям Томас · Узнать больше »
Топология
Лента Мёбиуса — поверхность с одной стороной и одним краем; пример объекта, изучаемого в топологии. бублика и кружки. Тополо́гия (от τόπος — место и λόγος — слово, учение) — раздел математики.
Новый!!: Кубический граф и Топология · Узнать больше »
Теорема Кёнига (комбинаторика)
Пример двудольного графа с наибольшим паросочетанием (выделено голубым) и наименьшим вершинным покрытием (выделено красным), оба имеют размер шесть. В теории графов теорема Кёнига, доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах.
Новый!!: Кубический граф и Теорема Кёнига (комбинаторика) · Узнать больше »
Теорема Брукса
полных графов требуется на единицу больше цветов, чем их максимальная степень. Эти графы и нечётные циклы являются единственными исключениями для теоремы Брукса. Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом.
Новый!!: Кубический граф и Теорема Брукса · Узнать больше »
Теорема Визинга
Теорема Визинга — утверждение теории графов, согласно которому рёбра любого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин \delta графа.
Новый!!: Кубический граф и Теорема Визинга · Узнать больше »
Флаг (геометрия)
Диаграмма граней квадратной пирамиды, показывающая один из её флагов Флаг в геометрии многогранников — последовательность граней (различной размерности) абстрактного многогранника, в которой каждая предыдущая грань содержится в последующей и последовательность содержит ровно по одной грани каждой размерности.
Новый!!: Кубический граф и Флаг (геометрия) · Узнать больше »
Фостер, Рональд
Рональд Мартин Фостер (3 октября 1896 — 2 февраля 1998), математик Bell Labs известный трудом по использованию электронных фильтров для линий телесвязи.
Новый!!: Кубический граф и Фостер, Рональд · Узнать больше »
Число пересечений (теория графов)
cr(''G'').
Новый!!: Кубический граф и Число пересечений (теория графов) · Узнать больше »
Эйлер, Леонард
Леона́рд Э́йлер (Leonhard Euler; 15 апреля 1707, Базель, Швейцария —, Санкт-Петербург, Российская империя) — швейцарский, немецкий и российский и, внёсший фундаментальный вклад в развитие этих наук (а также физики, астрономии и ряда прикладных наук) — С. 543—544.
Новый!!: Кубический граф и Эйлер, Леонард · Узнать больше »
Максимальный разрез графа
Максимальный разрез. Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза.
Новый!!: Кубический граф и Максимальный разрез графа · Узнать больше »
Многогранник
Додекаэдр Многогранник или полиэдр — обычно замкнутая поверхность, составленная из многоугольников, но иногда так же называют тело, ограниченное этой поверхностью.
Новый!!: Кубический граф и Многогранник · Узнать больше »
Мост (теория графов)
Граф с 6 мостами (выделены красным) Неориентированный связный граф, не имеющий разрезающих рёбер Мост — ребро в теории графов, удаление которого увеличивает число компонент связности.
Новый!!: Кубический граф и Мост (теория графов) · Узнать больше »
Задача коммивояжёра
43589145600 вариантов. Задача коммивояжёра (Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Новый!!: Кубический граф и Задача коммивояжёра · Узнать больше »
Задача о вершинном покрытии
Задача о вершинном покрытии — NP-полная задача информатики в области теории графов.
Новый!!: Кубический граф и Задача о вершинном покрытии · Узнать больше »
Задача о независимом множестве
Зада́ча о незави́симом мно́жестве относится к классу NP-полных задач в области теории графов.
Новый!!: Кубический граф и Задача о независимом множестве · Узнать больше »
Вычислительная сложность
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Новый!!: Кубический граф и Вычислительная сложность · Узнать больше »
Визуализация графов
Визуализация или отображение графов, как ответвление теории графов, относящееся к топологии и геометрии — двумерное представление графа.
Новый!!: Кубический граф и Визуализация графов · Узнать больше »
Вложение графа
Вложение графа — изучаемое в рамках топологической теории графов представление графа G на заданной поверхности \Sigma, в котором точки \Sigma ассоциируются с вершинами и простые дуги (гомеоморфные образы) ассоциируются с рёбрами таким образом, что.
Новый!!: Кубический граф и Вложение графа · Узнать больше »
Граф (математика)
Неориентированный граф с шестью вершинами и семью рёбрами Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.
Новый!!: Кубический граф и Граф (математика) · Узнать больше »
Граф Коксетера
Граф Коксетера — 3-регулярный граф с 28 вершинами и 42 рёбрам Все кубические дистанционно-регулярные графы известны, граф Коксетера — один из 13-ти таких графов.
Новый!!: Кубический граф и Граф Коксетера · Узнать больше »
Граф Науру
В теории графов граф Науру — это симметричный двудольный кубический граф с 24 вершинами и 36 рёбрами.
Новый!!: Кубический граф и Граф Науру · Узнать больше »
Граф Титце
ленты Мёбиуса на шесть взаимно соприкасающихся областей. Вершины и рёбра разбиения образуют вложение графа Титце в ленту. В теории графов граф Титце — это неориентированный кубический граф с 12 вершинами и 18 рёбрами.
Новый!!: Кубический граф и Граф Титце · Узнать больше »
Граф Фрухта
В теории графов графом Фрухта называется 3-регулярный граф с 12 вершинами и 18 рёбрами без нетривиальных симметрий.
Новый!!: Кубический граф и Граф Фрухта · Узнать больше »
Гамильтонов граф
Гамильтонова линия для додекаэдра, предложенная Гамильтоном для замены его игры «вокруг света» на додекаэдре на задачу для плоского графа. Гамильто́нов граф — математический объект теории графов.
Новый!!: Кубический граф и Гамильтонов граф · Узнать больше »
Гипотеза Тэйта
Гипотеза Тэйта утверждает, что любой 3-связный планарный кубический граф имеет гамильтонов цикл, проходящий через все его вершины.
Новый!!: Кубический граф и Гипотеза Тэйта · Узнать больше »
Гипотеза Барнетта
Гипотеза Барнетта — это нерешённый вопрос в теории графов о существовании гамильтоновых циклов в графах.
Новый!!: Кубический граф и Гипотеза Барнетта · Узнать больше »
Динамическое программирование
Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи.
Новый!!: Кубический граф и Динамическое программирование · Узнать больше »
Домики и колодцы
«Домики и колодцы» — классическая математическая головоломка, задача в которой — проложить от каждого из трёх колодцев к каждому из трёх домиков непересекающиеся тропинки.
Новый!!: Кубический граф и Домики и колодцы · Узнать больше »
Доминирующее множество
Доминирующее множество (красные вершины). В теории графов доминирующее множество для графа G.
Новый!!: Кубический граф и Доминирующее множество · Узнать больше »
Ловас, Ласло
Ласло Ловас (Lovász László,; род. 9 марта 1948) — венгерский, известный работами по комбинаторике, за которые он был награждён многими престижными премиями.
Новый!!: Кубический граф и Ловас, Ласло · Узнать больше »
Лемма о рукопожатиях
Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней.
Новый!!: Кубический граф и Лемма о рукопожатиях · Узнать больше »
1932 год в науке
В 1932 году были различные научные и технологические события, некоторые из которых представлены ниже.
Новый!!: Кубический граф и 1932 год в науке · Узнать больше »
