Матричная теорема о деревьях

Матричная теорема о деревьях или теорема Кирхгофа — даёт выражение на число остовных деревьев графа через определитель определённой матрицы.

Доказана Густавом Кирхгофом в 1847 году; мотивировкой этой теоремы послужили расчёты электрических цепей.

Источник: Википедия

Связанные понятия

Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов. Многочлен считает число раскрасок графа как функции от числа цветов. Многочлен первоначально определил Джордж Дейвид Биркгоф в попытке атаки на проблему четырёх красок. Многочлен обобщили Х. Уитни и У. Т. Тат до многочлена Тата, связав его с моделью Поттса статистической физики.

Умноже́ние ма́триц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведе́нием ма́триц.

Теорема де Брёйна — Эрдёша — классическая теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.

В математике квадра́тная ма́трица — это матрица, у которой число строк совпадает с числом столбцов, и это число называется порядком матрицы. Любые две квадратные матрицы одинакового порядка можно складывать и умножать.

Алгебраическая связность графа G — это второе из минимальных собственных значений матрицы Кирхгофа графа G. Это значение больше нуля в том и только в том случае, когда граф G является связным. Это следствие того факта, что сколько раз значение 0 появляется в качестве собственного значения матрицы Кирхгофа, из стольких компонент связности состоит граф. Величина этого значения отражает насколько хорошо связен весь граф и используется для анализа устойчивости и синхронизации сетей.

Лемма регулярности Семереди — лемма из общей теории графов, утверждающая, что вершины любого достаточно большого графа можно разбить на конечное число групп таких, что почти во всех двудольных графах, соединяющих вершины из двух разных групп, рёбра распределены между вершинами почти равномерно. При этом минимальное требуемое количество групп, на которые нужно разбить множество вершин графа, может быть сколь угодно большим, но количество групп в разбиении всегда ограничено сверху.

Кольцо многочленов — кольцо, образованное многочленами от одной или нескольких переменных с коэффициентами из другого кольца. Изучение свойств колец многочленов оказало большое влияние на многие области современной математики; можно привести примеры теоремы Гильберта о базисе, конструкции поля разложения и изучения свойств линейных операторов.

Бикватернионы — комплексификация (расширение) обычных (вещественных) кватернионов.

Формула Вика — формула теории вероятностей, выражающая математическое ожидание многочлена от координат гауссовского вектора через элементы матрицы ковариаций. Одним из её применений является связь между средним значением полинома от следов степеней случайной матрицы большого размера и родами поверхностей, получаемыми склейкой заданных многоугольников при различных отождествлениях сторон.

Теорема Дилуорса в комбинаторике — утверждение, характеризующее экстремальное свойство для частично упорядоченных множеств.

Многочлен Александера — это инвариант узла, который сопоставляет многочлен с целыми коэффициентами узлу любого типа. Джеймс Александер обнаружил его, первый многочлен узла, в 1923. В 1969 Джон Конвей представил версию этого многочлена, ныне носящую название многочлен Александера — Конвея. Этот многочлен можно вычислить с помощью скейн-соотношения, хотя важность этого не была осознана до открытия полинома Джонса в 1984. Вскоре после доработки Конвеем многочлена Александера стало понятно, что похожее...

В вычислительной математике одной из наиболее важных задач является создание эффективных и устойчивых алгоритмов нахождения собственных значений матрицы. Эти алгоритмы вычисления собственных значений могут также находить собственные векторы.

Подробнее: Алгоритм вычисления собственных значений

В математике, матричная функция — это функция, отображающая матрицу в другую матрицу.

Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.

В математике, норма́льная фо́рма — простейший либо канонический вид, к которому объект приводится эквивалентными преобразованиями.

Факторизация многочлена — представление данного многочлена в виде произведения многочленов меньших степеней.

В теории графов частичный куб — это подграф гиперкуба, сохраняющий расстояния (в терминах графов) — расстояние между любыми двумя вершинами подграфа, то же самое, что и в исходном графе. Эквивалентно, частичный куб — это граф, вершины которого можно пометить битовыми строками одинаковой длины, так что расстояние между двумя вершинами в графе равно расстоянию Хэмминга между этими двумя метками. Такая разметка называется разметкой Хэмминга и она представляет изометричное вложение частичного куба в...

