Вычисление хроматического многочлена произволного графа.

Хроматический многочлен любого графа равен сумме хроматических многочленов некоторого числа полных графов, число вершин в которых не больше, чем в графе .

20) Планарные графы. Теорема Эйлера. Доказать, что в любом планарном графе существует вершина, степень которой не превосходит 5.

Плана́рный граф —граф, который может быть изображён на плоскости без пересечения рёбер

Теорема Эйлера:

Для произвольного плоского связного графа с вершинами, ребрами и гранями справедливо следующее соотношение: 21) Планарные графы. Двойственные графы. Теорема о 5 красках. Плана́рный граф —граф, который может быть изображён на плоскости без пересечения рёбер Двойственный граф -это граф, в котором вершины соответствуют граням графа ; эти вершины соединены ребром, только если соответствующие им грани графа имеют общее ребро Теорема о 5 красках:Всякий связный планарный граф G можно правильно раскрасить не более чем 5-ю красками 22) Диэдральные группы. Образующие, определяющие соотношения. Цветные графы Кэли. Диэдральная группа: группа симметрии правильного многоугольника, включающая как вращения, так и осевые симметрии Образующие:Пусть G некоторая группа. Элементы g1, g2, gn называются образующими элементами группы G если всякий элемент g можно представить в виде: Определяющие соотношения: ??? Цветные графы Кэли:граф, который строится по группе с выделенной системой образующих 23) Циклические группы. Группа циклична, если она порожденная одним элементом, то есть все ее элементы являются степенями а. 24) Симметрические, знакопеременные группы. Симметрическая группа:Множество всех перестановок множества X (т.е. биекций X →X) с операцией композиции образуют группу, которая называется симметрической группой или группой перестановок X. Знакопеременные группы:это подгруппа симметрической группы, содержащая только четные перестановки. 25) Группы, подгруппы, разложение группы по подгруппе, нормальные подгруппы. Фактор-группы. Абелевы группы.. Группа: множество, на котором определена ассоциативная бинарная операция, причём для этой операции имеется нейтральный элемент (аналог единицы для умножения), и каждый элемент множества имеет обратный. Подгруппа ― подмножество {\displaystyle H}H группы {\displaystyle G}G, само являющееся группой относительно операции, определяющей {\displaystyle G}G. Подмножество {\displaystyle H}H группы {\displaystyle G}G является её подгруппой тогда и только тогда, когда: 1. {\displaystyle H}H содержит единичный элемент из {\displaystyle G}G 2. содержит произведение любых двух элементов из {\displaystyle H}H, 3. содержит вместе со всяким своим элементом {\displaystyle h}h обратный к нему элемент {\displaystyle h^{-1}}h^-1. Нормальная подгруппа: подгруппа особого типа, левый и правый смежные классы по которой совпадают Фактор-группы:множество смежных классов группы по её нормальной подгруппе, само являющееся группой с определённой специальным образом групповой операцией. Абелева группа:группа, в которой групповая операция является коммутативной 26) Теорема Лангранжа Пусть группа G конечна, и H — её подгруппа. Тогда порядок G равен порядку H, умноженному на количество её левых или правых классов смежности 27) Сопряженные элементы, нормальные подгруппы, гомоморфизм групп. Сопряженные элементы:Элементы g1 и g2 группы G называются сопряженными, если существует элемент h из G, для которого h*g1*h^-1 = g2 Нормальная подгруппа: подгруппа особого типа, левый и правый смежные классы по которой совпадают Гоморфизм групп:Отображение ф: G1 -> G2 группы <G1,*> в группе <G2, X> называется гомоморфизмом, если она сохраняет групповую структуру: Для всяких a, b их G1 : ф(a*b) = ф(а) X ф(b) 28) Действие групп на множествах. Системы транзитивности, транзитивные, интранзитивные группы. Действие групп на множествах: Пусть имеется множество Х. Группа G действует на X, если любых g из G и х из X определенно действие элемента g на элемент х(обозначаемое gx), обладающие следующими свойствами: 1) gx принадлежит Х 2) Для любых g1,g2 из G, х из Х выполнено (g1g2)x = g1(g2x) 3) Для любого х из Х выполнено ex = x Транзитивные группы:Пусть G – группа подстановок множества символов X = {x1, …, xn}, S – некоторое подмножество множества Х. Тогда подстановки из группы G, оставляющие на месте символы из S, образуют подгруппу K. Подстановки, переставляющие между собой символы из S, образуют подгруппу H, которая содержит K в качестве нормального делителя. Интранзитивные группы:Пусть G –группа подстановок, и пусть Si, i принадлежит I(множеству индексов) – различные орбиты группы G. Если вместо подстановок группы G рассматривать только подстановки множества Si, то последние образуют группу Gi. Для любого i из I элемент g из G определяет элемент gi из Gi, а именно подстановку символов из Si, инициируемую элементом g. 29) Группы автоморфизмов, внутренний автоморфизм, нормальные (инвариантные подгруппы). Группы автоморфизмов:биективный гомоморфизм группы на себя. Внутренний автоморфизм:Автоморфизм f группы G называется внутренним, если существует такой элемент a из G, что f(x)=axa^-1 Нормальная подгруппа: подгруппа особого типа, левый и правый смежные классы по которой совпадают 30) Теорема Кэлли В теории групп теорема Кэли утверждает, что любая конечная группа {\displaystyle (G,\circ )}(G,o) изоморфна некоторой подгруппе группы перестановок множества элементов этой группы. При этом каждый элемент a из G сопоставляется с перестановкой pa, задаваемое тождеством pa(g)=a о g, где g – произвольный элемент группы G. (ЗДЕСЬ о ЭТО НЕ БУКВА И НЕ ПЕРЕМЕННАЯ, А УМНОЖЕНИЕ В ГРУППАХ) 31) Представление диэдральной группы Dn в виде подгруппы подстановок n-ой степени. ??? 32) Лемма Бернсайда. Пусть группа G действует на множество X. Будем называть два элемента x и y эквивалентными, если x = gy, для некоторого g из G. Тогда число классов эквивалентности равно сумме числа стабилизаторов(неподвижная точка для элемента g называется такой элемент х, для которого gx = x) по всем элементам группы G, деленной на размер этой группы: . Где I(k) – количество стабилизаторов для элемента k.