Содержание:
Содержание
Введение 3
1 Определение графа 4
2 Операции над графами 4
Список используемых источников 15
Список используемых источников
1 Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с.
2 Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.
3 Татт У. Теория графов: Пер. с англ. – М.: Мир, 1988. – 424 с.
4 Бурков В.Н., Новиков Д.А. Основные понятия теории графов. http://dmtsoft.ru/bn/391/as/oneaticleshablon/
5 Князьков В.С., Волченская Т.В. Введение в теорию графов. http://www.intuit.ru/department/algorithms/ingrth/2/
Выдержка из работы:
Некоторые тезисы из работы по теме Операции над графами
Введение
В математической теории графов граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или ребра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или ребрах.
Теория графов может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы.
Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную в то время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен спустя 200 лет (в 1936 г .) Д. Кенигом.
Граф - система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (геометрический способ задания графа). Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок - ребрами. Граф, в котором направление линий не выделя¬ется (все линии являются ребрами), называется неориентирован¬ным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.
Теория графов рассматривается как раздел дискретной математики (точнее - теории множеств), и формальное определение графа таково: задано конечное множество X , состоящее из n элементов (X = {1, 2,..., n}), называемых вершинами графа, и подмножество V декартова произведения X хХ, то есть VcX 2 , называемое множеством дуг, тогда ориентированным графом G называется совокупность ( X , V ) (неориентированным графом назы¬вается совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X ). Дугу между вершинами i и j , i , j еХ, будем обозначать ( i , j ). Число дуг графа будем обозначать m ( V = ( v 1, v 2,..., v m )).
Язык графов оказывается удобным для описания многих фи¬зических, технических, экономических, биологических, социаль¬ных и других систем [4].