Группы и их графы
Понятие, свойства алгебраических операций. Изоморфизм групп, подгруппы. Смежные классы, фактор-группы, гомоморфизм и циклические группы. Определение графов, изоморфизм. Графы специального вида, деревья, циклы и планарность. Группы подстановок и тетраэдра.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 29.06.2014 |
| Размер файла | 643,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Министерство высшего и среднего специального образования Республики Узбекистан
Ташкентский Государственный Педагогический Университет имени Низами
Физико-математический факультет
Направление 5110100 «Методика преподавания математики»
КУРСОВАЯ РАБОТА
НА ТЕМУ:
«Группы и их графы»
Оглавление
Введение
1. Группы
1.1 Понятие алгебраической операции
1.2 Свойства алгебраических операций
1.3 Изоморфизм групп
1.4 Понятие подгруппы
1.5 Смежные классы; классы сопряженных элементов
1.6 Нормальные подгруппы. Фактор-группы
1.7 Гомоморфизм
1.8 Циклические группы
2. Теория графов
2.1 Основные определения
2.2 Графы специального вида
2.3 Изоморфизм графов
2.4 Деревья
2.5 Эйлеровы и гамильтоновы циклы
2.6 Планарность. Двойственные графы
3. Группы и их графы
3.1 Группы подстановок
3.2 Группа тетраэдра
4. Практическая часть
Заключение
Список использованных источников
Введение
Теория групп начала оформляться в качестве самостоятельного раздела математики в конце восемнадцатого века. В течение первых десятилетий девятнадцатого века она развивалась медленно и практически не привлекала к себе внимания. Но затем, около 1830 года, благодаря работам Галуа и Абеля о разрешимости алгебраических уравнений всего за несколько лет она совершила гигантский скачок, который оказал глубокое влияние на развитие всей математики.
С тех пор основные понятия теории групп стали детально исследоваться. Постепенно они проникли во многие разделы математики и нашли применение в таких различных областях знания, как, например, квантовая механика, кристаллография и теория узлов.
Данная курсовая работа посвящена группам и их графическому представлению. Наша первая задача - выяснить, что же такое «группа».
Основная идея дальнейших рассмотрений, проникающая в самую сущность понятия группы, связана с концепцией структуры. Перед нами развернется ряд примеров и пояснений, определений и теорем, варьирующих одну основную тему - как группы и их графы представляют и иллюстрируют одну из разновидностей математической структуры.
1. Группы
1.1 Понятие алгебраической операции
группа изоморфизм граф подгруппа
Говорят, что на множестве X определена алгебраическая операция (), если каждой упорядоченной паре элементов поставлен в соответствие некоторый элемент называемый их произведением.
Примеры.
Композиция перемещений на множествах является алгебраической операцией.
Композиция подстановок является алгебраической операцией на множестве всех подстановок степени n.
Алгебраическими операциями будут и обычные операции сложения, вычитания и умножения на множествах соответственно целых, вещественных и комплексных чисел. Операция деления не будет алгебраической операцией на этих множествах, поскольку частное не определено при . Однако на множествах
,
это будет алгебраическая операция.
Сложение векторов является алгебраической операцией на множестве .
Векторное произведение будет алгебраической операцией на множестве .
Умножение матриц будет алгебраической операцией на множестве всех квадратных матриц данного порядка.
1.2 Свойства алгебраических операций
1. Операция (*) называется ассоциативной, если
.
Это свойство выполняется во всех приведенных выше примерах, за исключением операций вычитания (и деления) и операции векторного умножения векторов. Наличие свойства ассоциативности позволяет определить произведение любого конечного множества элементов. Например, если ,
.
В частности можно определить степени с натуральным показателем:
.
При этом имеют место обычные законы:
, .
1. Операция (*) называется коммутативной, если
.
В приведенных выше примерах операция коммутативна в примерах 3 и 4 и не коммутативна в остальных случаях. Отметим, что для коммутативной операции
.
2. Элемент называется нейтральным для алгебраической операции (*) на множестве X, если
.
В примерах 1-6 нейтральными элементами будут соответственно тождественное перемещение, тождественная перестановка, числа 0 и 1 для сложения и умножения, нулевой вектор, единичная матрица. Для векторного произведения нейтральный элемент отсутствует. Отметим, что нейтральный элемент (если он существует) определен однозначно. В самом деле, если - нейтральные элементы, то
.
Наличие нейтрального элемента позволяет определить степень с нулевым показателем:
.
3. Допустим, что для операции (*) на X существует нейтральный элемент. Элемент называется обратным для элемента , если
.
Отметим, что по определению
.
Все перемещения обратимы также как и все подстановки. Относительно операции сложения все числа обратимы, а относительно умножения обратимы все числа, кроме нуля. Обратимые матрицы - это в точности все матрицы с ненулевым определителем. Если элемент x обратим, то определены степени с отрицательным показателем:
.
Наконец, отметим, что если x и y обратимы, то элемент также обратим и
.
(Сначала мы одеваем рубашку, а потом куртку; раздеваемся же в обратном порядке!).
Определение (абстрактной) группы.
Пусть на множестве G определена алгебраическая операция (*). (G,*) называется группой, если
Операция (*) ассоциативна на G.
Для этой операции существует нейтральный элемент e (единица группы).
Каждый элемент из G обратим.
Примеры групп.
1. Любая группа преобразований.
2. (Z, +), (R, +), (C, +).
3.
Простейшие свойства групп. В любой группе выполняется закон сокращения:
(левый закон сокращения; аналогично, имеет место и правый закон).
Доказательство.
Домножим равенство слева на и воспользуемся свойством ассоциативности:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
.
1. Признак нейтрального элемента:
Доказательство.
Применим к равенству
закон сокращения.
2. Признак обратного элемента:
Доказательство.
Применим закон сокращения к равенству
.
3. Единственность обратного элемента. Обратный элемент определен однозначно. Следует из п.3.
4. Существование обратной операции. Для любых двух элементов произвольной группы G уравнение
5.
имеет и притом единственное решение.
Доказательство.
Непосредственно проверяется, что
(левое частное элементов ) является решением указанного уравнения. Единственность вытекает из закона сокращения, примененного к равенству
.
Аналогично устанавливается существование и единственность правого частного.
1.3 Изоморфизм групп
Отображение двух групп G и K называется изоморфизмом, если
1. Отображение взаимно однозначно.
2. Отображение сохраняет операцию:
.
Поскольку отображение обратное к также является изоморфизмом, введенное понятие симметрично относительно групп G и K , которые называются изоморфными.
Примеры.
1. Группы поворотов плоскости и вокруг точек и изоморфны между собой. Аналогично, изоморфными будут и группы, состоящие из поворотов пространства относительно любых двух осей.
2. Группа диэдра и соответствующая пространственная группа изоморфны.
Группа тетраэдра T изоморфна группе состоящей из четных подстановок четвертой степени. Для построения изоморфизма достаточно занумеровать вершины тетраэдра цифрами 1,2,3,4 и заметить, что каждый поворот, совмещающий тетраэдр с собой некоторым образом переставляет его вершины и, следовательно, задает некоторую подстановку множества{1,2, 3, 4} Повороты вокруг оси, проходящей через некоторую вершину (например 1), оставляет символ 1 на месте и циклически переставляет символы 1, 2, 3. Все такие перестановки - четные. Поворот вокруг оси, соединяющей середины ребер (например, 12 и 34) переставляет символы 1 и 2, а также 3 и 4. Такие перестановки также являются четными.
Формула определяет взаимно однозначное соответствие между множеством R вещественных чисел и множеством положительных чисел. При этом
.
Это означает, что является изоморфизмом.
Замечание. В абстрактной алгебре изоморфные группы принято считать одинаковыми. По существу это означает, что игнорируются индивидуальные свойства элементов группы и происхождение алгебраической операции.
1.4 Понятие подгруппы
Непустое подмножество называется подгруппой, если само является группой. Более подробно это означает, что
, и .
Признак подгруппы.
Непустое подмножество будет подгруппой тогда и только тогда, когда
.
Доказательство.
В одну сторону это утверждение очевидно. Пусть теперь - любой элемент. Возьмем в признаке подгруппы. Тогда получим
.
Теперь возьмем . Тогда получим
.
Примеры подгрупп.
Для групп преобразований новое и старое понятие подгруппы равносильны между собой.
- подгруппа четных подстановок.
и т.д.
Пусть G - любая группа и - любой фиксированный элемент. Рассмотрим множество
всевозможных степеней этого элемента. Поскольку
,
рассматриваемое множество является подгруппой. Она называется циклической подгруппой с образующим элементом g.
Пусть любая подгруппа. Рассмотрим множество
- централизатор подгруппы H в группе G. Из определения вытекает, что если , то
,
то есть . Теперь ясно, что если , то и
и значит централизатор является подгруппой. Если группа G коммутативна, то
.
Если G=H, то централизатор состоит из тех элементов, которые перестановочны со всеми элементами группы; в этом случае он называется центром группы G и обозначается Z(G).
Замечание об аддитивной форме записи группы.
Иногда, особенно когда операция в группе коммутативна, она обозначается (+) и называется сложением. В этом случае нейтральный элемент называется нулем и удовлетворяет условию:
g+0=g.
Обратный элемент в этом случае называется противоположным и обозначается (-g). Степени элемента g имеют вид g+g+...+g , называются кратными элемента g и обозначаются ng.
1.5 Смежные классы; классы сопряженных элементов
Пусть, как и выше, некоторая подгруппа. Реализуем H как группу L(H,G) левых сдвигов на группе G. Орбита
называется левым смежным классом группы G по подгруппе H. Аналогично, рассматривая правые сдвиги, приходим к правым смежным классам . Заметим, что стабилизатор St(g, L(H,G)) (как и St(g, R(H,G))) тривиален поскольку состоит из таких элементов , что
hg=g.
Поэтому, если группа H конечна, то все левые и все правые смежные классы состоят из одинакового числа элементов, равного .
Орбиты группы называются классами сопряженных элементов группы G относительно подгруппы H и обозначаются Если G=H, говорят просто о классах сопряженных элементов группы G. Классы сопряженных элементов могут состоять из разного числа элементов. Это число равно , где Z(H,g) подгруппа H, состоящая из всех элементов h перестановочных с g.
Пример.
Пусть
- группа подстановок степени 3. Занумеруем ее элементы: =(1,2,3); =(1,3,2); =(2,1,3); =(2,3,1); =(3,1,2); =(3,2,1). Пусть . Легко проверить, что левые смежные классы суть:
, , .
Правые смежные классы:
, , .
Все эти классы состоят из 2 элементов.
Классы сопряженных элементов G относительно подгруппы H:
, , , .
В то же время,
, , .
Теорема 1. (Лагранжа).
Пусть H подгруппа конечной группы G. Тогда порядок H является делителем порядка G.
Доказательство.
По свойству орбит G представляется в виде объединения непересекающихся смежных классов:
.
Поскольку все смежные классы состоят из одинакового числа элементов,
,
откуда и вытекает теорема.
Замечание.
Число s левых (или правых) смежных классов называется индексом подгруппы .
Следствие.
Две конечные подгруппы группы G порядки которых взаимно просты пересекаются только по нейтральному элементу.
В самом деле, если эти подгруппы, то их общая подгруппа и по теореме Лагранжа - общий делитель порядков H и K то есть 1.
1.6 Нормальные подгруппы. Фактор-группы
Пусть любая подгруппа и - любой элемент. Тогда
также является подгруппой G притом изоморфной H, поскольку отображение сопряжения является изоморфизмом. Подгруппа называется сопряженной по отношению к подгруппе H.
Определение.
Подгруппа H называется инвариантной или нормальной в группе G, если все сопряженные подгруппы совпадают с ней самой:
.
Равенство можно записать в виде Hg = gH и таким образом, подгруппа инвариантна в том и только в том случае, когда левые и правые смежные классы по этой подгруппе совпадают.
Примеры.
В коммутативной группе все подгруппы нормальны, так как отображение сопряжения в такой группе тождественно.
В любой группе G нормальными будут , во первых, тривиальная подгруппа и, во вторых, вся группа G. Если других нормальных подгрупп нет, то G называется простой.
В рассмотренной выше группе подгруппа не является нормальной, так как левые и правые смежные классы не совпадают. Сопряженными с H будут подгруппы
Если - любая подгруппа, то ее централизатор
Z = Z(H,G)
- нормальная подгруппа в G , так как для всех ее элементов z
.
В частности, центр Z(G) любой группы G -нормальная подгруппа.
Подгруппа H индекса 2 нормальна. В самом деле, имеем 2 смежных класса: H и
Hg = G-H = gH.
Теорема 2 (свойство смежных классов по нормальной подгруппе).
Если подгруппа H нормальна в G, то множество всевозможных произведений элементов из двух каких либо смежных классов по этой подгруппе снова будет одним из смежных классов, то есть
.
Доказательство.
Очевидно, что для любой подгруппы H . Но тогда
= = = .
Таким образом, в случае нормальной подгруппы H определена алгебраическая операция на множестве смежных классов. Эта операция ассоциативна, поскольку происходит из ассоциативного умножения в группе G. Нейтральным элементом для этой операции является смежный класс . Поскольку
,
всякий смежный класс имеет обратный. Все это означает, что относительно этой операции множество всех (левых или правых) смежных классов по нормальной подгруппе является группой. Она называется факторгруппой группы G по H и обозначается G/H. Ее порядок равен индексу подгруппы H в G.
1.7 Гомоморфизм
Гомоморфизм групп - это естественное обобщение понятия изоморфизма.
Определение.
Отображение групп называется гомоморфизмом, если оно сохраняет алгебраическую операцию, то есть
: .
Таким образом, обобщение состоит в том, что вместо взаимно однозначных отображений, которые участвуют в определении изоморфизма, здесь допускаются любые отображения.
Примеры.
1. Разумеется, всякий изоморфизм является гомоморфизмом.
2. Тривиальное отображение
является гомоморфизмом.
3. Если - любая подгруппа, то отображение вложения
будет инъективным гомоморфизмом.
4. Пусть - нормальная подгруппа. Отображение группы G на факторгруппу G/H будет гомоморфизмом поскольку
.
Этот сюръективный гомоморфизм называется естественным.
Теорема 3(свойства гомоморфизма).
Пусть - гомоморфизм групп, и - подгруппы. Тогда:
, .
- подгруппа.
-подгруппа, причем нормальная, если таковой была .
Доказательство.
и по признаку нейтрального элемента
.
Теперь имеем:
.
Пусть p = (h), q = (k). Тогда и
.
По признаку подгруппы получаем 2.
Пусть то есть элементы p = (h), q = (k) входят в . Тогда
то есть . Пусть теперь подгруппа нормальна и - любой элемент.
и потому
.
Определение.
Нормальная подгруппа
называется ядром гомоморфизма .Образ этого гомоморфизма обозначается .
Теорема 4.
Гомоморфизм инъективен тогда и только тогда, когда
Доказательство.
Поскольку
,
указанное условие необходимо. С другой стороны, если
,
То
и если ядро тривиально, и отображение инъективно.
Понятие гомоморфизма тесно связано с понятием фактор-группы.
Теорема 5 (о гомоморфизме).
Любой гомоморфизм можно представить как композицию естественного (сюръективного) гомоморфизма
,
Изоморфизма
и (инъективного) гомоморфизма
(вложения подгруппы в группу):
.
Доказательство.
Гомоморфизмы p и i описаны выше (см. примеры) Построим изоморфизм . Пусть
.
Элементами факторгруппы являются смежные классы Hg. Все элементы имеют одинаковые образы при отображении :
.
Поэтому формула
определяет однозначное отображение
.
Проверим сохранение операции
.
Поскольку отображение очевидно сюръективно, остается проверить его инъективность. Если
,
То
и потому
.
Следовательно,
и по предыдущей теореме инъективно.
Пусть - любой элемент. Имеем:
.
Следовательно,
.
1.8 Циклические группы
Пусть G произвольная группа и - любой ее элемент. Если некоторая подгруппа содержит g, то она содержит и все степени . С другой стороны, множество
очевидно является подгруппой G.
Подгруппа Z(g) называется циклической подгруппой G с образующим элементом g. Если G = Z(g) , то и вся группа G называется циклической.
Таким образом, циклическая подгруппа с образующим элементом g является наименьшей подгруппой G, содержащей элемент g.
Примеры
Группа Z целых чисел с операцией сложения является циклической группой с образующим элементом 1.
Группа поворотов плоскости на углы кратные n является циклической с образующим элементом - поворотом на угол n, n = 1, 2,
Теорема 6 (о структуре циклических групп).
Всякая бесконечная циклическая группа изоморфна Z. Циклическая группа порядка n изоморфна Z / nZ .
Доказательство.
Пусть G = Z(g) - циклическая группа. По определению, отображение
- сюръективно. По свойству степеней
и потому - гомоморфизм. По теореме о гомоморфизме
.
H = KerZ.
Если H - тривиальная подгруппа, то . Если H нетривиальна, то она содержит положительные числа. Пусть n - наименьшее положительное число, входящее в H. Тогда nZH. Предположим, что в H есть и другие элементы, то есть целые числа не делящееся на n нацело и k одно из них. Разделим k на n с остатком:
k = qn +r,
где 0 < r < n. Тогда
r = k - qn H,
что противоречит выбору n. Следовательно,
nZ = H
и теорема доказана.
Отметим, что
Z / nZ
Замечание. В процессе доказательства было установлено, что каждая подгруппа группы Z имеет вид nZ , где n = 0 ,1 , 2 ,...
Определение.
Порядком элемента называется порядок соответствующей циклической подгруппы Z( g ).
Таким образом, если порядок g бесконечен, то все степени - различные элементы группы G. Если же этот порядок равен n, то элементы
различны и исчерпывают все элементы из Z( g ), а
N
кратно n. Из теоремы Лагранжа вытекает, что порядок элемента является делителем порядка группы. Отсюда следует, что для всякого элемента g конечной группы G порядка n имеет место равенство
.
Следствие.
Если G - группа простого порядка p, то
- циклическая группа.
В самом деле, пусть - любой элемент отличный от нейтрального. Тогда его порядок больше 1 и является делителем p, следовательно он равен p. Но в таком случае
G = Z( g ).
Теорема 7 (о подгруппах конечной циклической группы).
Пусть G - циклическая группа порядка n и m - некоторый делитель n. Существует и притом только одна подгруппа HG порядка m. Эта подгруппа циклична.
Доказательство.
По предыдущей теореме GZ / nZ. Естественный гомоморфизм устанавливает взаимно однозначное соответствие между подгруппами HG и теми подгруппами KZ , которые содержат
Ker = nZ.
Но, как отмечалось выше, всякая подгруппа K группы Z имеет вид kZ Если kZnZ, то k - делитель n и (k) - образующая циклической группы H порядка m = n /k. Отсюда и следует утверждение теоремы.
Верна и обратная теорема: если конечная группа G порядка n обладает тем свойством, что для всякого делителя m числа n существует и притом ровно одна подгруппа H порядка m, то G - циклическая группа.
Доказательство.
Будем говорить, что конечная группа G порядка N обладает свойством (Z), если для всякого делителя m числа N существует и притом только одна подгруппа HG порядка m. Нам надо доказать, что всякая группа, обладающая свойством (Z) циклическая. Установим, прежде всего, некоторые свойства таких групп.
Лемма 1.
Если G обладает свойством (Z), то любая подгруппа G нормальна.
Если x и y два элемента такой группы и их порядки взаимно просты, то
xy = yx.
Если H подгруппа порядка m такой группы G порядка N и числа m и N/m взаимно просты, то H обладает свойством (Z).
Доказательство леммы.
1. Пусть HG . Для любого подгруппа имеет тот же порядок, что и H. По свойству
(Z)
то есть подгруппа H нормальна.
2. Пусть порядок x равен p, а порядок y равен q. По пункту 1) подгруппы Z(x) и Z(y) нормальны. Значит,
Z(x)y = yZ(x) и xZ(y) = Z(y)x
и потому для некоторых и
.
Следовательно,
.
Но, поскольку порядки подгрупп Z(x) и Z(y) взаимно просты, то
Следовательно,
и потому
xy = yx.
Используя свойство (Z), выберем в G подгруппу K порядка N/m. По 1) эта подгруппа нормальна, а поскольку порядки H и K взаимно просты, эти подгруппы пересекаются лишь по нейтральному элементу. Кроме того по 2) элементы этих подгрупп перестановочны между собой. Всевозможные произведения hk =kh, где hH, kK попарно различны, так как
=e
поскольку это единственный общий элемент этих подгрупп. Количество таких произведений равно
m N/m =
и, следовательно, они исчерпывают все элементы G. Сюръективное отображение
является гомоморфизмом с ядром K. Пусть теперь число s является делителем m. Выберем в G подгруппу S порядка s. Поскольку s и N/m взаимно просты,
и потому - подгруппа порядка s. Если бы подгрупп порядка s в H было несколько, то поскольку все они были бы и подгруппами G условие (Z) для G было бы нарушено. Тем самым мы проверили выполнение условия (S) для подгруппы H.
Доказательство теоремы.
Пусть
- разложение числа N в произведение простых чисел. Проведем индукцию по k. Пусть сначала k = 1, то есть .
Выберем в G элемент x максимального порядка . Пусть y любой другой элемент этой группы. Его порядок равен , где u s. Группы и имеют одинаковые порядки и по свойству (Z) они совпадают. Поэтому и мы доказали, что x - образующий элемент циклической группы G. Пусть теорема уже доказана для всех меньших значений k. Представим N в виде произведения двух взаимно простых множителей N = pq (например, ). Пусть H и K подгруппы G порядка p и q. Использую 3) и предположение индукции , мы можем считать, что H = Z(x), K = Z(y), Причем xy = yx. Элемент xy имеет порядок pq = N и, следовательно, является образующим элементом циклической группы G.[4]
2. Теория графов
2.1 Основные определения
Пусть V - непустое множество, V2 - множество всех его двухэлементных подмножеств, т.е. множество неупорядоченных пар {а, b}, где а, b ? V. Пара (V, E), где Е - произвольное подмножество V2, называется графом (неориентированным графом). При этом элементы множества V называются вершинами графа, элементы множества E - ребрами. Множества вершин и ребер графа G обозначаются символами V(G) и E(G) соответственно. Вершины и ребра графа называются его элементами.
В дальнейшем рассматриваются только конечные графы, т.е. множество E предполагается конечным. Число | V(G) | вершин называется его порядком и обозначается через |G|. Если
|G| = п,
|E(G)| = т,
то G называют (п, т)-графом.
Говорят, что две вершины u и v смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если е = {u, v} - ребро, то вершины u и v называют его концами. В этом случае также говорят, что ребро е соединяет вершины u и v. Такое ребро обозначается символом uv .
Два ребра называются смежными, если они имеют общий конец.
Вершина е и ребро v называются инцидентными, если v является концом ребра е, и не инцидентными в противном случае.
Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии - ребрам.
Ориентированный граф - это пара (V, А), где V - множество вершин, А - множество ориентированных ребер (или дуг), т.е. упорядоченных пар (u, v), где u, v ? V. При этом и называется началом дуги, v - концом. На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу.[1,3]
Число ребер, инцидентных некоторой вершине v, называется степенью вершины и обозначается deg v. В полном графе Кn степень каждой вершины равна n - 1.
Вершина степени 0 называется изолированной, вершина степени 1 - концевой (висячей). Ребро, инцидентное концевой вершине, также называется концевым. Вершина графа, смежная с каждой другой его вершиной, называется доминирующей.
Подграфом графа называется граф, являющийся подмоделью исходного графа. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).
Например, подграфами графа G являются графы H1 и H2:
Рис. 1
Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого - U, содержащий те и только те рёбра, оба конца которых входят в U.
Подграф называется H остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.
Так, для графа G, изображенного на рисунке, G1 - его остовной подграф, а G2- порожденный (рис. 2).
Рис. 2
2.2 Графы специального вида
Приведем примеры некоторых графов специального вида.
Граф G называется полным, если любые две его вершины смежны. Полный граф порядка п обозначается символом Кп, в нем ребер . На рис. 3 изображены графы Кп порядка n?5 .
Рис. 3
Граф называется пустым, если в нем нет ребер. Пустой граф порядка п обозначается Оп.
Ниже неоднократно используются термины “разбиение” и “покрытие”. Набор подмножеств множества S называется покрытием множества S, если объединение этих множеств совпадает с S. Покрытие называется разбиением, если никакие два из входящих в него множеств не пересекаются.
Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям.
Например:
Рис. 4
Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Полный двудольный граф, доли которого состоят из p и q вершин, обозначается символом Kp,q.
Например, K2,3 может быть изображен так:
Рис. 5
2.3 Изоморфизм графов
Легко подсчитать число графов с фиксированным множеством вершин V. Эти графы различаются своими ребрами, и поэтому их число равно количеству подмножеств множества VЧV, т.е., где п=|V|. Однако эти графы на всегда следует различать. Как в применении теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребра графа). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно не различать. Такие графы называются изоморфными.
Пусть G и Н - графы, а ц: V G V H - биекция. Если для любых вершин и и v графа G их образы ц(u) и ц(v) смежны в Н тогда и только тогда, когда и и v смежны в G, то эта биекция называется изоморфизмом графа G на граф Н. Если такой изоморфизм существует, то мы пишем GH и говорим, что графы G и Н изоморфны.
Очевидно, что отношение изоморфизма графов является эквивалентностью, т.е. оно симметрично, рефлексивно и транзитивно. Следовательно, все графы разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять, т.е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игнорируется при введении понятия графа. Класс изоморфных графов принято называть абстрактным графом.
В некоторых случаях приходится различать изоморфные графы. Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, …, п. Отождествив каждую из вершин графа с ее номером (а, следовательно, множество вершин - с множеством чисел {1, 2, …, п}), определим равенство графов G и Н одного и того же порядка: G = Н тогда, когда ЕG = ЕН.
Способы задания графа
Способы задания графа:
1. Явное задание графа как алгебраической системы.
2. Геометрический.
3. Матрица смежности.
4. Матрица инцидентности.
Рассмотрим различные способы задания для одного и того же графа.
1. Явное задание графа как алгебраической системы <{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение - бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d}; { (a,b), (b,a), (b,c), (c,b), (a,c), (c,a), (c,d), (d,c) }>. В таком представлении ребру соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин - его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф мы будем записывать как пару G(V,E), где V - множество вершин, а E - множество рёбер.
В дальнейшем будем опираться именно на второе определение графа.
2. Геометрический.
Рис. 6
2. Матрица смежности.
Пусть G - помеченный граф порядка n, V={1, 2, 3, …, n}. Определим nЧm-матрицу A=A(G), положив:
Аij =
A(G) называется матрицей смежности графа G.
A=
3. Матрица инцидентности.
Пусть G(n,m)- граф, V={1, 2, 3, …,n}, E={l1, l2, l3, …, ln}. Опредилим mЧn - матрицу I=I(G) условиями
Ikl =
I =
Маршруты, цепи и циклы
Маршрутом в графе
G = <V,E; I>
называется последовательность вершин и рёбер вида v0,e1,v1,e2, ..., vn-1,en,vn, где vi V, i ? [0,n], ei ? E, (vi-1,ei), (vi,ei) ? I, i ? [1, n]. Вершины v0, vn называются связанными данным маршрутом (или просто связанными). Вершину v0 называют началом, а vn - концом маршрута. Если v0 = vn, то маршрут называют замкнутым. Число n называется длиной маршрута.
Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Маршрут, в котором все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.
Минимальная из длин циклов графа называется его обхватом.
Для ориентированного графа рассматривается понятие ориентированного маршрута - это последовательность v0,e1,v1,e2, ..., vn-1,en,vn, где vi ? V, i ? [0,n], ei ? E, (vi-1,ei), (vi,ei) ? I, i ? [1, n], в которой
ei=(vi,vi+1).
Аналог цепи в этой ситуации - путь (ориентированная цепь), аналог цикла - контур (ориентированный цикл).
Пример 1.
Для графа, изображенного на рисунке, привести примеры простой цепи; цепи, не являющейся простой; маршрута, не являющегося цепью; простого цикла. Найдите обхват графа.
Рис. 7
Решение:
(1, 2) и (1, 2, 4, 7)- простые циклы;
(1, 2, 4, 7, 8, 4)- цепь, не являющееся простой;
(1, 2, 4, 7, 8, 4, 2)- маршрут, не являющийся цепью;
(1, 2, 4, 1)- простой цикл;
Обхват графа равен 3.
Графы часто используют для изображения различных отношений (например, иерархических отношений, т. е., на языке математики - отношений частичного порядка). Правда, для точного представления таких графов необходимо выразить понятие направления на графе.
Пример 2. (граф отношения делимости).
Построим граф, изображающее отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое (рис. 8).
Рис. 8
Граф называется связным, если любая пара его вершин связана.
Связными компонентами графа называются подграфы данного графа, вершины которых являются классами эквивалентности отношения свзанности в данном графе.
Цикломатическим числом графа называется число связных компонент графа плюс число рёбер минус число вершин.[3]
2.4 Деревья
Граф G = (V,E) называется деревом, если он связный и не содержит циклов. Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. Вершины степени 1 в дереве называют его листьями. Другие вершины называются внутренними вершинами.
Подграф G1 = (V1,E1) графа G = (V,E) называется остовным деревом, если G1 - дерево и V1 = V.
Для (p, q)- графа G следующие утверждения эквивалентны:
1) G - дерево;
2) G - ациклическим и q = p-1;
3) G - связный и q = p-1;
4) любые две несовпадающие вершины графа G соединяет единственная простая цепь;
5) G - без циклов, но при добавлении любого нового ребра на тех же вершинах появляется цикл.
Ориентированное дерево Т представляет собой свободный от петель ориентированный граф, соответствующий неориентированный граф которого является деревом, так что, если существует путь от вершины а к вершине b, то он единственный.
Предположим, что дерево представляет собой объект, подвижный в вершинах, и подвесим дерево за одну из его вершин так, что остальная его часть повиснет ниже этой вершины. Например, пусть задано дерево:
Рис. 9
Если подвесить его за вершину v3, получится дерево, представленное на рис. 10, а). Если подвесить дерево за вершину v4, оно будет выглядеть так, как показано на рис. 10, б).
Рис. 10
Вершина в самой верхней части каждого из изображений называется корнем дерева. Если корень дерева определен, дерево называется корневым деревом. При необходимости можно заменить корневое дерево Т на ориентированное Т, при этом дерево на рис.11, в) будет заменено деревом на рис.11,г).
Рис. 11
Такое дерево называется корневым ориентированным дерево Т, порожденным корневым деревом Т. При этом следует помнить, что это дерево отличается от неориентированного дерева и что вид ориентированного дерева зависит от выбора корня.
Если корень выбран, уровень вершины v определяется длинной единственного пути из корня в эту вершину. Высотой дерева называется длинна самого длинного маршрута от корня дерева до листа.
Если рассматривать корневое ориентированное дерево Т, порожденное данным корневым деревом Т, тогда вершина u называется родителем вершины v, а v называется сыном вершины u, если существует ориентированное ребро из u в v.
Если u - родитель v и v', тогда v и v' называются братьями. Если существует ориентированный маршрут из вершины u в вершину v, тогда u называется предком вершины v, а v называется потомком вершины u.
Если наибольшая из степеней выхода для вершин дерева равна m, тогда дерево называется m-арным деревом. В частном случае, когда m=2, дерево называется бинарным деревом.
Взвешенный граф - это граф, каждому ребру которого приписано действительное число, называемое весом ребра.[1]
2.5 Эйлеровы и гамильтоновы циклы
Эйлеровым называется цикл, проходящий по каждому ребру графа ровно один раз. Граф, имеющий эйлеров цикл, тоже будем называть эйлеровым. Такой граф можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий.
Например, граф, изображенный на рис. 12, является эйлеровым, поскольку он содержит эйлеров цикл (1, 2, 3, 4, 5, 6, 1). В этом графе есть и другие эйлеровые циклы. Ясно, что любые два таких цикла отличаются друг от друга только порядком обхода ребер.
Рис. 12
Теорема 8 (Критерий эйлеровости графа). Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин - чётные числа.
Требование связности в теореме естественно - несвязный граф может быть эйлеровым только в том случае, если только одна связная компонента содержит рёбра.
Кроме понятия эйлерова цикла в задачах часто возникает необходимость нахождения цепи, проходящей по каждому ребру ровно один раз (снимается требование замкнутости. Такие цепи будем называть эйлеровыми цепями.
Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз.
Пример гамильтонова пути в графе и графа, в котором такого пути не существует, показан на рис. 13 (а), (б) соответственно.
Рис. 13
2.6 Планарность. Двойственные графы
Планарные графы
Существует правило изображение графов на поверхности: рёбра графа должны пересекаться только своими концами, то есть в точках, представляющих вершины графа. Для графа, который может быть изображён подобным образом на плоскости, существует название: плоский граф.
Любой граф, изоморфный плоскому графу, называется планарным.
Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.
Границей грани будем считать множество вершин и ребер, принадлежащих этой грани. Например, граф, изображенный на рис. 14, имеет 4 грани:
Рис. 14
Отметим, что всякий граф имеет одну и притом единственную неограниченную грань (на рисунке это грань 4). Такая грань называется внешней, а остальные грани - внутренними.
Данное понятие грани, по существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник ``расплющиваем'' так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали ``исчезнет'', но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.
Таким образом, можно говорить о вершинах, рёбрах и гранях многогранника, а оперировать соответствующими понятиями для плоского графа.
Когда мы говорим ``плоский граф'', мы имеем в виду геометрический объект. Однако, конечно же не все его геометрические свойства нам важны (например, неважен абсолютный размер). Поэтому точнее считать, что плоский граф - это трёхосновная модель <V,E,S; I, B>, где V - множество вершин, E - множество рёбер, S - множество граней, I - отношение инцидентности, а B - отношение ограниченности, связывающее рёбра с ограничиваемыми ими гранями.
Двойственные графы
Пусть G - планарный граф. Построим граф G* следующим образом. Число вершин графа G* равно числу граней G. Каждой грани G поставим в соответствие вершину G*. Вершины в G* смежны тогда и только тогда, когда соответствующие им грани в G граничат по ребру, причем две вершины G* соединяет столько ребер, сколько общих граничных ребер у соответствующих им граней. Граф G* называется двойственным (сопряженным) графу G.
Для многогранников опять-таки существует очень наглядный способ получения двойственных графов. Он состоит в следующем. В центре каждой грани ставится точка - такие точки будут вершинами двойственного графа. Рёбрами надо соединить те вершины, грани которых разделены рёбрами в исходном графе. В результате получается многогранник, вписанный в исходный. Причём, если исходный граф правильный (полуправильный) многогранник, то и двойственный тоже будет правильным (полуправильным).[1,3]
Пример (двойственный граф). На рис. 15 изображены двойственные графы куба и октаэдра.
Рис. 15
3. Группы и их графы
3.1 Группы подстановок
Многие работы по теории групп посвящены исследованию класса групп, называемых группами подстановок (или группами перестановок). Группы подстановок особенно интересны тем, что с их помощью можно получить конкретные представления всех конечных групп. Мы увидим, что любая конечная группа изоморфна некоторой группе подстановок.
Множество взаимно однозначных отображений множества из п элементов на себя составляет группу отображений. Такие отображения называют подстановками, а группы, элементами которых являются подстановки, - группами подстановок.
Пусть множество состоит из трех элементов, расположенных в произвольном, но фиксированном порядке: a1, a2, a3. В таких случаях часто бывает удобно обращать внимание лишь на нижние индексы и считать, что мы имеем дело с последовательностью 1, 2, 3; таким образом, например, третий элемент а3 обозначается просто как 3.
Пусть теперь М -- некоторое взаимно однозначное отображение этого множества па себя:
М: ,
Или
,
Или
Будем рассматривать это отображение М как подстановку элементов упорядоченного множества (вместо 1 «подставляется» 2, вместо 2 - 3, вместо 3 - 1) или как перестановку последовательности 1, 2, 3, в результате которой получается последовательность 2, 3, 1. Именно по этой причине мы называем группу отображений конечного множества в себя группой подстановок (или группой перестановок).
Разложение подстановок в произведение циклов. Отображение, или подстановка М, устанавливает соответствия
Эта циклическая конфигурация наводит на мысль записать М в виде одной строки, заключенной в скобки:
М = (1 2 3),
и такая запись будет означать, что М отображает каждый символ в ближайший к нему справа, а последний - в первый. Подстановку М можно записать в виде цикла тремя способами:
(1 2 3), (2 3 1), (3 1 2),
так как несущественно, какой элемент указанного цикла мы поставим первым.
Пусть задано следующее отображение N множества из четырех элементов a1, a2, a3, a4:
N =
Можно ли представить это отображение в виде цикла? Так как 4 отображается в 4, то N можно представить как (1 2 3).
Если условиться, что любой элемент, не появляющийся в цикле, переходит в себя. Аналогично,
так как отображение, записанное в левой части, полностью описывается двучленным циклом (2 4), если эту запись понимать так: 2>4, 4>2, 1>1 и 3>3.
Можно ли записать с помощью циклов произвольное отображение конечного множества в себя? Например, как записать отображение
в котором в противоположность предыдущему отображению N множество соответствий не «выстраивается» в один цикл? Начнем с символа 1 и запишем справа от него его образ 2: (1 2.
Чтобы продолжить цикл далее, надо посмотреть, во что переходит символ 2. Его образом будет 4, и мы пишем (1 2 4.
Если мы попытаемся продолжить цикл дальше, то увидим, что отображение А переводит 4 в 1, и окончательно имеем (1 2 4).
Но этот цикл не есть запись отображения А, так как соответствующее ему отображение не переводит 3 в 5, а 5 в 3. Эти переходы осуществляются циклом (3 5), который каждый из остальных символов переводит в себя. Итак, ясно, что если выполняется сначала отображение
,
А затем отображение
то произведение этих отображений (их суперпозиция) есть отображение А, т.е.
.
Отметим, что поскольку эти два цикла не содержат общих символов и не оказывают друг на друга влияния, то безразлично, в каком порядке мы производим соответствующие отображения; следовательно,
(1 2 4) (3 5) = (3 5) (1 2 4).
Чтобы получить представление отображения А с помощью циклов, мы воспользовались способом, который можно применить к отображению любого конечного множества на себя. Отсюда следует, что каждую подстановку конечного множества можно записать как произведение циклов, не содержащих общих символов.
Рассмотрим теперь отображения (12) (2 3) и (2 3) (12)
и выясним, будут ли перестановочны циклы (1 2) и (2 3) с общим символом 2. Произведение (12) и (2 3) дает:
1 > 2, затем 2 > 3 и окончательно 1 > 3,
3 > 3, затем 3 > 2 и окончательно 3 > 2,
2 > 1, затем 1 > 1 и окончательно 2 > 1.
Таким образом,
(1 2) (2 3) = (1 3 2).
С другой стороны, (2 3) (1 2) дает:
1 > 1, затем 1 > 2 и окончательно 1 > 2,
2 > 3, затем 3 > 3 и окончательно 2 > 3,
3 > 2, затем 2 > 1 и окончательно 3 > 1.
Таким образом,
(2 3) (1 2) = (1 2 3),
т. е. циклы (12) и (2 3) не коммутируют. Циклы, не содержащие общих символов, перестановочны между собой, а содержащие общие символы могут и не быть перестановочны.
Конечная группа изоморфна группе подстановок. Каждую конкретную группу можно рассматривать как одно из многих возможных представлений некоторой абстрактной группы, которая изоморфна каждому из этих представлений. В сформулированной ниже теореме утверждается, что для каждой конечной абстрактной группы существует ее конкретное представление в виде некоторой группы подстановок. Напомним, что подстановка на п символах- это взаимно однозначное отображение множества из п элементов на себя.
Теорема 9. Пусть задана конечная группа порядка n. Тогда существует группа подстановок на n элементах, изоморфная данной группе.
Найдем представление в виде группы подстановок для циклической группы С4 четвертого порядка. Составим прежде всего таблицу умножения этой группы, причем элементы I, а, а2, а3 будем обозначать также символами g1, g2, g3, g4 соответственно.
|
I |
а |
а2 |
а3 |
||
|
g1 |
g2 |
g3 |
g4 |
||
|
I |
I |
а |
а2 |
а3 |
|
|
g1 |
g1 |
g2 |
g3 |
g4 |
|
|
а |
a |
а2 |
а3 |
I |
|
|
g2 |
g2 |
g3 |
g4 |
g1 |
|
|
а2 |
а2 |
а3 |
Подобные документы
Понятие алгебраической системы (группы), ключевые условия, которым она удовлетворяет и ее нейтральный элемент. Основные свойства группы. Мультипликативные и аддитивные циклические подгруппы и группы. Теорема Лагранжа и характеристика следствий из нее.
курсовая работа [173,6 K], добавлен 10.01.2015Теория групп как фундаментальное понятие и один из разделов современной математики. Основные определения и теоремы. Смежные классы: правые и левые, двойные. Нормальные подгруппы, фактор-группы. Способы их использования в решении различных задач.
курсовая работа [136,6 K], добавлен 30.03.2010Исследование свойств конечной разрешимой группы с заданными инвариантами подгруппы Шмидта. Основные свойства проекторов и инъекторов. Определение подгруппы группы, максимальной подгруппы группы, инъектора и биектора. Изложение теорем, следствий и лемм.
курсовая работа [177,7 K], добавлен 22.09.2009Группы и их подгруппы. Централизаторы и нормализаторы. Разрешимые, сверхразрешимые, нильпотентные и холловы группы. Прямое, полупрямое произведения и сплетение групп. Простейшие свойства классов Фиттинга. Нормальные классы Фиттинга и их произведение.
дипломная работа [177,3 K], добавлен 19.04.2011Сущность теории групп. Роль этого понятия в математике. Мультипликативная форма записи операций, примеры групп. Формулировка сущности подгруппы. Гомоморфизмы групп. Полная и специальная линейная группы матриц. Классические группы малых размерностей.
курсовая работа [241,0 K], добавлен 06.03.2014Характеристика и основополагающие свойства силовых подгрупп конечных групп, определение и доказательство соответствующих лемм. Понятие и свойства супердобавлений. Строение группы с максимальной и силовской подгруппой, обладающей супердобавлением.
курсовая работа [489,5 K], добавлен 05.01.2010Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Примеры алгебраических групп матриц, классические матричные группы: общая, специальная, симплектическая и ортогональная. Компоненты алгебраической группы. Ранг матрицы, возвращение к уравнениям, совместимость. Линейные отображения, действия с матрицами.
курсовая работа [303,7 K], добавлен 22.09.2009Исследование существования примарных нормальных подгрупп в бипримарных группах. Конечные бипримарные группы, разрешимые группы порядка. Порядки силовских подгрупп общей линейной группы. Доказательство лемм и теорем с использованием бинома Ньютона.
курсовая работа [527,0 K], добавлен 26.09.2009Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007
