ГРАФЫ И ИХ АВТОМОРФИЗМЫ

ВВЕДЕНИЕ 4
1 Основные понятия графов 6
1.1 Виды графов и их способы задания 6
1.2 Матричные способы задания графов 8
1.3 Маршруты и циклы, пути и контуры в графе 10
1.4 Связность графа 12
2 Важные классы графов 15
2.1 Деревья 15
2.2 Двудольные графы 17
2.3 Планарные графы 17
3 Изоморфизм графа 19
3.1 Определение изоморфизма 19
3.2 Инварианты графов 20
4 Группа автоморфизмов графа 21
5 Задачи теории графов 23
ЗАКЛЮЧЕНИЕ 26
ЛИТЕРАТУРА 27

Купить

Теория графов - это раздел дискретной математики, рассматриваемый множества, на которых зaдaны отношения между элементами. Объекты тaкого родa могут быть nредстaвлены в виде изображений, которые состоят из точек, кружочков или других фигур, соединенных линиями. Точки соответствуют элементам множествa, а линии показывают связи, или, другими словами, отношения между ними. Такие рисунки, как правило, называют графами, но рисунок - лишь один из способов задания графа.
Считается, что основателем теории графов был Леонард Эйлер. В 1736 году в одном из своих писем к итальянскому математику и инженеру Маринони он сформулировал и предложил решение задачи о семи кёнигсбергских мостах. Задача заключалась в том, что возможно ли обойти все семь мостов непрерывно, проходя только один раз через каждый мост. Впоследствии эта задача стала одной из классических задач теории графов. Побуждение к развитию теория графов получила на рубеже XIX и XX столетий, когда явно увеличилось число работ в области топологии и комбинаторики. Как отдельная математическая дисциплина теория графов была впервые предложена в работе венгерского математика Кёнинга в 30-е годы XX столетия. Ему приписывается введение термина «граф».
В последнее время графы и относящиеся к ним методы исследований применяются в разных областях науки: в теории планирования и управления, математической лингвистике, психологии, экономике, социологии, биологии, медицине. Фактически графами являются схемы различных коммуникаций, химических соединений, блок-схемы компьютерных программ и многое другое. Можно взять использование графов в геоинформационных системах как наиболее жизненный пример. Имеющиеся или заново проектируемые дома, сооружения и т. п. считаются за вершины, а соединяющие их дороги, линии электропередачи и т. п. — за рёбра. Использование различных вычислений на таком графе дает возможность найти ближайший магазин или рассчитать оптимальный маршрут.
Теория графов имеет как плюсы, так и минусы в решении отдельных задач. Преимуществом является: наглядность, доступность и конкретность. Большой недостаток заключается в том, что не каждую задачу возможно привести под теорию графов.
Тема является актуальной за счет того, что теория графов делает большие успехи в развитии, также находит широкое применение в различных областях. Это направление имеет возможность открывать нечто новое, поскольку теория графов содержит огромное число проблем, которые на сегодняшний день являются не решенными, и такое же число не доказанных гипотез.
Хотелось бы показать применение в различных сферах:
Графы и информация. В теории информации крайне важную роль представляют двоичные деревья. Допустим, нам необходимо закодировать некоторое число сообщений в виде конечных последовательностей разной длины, которые состоят из нулей и единиц. В случае если вероятности кодовых слов указаны, то наилучшим будут считать код, где средняя длина слов меньше, чем в других распределениях вероятностей. Алгоритм Хаффмана дает нам возможность решить такую задачу о построении оптимального кода.
В рамках теории поиска двоичные кодовые деревья допускают интерпретацию. Вдобавок каждой вершине соответствует вопрос, на который следует ответить либо «да», либо «нет». Этим ответам сопоставляется два ребра, которые исходят из вершины. «Опрос» можно завершить, когда получится определить требования.
Следовательно, если кому-либо потребуется взять интервью у различных людей, то план интервью, в котором ответ на следующий вопрос зависит от заранее неизвестного ответа на предыдущий вопрос, представляется в виде двоичного дерева.
Графы и физика. Для радиолюбителей сложнее всего показалась задача по конструированию печатных схем. Печатной схемой называется пластинка из некоторого диэлектрика (изолирующего материала), на котором вытравлены дорожки наподобие металлических полосок. Возможность пересекаться эти дорожки имеют только в определенных точках, где установлены требующиеся элементы (диоды, триоды, резисторы и другие), в иных местах их пересечение вызовет замыкание электрической цепи.
Для решения этой задачи требуется построить плоский граф, с вершинами в заданных точках.
Графы и экономика. Теория графов применяется в экономике, к примеру, когда следует выбрать подходящий вариант развозки товаров по магазинам. Составляя большие проекты, в которых содержатся разного рода работы, может возникнуть ситуация, когда ту или иную работу возможно начать только по окончании других. Таким образом, при строительстве дома нельзя перейти к отделочным работам, пока не выстроены стены, а стены можно выстроить только после укладки фундамента. Такая последовательность работ представляется в виде сетевых графиков, которые используются при планировании действий предприятия.
Следовательно, зная дату начала строительства и время, за которое следует выполнить каждую работу, можно определить, когда необходимо доставить материалы или пригласить бригады специалистов.
Сетевые графики также применяют проектировщики машин с огромным числом деталей, диспетчеры железных дорог и прочие специалисты.
Таким образом, можно сделать вывод, что теория графов бесспорно имеет практическую ценность.
Невозможно охватить всю проблематику теории графов. Поэтому были выделены темы, которые касаются связности, поиска путей, циклов в графах, также деревьев - одного из наиболее встречаемого вида графов.

Купить