Понятия со словом «контрпример»
Связанные понятия
Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Теорема о четырёх красках — теорема, которая утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке не считаются общей границей для них. Задача раскраски...
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации.
Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Названа в честь Фрэнка Рамсея.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов. Многочлен считает число раскрасок графа как функции от числа цветов. Многочлен первоначально определил Джордж Дейвид Биркгоф в попытке атаки на проблему четырёх красок. Многочлен обобщили Х. Уитни и У. Т. Тат до многочлена Тата, связав его с моделью Поттса статистической физики.
Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.
Экспандеры — это класс графов, изучение которых первыми начали московские математики М. С. Пинскер, Л. А. Бассалыго и Г. А. Маргулис в семидесятые годы XX века.
Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь (путь в неориентированном или ориентированном графе, который проходит все вершины графа ровно один раз) или гамильтонов цикл в заданном графе (ориентированном или неориентированном). Обе задачи NP-полны.
Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.
Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр (порождённых циклов нечётной длины), ни нечётных антидыр (дополнений нечётным дырам). Гипотезу высказал Берж в 1961. Доказательство Марии Чудновской, Нила Робертсона, Пола Сеймура и Робина Томаса было заявлено в 2002 и опубликовано ими в 2006.
Лемма регулярности Семереди — лемма из общей теории графов, утверждающая, что вершины любого достаточно большого графа можно разбить на конечное число групп таких, что почти во всех двудольных графах, соединяющих вершины из двух разных групп, рёбра распределены между вершинами почти равномерно. При этом минимальное требуемое количество групп, на которые нужно разбить множество вершин графа, может быть сколь угодно большим, но количество групп в разбиении всегда ограничено сверху.
Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.
Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...
Спектральная теория графов — направление в теории графов, изучающее свойства графов, характеристических многочленов, собственных векторов и собственных значений матриц, связанных с графом, таких, как его матрица смежности или матрица Кирхгофа.
Задача о клике относится к классу NP-полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.
Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.
Задача поиска изоморфного подграфа — это вычислительная задача, в которой входом являются два графа G и H и нужно определить, не содержит ли G подграф, изоморфный графу H.
«Тогда́ и то́лько тогда́» — логическая связка эквиваленции между утверждениями, применяемая в логике, математике, философии. Чтобы быть эквиваленцией, связка должна быть идентична стандартному материальному условному высказыванию («только тогда» эквивалентно «если … то»), соединённому со своей противоположностью, откуда и название связки. В результате истинность одного утверждения требует такой же истинности другого, то есть либо оба они истинны, либо оба ложны. Можно спорить о том, передаёт ли выражение...
Конечная геометрия — это любая геометрическая система, имеющая конечное количество точек. Например, евклидова геометрия не является конечной, так как евклидова прямая содержит неограниченное число точек, а точнее говоря, содержит ровно столько точек, сколько существует вещественных чисел. Конечная геометрия может иметь любое конечное число измерений.
Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытия.
Алгебраическая теория графов — это ветвь математики, в которой применяются алгебраические методы к задачам с графами. Другие подходы к задачам с графами — это геометрический, комбинаторный и алгоритмический. Существует три основные ветви алгебраической теории графов — две ветви используют линейную алгебру и теорию групп, а одна ветвь изучает инварианты графа.
Граф Кэли — граф, который строится по группе с выделенной системой образующих. Назван в честь Артура Кэли.
Кососимметрический граф — это ориентированный граф, который изоморфен своему собственному транспонированному графу, графу, образованному путём обращения всех дуг, с изоморфизмом, который является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа.
Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств.
В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
Подробнее: Аппроксимационный алгоритм
Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Критерий планарности Маклейна — это описание планарных графов в терминах их пространства циклов. Критерий носит имя Саундерса Маклейна, опубликовавшего критерий в 1937. Критерий утверждает, что конечный неориентированный граф является планарным тогда и только тогда, когда пространство циклов графа (по модулю 2) имеет базис циклов, в котором каждое ребро графа принадлежит не более чем двум базисным векторам.
Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.
В математике свободная абелева группа (свободный Z-модуль) — это абелева группа, имеющая базис, то есть такое подмножество элементов группы, что для любого её элемента существует единственное его представление в виде линейной комбинации базисных элементов с целыми коэффициентами, из которых только конечное число являются ненулевыми. Элементы свободной абелевой группы с базисом B называют также формальными суммами над B. Свободные абелевы группы и формальные суммы используются в алгебраической топологии...
Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из групп типа Ли, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью...
В теории графов
паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям.
Группа классов идеалов дедекиндова кольца — это, грубо говоря, группа, позволяющая сказать, насколько сильно в данном кольце нарушается свойство факториальности. Эта группа тривиальна тогда и только тогда, когда дедекиндово кольцо является факториальным. Свойства дедекиндова кольца, касающиеся умножения его элементов, тесно связаны с устройством этой группы.
Гипотеза в математике — утверждение, которое на основе доступной информации представляется с высокой вероятностью верным, но для которого не удаётся получить математическое доказательство. Математическая гипотеза является открытой математической проблемой, и каждую нерешённую математическую проблему, которая является проблемой разрешимости, можно сформулировать в форме гипотезы. Однако в виде гипотезы может быть сформулирована не всякая математическая проблема. Например, конкретное решение некоторой...
В теории графов графами Пэли (названы в честь Раймонда Пэли) называются плотные неориентированные графы, построенные из членов подходящего конечного поля путём соединения пар элементов, отличающихся на квадратичный вычет. Графы Пэли образуют бесконечное семейство конференсных графов, поскольку тесно связаны с бесконечным семейством симметричных конференсных матриц. Графы Пэли дают возможность применить теоретические средства теории графов в теории квадратичных вычетов и имеют интересные свойства...
Подробнее: Граф Пэли
Кольцо многочленов — кольцо, образованное многочленами от одной или нескольких переменных с коэффициентами из другого кольца. Изучение свойств колец многочленов оказало большое влияние на многие области современной математики; можно привести примеры теоремы Гильберта о базисе, конструкции поля разложения и изучения свойств линейных операторов.
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Аддитивная комбинаторика (от англ. addition — сложение) — междисциплинарная область математики, изучающая взаимозависимость различных количественных интерпретаций понятия структурированности подмножества группы (как правило, конечной), а также аналогичные свойства производных от множества структур, использующихся при этих интерпретациях. Кроме того, аддитивная комбинаторика изучает структурированность в различных смыслах некоторых специфических множеств или классов множеств (например, подмножеств...
Вырожденность известна также под именем k-ядерное число, ширина и зацепление, и, по существу, это то же самое, что и число раскраски или число Секереша — Вилфа. k-Вырожденные графы называются также k-индуктивными графами. Вырожденность графа может быть вычислена за линейное время с помощью алгоритма, который последовательно удаляет вершины с минимальной степенью. Компонента связности, оставшаяся после удаления всех вершин со степенью , меньшей k, называется k-ядром графа, и вырожденность графа равна...
Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графа.
Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа ) утверждает, что неориентированные графы, частично упорядоченные отношением минорности, образуют вполне квазиупорядоченное множество. Эквивалентно, любое семейство графов, замкнутое по минорам, может быть определено конечным набором запрещённых миноров, аналогично как теорема Вагнера определяет планарные графы как графы, не имеющие в качестве миноров полный граф K5 и полный двудольный граф K3,3.
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные . Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, т.е. при стремлении размера входа к бесконечности. Например, если время, которое нужно алгоритму для выполнения...
Подробнее: Временная сложность алгоритма
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь. Другими словами, нет изолированной вершины ( такой, которая не имеет соответствующих ей рёбер (называется "ребра, инцидентные вершине 1" (или 2) ).
Проективная группа — группа преобразований проективного пространства, индуцируемых линейными преобразованиями соответствующего векторного пространства. Её элементы называются проективными преобразованиями — они обобщают проективные преобразования проективной плоскости. С матричной точки зрения проективная группа — это группа всех невырожденных матриц с точностью до скалярных матриц.