Характеристический многочлен матрицы

Характеристический многочлен матрицы — многочлен, определяющий её собственные значения.

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

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

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

Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.

Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов образует вершинную группу графа или просто группу графа. Группа подстановок на множестве ребер называется реберной группой графа, которая тесно связана с вершинной...

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

Симметричный граф (или транзитивный относительно дуг граф) — граф G, для любых двух пар смежных вершин которого u1—v1 и u2—v2 имеется автоморфизм...

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

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

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

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

Подробнее: Граф Пэли

В теории графов графом гиперкуба Qn называется регулярный граф с 2n вершинами, 2n−1n рёбрами и n рёбрами, сходящимися в одной вершине. Его можно получить как одномерный скелет геометрического гиперкуба. Например, Q3 — это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. Граф можно получить другим образом, отталкиваясь от семейства подмножеств множества с n элементами путём использования в качестве вершин все подмножества и соединением двух вершин ребром, если соответствующие множества...

Подробнее: Граф гиперкуба

Сильно регулярный граф является дистанционно-регулярным с диаметром 2, но только в том случае, когда μ не равно нулю.

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

Дистанционно-регулярный граф — регулярный граф такой, что для любых двух вершин v и w число вершин с расстоянием j от v и расстоянием k от w зависят только от j, k и i = d(v, w).

Дистанционно-транзитивный граф — такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, существует автоморфизм графа, который переводит v в x и w в y.

Обхват в теории графов — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности.

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

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

Подробнее: Обобщённый граф Петерсена

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

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

Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).

В теории графов паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.

Полный двудольный граф (биклика) — специальный вид двудольного графа, у которого любая вершина первой доли соединена со всеми вершинами второй доли вершин.

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

Двудо́льный граф или бигра́ф — это математический термин теории графов, обозначающий граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

В теории графов графом-циклом называется граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как Cn. Число вершин в Cn равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам.

Подробнее: Граф-цикл

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

Подробнее: Граф единичных расстояний

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).

Подробнее: Глоссарий теории графов

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

Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. (По теореме Визинга хроматический индекс кубического графа равен 3 или 4.) Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.

Граф Ле́ви (также граф инциде́нтности) — двудольный граф, соответствующий структуре инцидентности. Из набора точек и линий в геометрии инцидентности или проективной конфигурации образуется граф с одной вершиной для каждой точки, одной вершиной для каждой линии и одного ребра для каждой инциденции точки и линии (то есть отношения «точка лежит на линии»). Эти графы назвали именем Фридриха Леви, который описал их в 1942 году.

Окрестность часто обозначается как NG(v) или (если известно, о каком графе идёт речь) N(v). То же самое обозначение окрестности может использоваться для ссылки на множество смежных вершин, а не на соответствующий порождённый подграф. Окрестность, описанная выше, не включает саму вершину v и об этой окрестности говорят как об открытой окрестности вершины v. Можно определить окрестность, включающую v. В этом случае окрестность называется закрытой и обозначается как NG. Если не указано явно, окрестность...

Зада́ча о незави́симом мно́жестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике.

В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.

Подробнее: Циркулянтный граф

n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим, если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём.

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

Подробнее: Решётка (теория графов)

Путь в графе — последовательность вершин, в которой каждая вершина соединена со следующей ребром.

Проективная пло́скость — двумерное проективное пространство. Важным частным случаем является вещественная проективная плоскость.

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

Подробнее: Граф пересечений

Число очередей графа — это инвариант графа, определённый аналогично стэковому числу (толщине книги) и использующий упорядочение FIFO (первый вошёл, первый вышел, очередь) вместо упорядочения LIFO (последним вошёл, первым вышел, стэк).

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

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

В теории графов неориентированный граф H называется минором графа G, если H может быть образован из G удалением рёбер и вершин и стягиванием рёбер.

Подробнее: Минор графа

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

В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.

Подробнее: Рёберный граф

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

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

В теории графов короной с 2n вершинами называется неориентированный граф с двумя наборами вершин ui и vi и рёбрами между ui и vj, если i ≠ j. Можно рассматривать корону как полный двудольный граф, из которого удалено совершенное паросочетание, как двойное покрытие двудольным графом полного графа, или как двудольный граф Кнезера Hn,1, представляющий подмножества из 1 элемента и (n − 1) элементов множества из n элементов с рёбрами между двумя подмножествами, если одно подмножество содержится в другом...

Подробнее: Корона (теория графов)

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

В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.

Подробнее: Внешнепланарный граф

Обобщённый многоугольник — это структура инцидентности, предложенная Жаком Титсом в 1959 году. Обобщённые n-угольники вмещают в качестве частных случаев проективные плоскости (обобщённые треугольники, n=3) и обобщённые четырёхугольники (n=4). Многие обобщённые многоугольники получаются из групп типа Ли, но существуют некоторые экзотические обобщённые многоугольники, которые таким способом не получаются. Обобщённые многоугольники, удовлетворяющие условию, известному как свойство Муфанга, полностью...

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