Основна́я теоре́ма а́лгебры — утверждение о том, что поле комплексных чисел алгебраически замкнуто, то есть всякий отличный от константы многочлен (от одной переменной) с комплексными коэффициентами имеет, по крайней мере, один корень на поле комплексных чисел. Утверждение справедливо и для многочленов с вещественными коэффициентами, так как всякое вещественное число является комплексным с нулевой мнимой частью.

Лемма о змее — это инструмент, используемый в математике, особенно в гомологической алгебре, для построения длинных точных последовательностей. Лемма о змее верна в любой абелевой категории и играет ключевую роль в гомологической алгебре и её приложениях, например в алгебраической топологии. Гомоморфизмы, построенные с её помощью, обычно называют связывающими гомоморфизмами.

Тополо́гия Зари́сского, или топология Зариского, — специальная топология, отражающая алгебраическую природу алгебраических многообразий. Названа в честь Оскара Зарисского и, начиная с 1950-х годов, занимает важное место в алгебраической геометрии.

В линейной алгебре положи́тельно определённая ма́трица — это эрмитова матрица, которая во многом аналогична положительному вещественному числу. Это понятие тесно связано с положительно определённой симметрической билинейной формой (или полуторалинейной формой в случае с комплексными числами).

Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение...

Лине́йная а́лгебра — раздел алгебры, изучающий объекты линейной природы: векторные (или линейные) пространства, линейные отображения, системы линейных уравнений, среди основных инструментов, используемых в линейной алгебре — определители, матрицы, сопряжение. Теория инвариантов и тензорное исчисление обычно (в целом или частично) также считаются составными частями линейной алгебры. Такие объекты как квадратичные и билинейные формы, тензоры и операции как тензорное произведение непосредственно вытекают...

В математике монодро́ми́ей называется явление, состоящее в преобразовании некоторого объекта при обнесении его вдоль нетривиального замкнутого пути.

Подробнее: Монодромия

Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Её сложность лежит в основе некоторых алгоритмов шифрования с открытым ключом, таких как RSA.

Теорема Ласкера — Нётер утверждает, что каждый идеал нётерова кольца можно записать в виде конечного пересечения примарных идеалов. Такое представление идеала называется примарным разложением. В случае области главных идеалов это эквивалентно представлению в виде конечного пересечения (или произведения) степеней простых идеалов, то есть обобщает основную теорему арифметики. В 1905 теорема была доказана Эммануилом Ласкером в частном случае колец многочленов или сходящихся степенных рядов; общий случай...

В математике термин матрица Картана имеет три значения. Все они названы по имени французского математика Эли Картана. Фактически, матрицы Картана в контексте алгебр Ли впервые исследовал Вильгельм Киллинг, в то время как форма Киллинга принадлежит Картану.

Критерий планарности Маклейна — это описание планарных графов в терминах их пространства циклов. Критерий носит имя Саундерса Маклейна, опубликовавшего критерий в 1937. Критерий утверждает, что конечный неориентированный граф является планарным тогда и только тогда, когда пространство циклов графа (по модулю 2) имеет базис циклов, в котором каждое ребро графа принадлежит не более чем двум базисным векторам.

Симметрия встречается не только в геометрии, но и в других областях математики. Симметрия является видом инвариантности, свойством неизменности при некоторых преобразованиях.

В интегрировании, разложение дробей позволяет интегрировать рациональные функции. Любая рациональная функция может быть представлена в виде суммы некоторого многочлена и некоторого числа дробных функций. Каждая дробь имеет знаменатель в виде многочлена первой или второй степени, причём многочлен в знаменателе, в свою очередь, также может быть возведён в некоторую положительную целую степень. (В случае комплексной переменной, знаменатели являются многочленами первой степени, и эти многочлены могут...

Алгебраическая поверхность — это алгебраическое многообразие размерности два. В случае геометрии над полем комплексных чисел алгебраическая поверхность имеет комплексную размерность два (как комплексное многообразие, если оно неособо), а потому имеет размерность четыре как гладкое многообразие.

Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям.

Теорема Э́рдёша — Се́кереша в комбинаторике — утверждение, уточняющее одно из следствий теоремы Рамсея для финитного случая. В то время как теорема Рамсея облегчает доказательство того, что каждая последовательность разных действительных чисел содержит монотонно возрастающую бесконечную подпоследовательность или монотонно убывающую бесконечную подпоследовательность, результат, доказанный Палом Эрдёшем и Дьёрдем Секерешем, идёт дальше. Для данных r, s они показали, что любая последовательность разных...

Лемма Гаусса — утверждение про свойства многочленов над факториальными кольцами, которое впервые было доказано для многочленов над кольцом целых чисел. Широко применяется в теории колец и полей, в частности, при доказательстве факториальности кольца многочленов над факториальным кольцом и теоремы Люрота.

Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в логике графов второго порядка, может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан Брюно Курселем в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.

Прямое или декартово произведение двух множеств — это множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств.

Функция делителей — арифметическая функция, связанная с делителями целого числа. Функция известна также под именем функция дивизоров.

По́ле в общей алгебре — множество, для элементов которого определены операции сложения, взятия противоположного значения, умножения и деления (кроме деления на нуль), причём свойства этих операций близки к свойствам обычных числовых операций. Простейшим полем является поле рациональных чисел (дробей). Хотя названия операций поля взяты из арифметики, следует иметь в виду, что элементы поля не обязательно являются числами, и определения операций могут быть далеки от арифметических.

Косое разбиение графа — это разбиение его вершин на два подмножества, такое что порождённый подграф, образованный одним из его подмножеств вершин является несвязным, а другой порождённый подграф, образованный другим подмножеством является дополнением несвязного графа. Косые разбиения играют важную роль в теории совершенных графов.

Гомоморфизм графов — это отображение между двумя графами, не нарушающее структуру. Более конкретно, это отображение между набором вершин двух графов, которое отображает смежные вершины в смежные.

Теорема о приведении матрицы к диагональной форме — утверждение о возможности приведения любой вещественной квадратной матрицы к диагональному виду при помощи умножения на две вещественные ортогональные матрицы. Допускает обобщение на случай любой вещественной матрицы. Имеет большое значение в линейной алгебре и вычислительной математике.

Аддитивная комбинаторика (от англ. addition — сложение) — междисциплинарная область математики, изучающая взаимозависимость различных количественных интерпретаций понятия структурированности подмножества группы (как правило, конечной), а также аналогичные свойства производных от множества структур, использующихся при этих интерпретациях. Кроме того, аддитивная комбинаторика изучает структурированность в различных смыслах некоторых специфических множеств или классов множеств (например, подмножеств...

Теорема об упаковке кругов (известная также как теорема Кёбе — Андреева — Тёрстона) описывает возможные варианты касания окружностей, не имеющих общих внутренних точек. Граф пересечений (иногда называемый графом касаний) упаковки кругов — это граф, вершины которого соответствуют кругам, а рёбра — точкам касания. Если упаковка кругов осуществляется на плоскости (или, что эквивалентно, на сфере), то их граф пересечений называется графом монет. Графы монет всегда связны, просты и планарны. Теорема упаковки...

Произведением Мояля — самый известный пример звёздочного произведения в фазовом пространстве.

В математике перестановочный многогранник порядка n — это (n − 1)-мерный выпуклый многогранник, вложенный в n-мерное евклидово пространство, который является выпуклой оболочкой всех n! точек, получающихся перестановками координат вектора (1, 2, 3, …, n).

В математике инвариант Парри — Салливана (или число Парри — Салливана) — это числовое значение, представляющее интерес при изучении матриц инцидентности в теории графов и некоторых одномерных динамических систем. Инвариант даёт частичную классификацию нетривиальных неприводимых матриц инцидентности.

В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер).

Подробнее: Совершенный граф

В теории категорий есте́ственное преобразова́ние предоставляет способ перевести один функтор в другой, сохраняя внутреннюю структуру (например, композиции морфизмов). Поэтому естественное преобразование можно понимать как «морфизм функторов». Эта интуиция может быть строго формализована в определении категории функторов. Естественные преобразования — наиболее базовое определение в теории категорий наряду с функторами, поэтому оно появляется в большинстве её приложений.

Подробнее: Естественное преобразование

Алгебраическая геометрия — раздел математики, который объединяет алгебру и геометрию. Главным предметом изучения классической алгебраической геометрии, а также в широком смысле и современной алгебраической геометрии, являются множества решений систем алгебраических уравнений. Современная алгебраическая геометрия во многом основана на методах общей алгебры (особенно коммутативной) для решения задач, возникающих в геометрии.

В математике вектором Витта называется бесконечная последовательность элементов коммутативного кольца.

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я