Тема 4. Элементы теории графов.
Теория графов – раздел дискретной математики. Ее развитие тесно связано с развитием математической логики, автоматики, теории игр, математической экономики, математической лингвистики и других наук, где в отличие от классического анализа непрерывных величин на первый план выдвигаются рассуждения и построения дискретно-комбинаторного характера.
Именно дискретный характер практических и теоретических задач привел к значительным трудностям при их анализе и решении. При решении этих задач возникло множество способов решения. Следовательно, возникла необходимость применять универсальные методы. Так возникла теория графов.
Графические представления в широком смысле – это любые наглядные отображения исследуемых систем, процессов, явлений на плоскости. К ним могут быть отнесены:
· рисунки;
· чертежи;
· графики;
· планы и карты местности;
· блок-схемы процессов;
· диаграммы.
Такие изображения наглядно представляют различные взаимосвязи: пространственные, хронологические, логические, структурно-следственные.
Мощным и наиболее исследованным классом объектов, относящихся к графическим представлениям, являются графы. Их язык нагляден и удобен в формальных описаниях.
Определение: Графом называется пара множеств 
, где Х – непустое множество вершин 
, Е - множество ребер 
.
При изображении графа несущественны геометрические свойства ребер (длина, толщина, кривизна и т.п.) и взаимное расположение вершин на плоскости. Таким образом, граф – это свободная конструкция, для которой имеет значение лишь факт наличия связи между вершинами.
|
|
|
Если вершины 
и 
принадлежат некоторому ребру, то говорят, что ребро инцидентно вершинам (они будут называться смежными).
Если ребро инцидентно одной и той же вершине, то оно называется петлей.
Вершина, не инцидентная никакому ребру, называется изолированной.
Если в графе есть вершины, соединенные с двумя или более другими, то он называется мультиграф.
Число ребер, исходящих из данной вершины, называется степенью или кратностью данной вершины.
Маршрутом длины m называется некоторая последовательность m ребер графа такая, что вершины двух последних ребер в последовательности совпадают. Маршрут может быть замкнутым, если приводит в ту же вершину.
Две вершины называются связанными, если существует маршрут их соединяющий.
Граф, в котором все вершины связаны, называется связным.
История.
Первая работа о графах появилась в 1736 году в публикации Петербургской Академии наук. Это была статья Леонарда Эйлера по поводу задачи о кенигсбергских мостах. Задача состояла в следующем.
|
|
|
Кенигсберг (ныне Калининград) расположен на берегах реки Прегель и двух ее островах. В городе было семь мостов, расположенных следующим образом:
По воскресениям горожане любили прогуливаться по берегам реки, ее островам и мостам и при этом возникла такая задача – возможно ли, выйдя из какого-то места, вернуться в него, обойдя все мосты в точности по одному разу? Для решения этой задачи Эйлер построил граф, вершинами которого были берега и острова, а ребрами – соединяющие их мосты (сам термин «граф» был введен ровно 200 лет спустя в монографии Кенига).
Задача состоит в том, чтобы найти цикл, проходящий по всем ребрам в точности по одному разу. Такая линия на графе называется Эйлеровой линией, граф, в котором это возможно, - Эйлеров граф. Это невозможно, так как если бы такой цикл существовал, то он в каждую вершину входил бы, и выходил бы одно и то же число раз и, значит, степени всех вершин графа должны были бы быть четными, что не имеет места для графа этой задачи.
Типы задач, связанных с графами:
1. лабиринты;
2. автомобильные дороги, соединяющие города;
3. линии электропередач;
4. сетевое планирование;
5. назначение на должность;
6. одностороннее движение;
Особые виды графов:
|
|
|
1. Частичный граф (или суграф) – граф, содержащий все вершины, но часть ребер.
2. Подграф – граф, содержащий подмножество вершин и все ребра их соединяющие.
3. Ориентированным графом (или орграфом) D называется пара множеств 
, где Х – непустое множество вершин , А – множество упорядоченных пар вершин, называемых дугами. 
(множество А является подмножеством декартова произведения множества вершин на себя).
4. Дерево – это связный граф, не имеющий циклов. У дерева с n вершинами будет n-1 ветка (ребро). Это минимальное количество ребер, чтобы граф был связным. Если убрать одно ребро, то граф распадется на компоненты. Если добавить ребро, то появится цикл. Несвязный граф, компонентами которого являются деревья, называется лес.
Ориентированный граф можно изображать с помощью матрицы смежности. Это квадратная матрица, содержащая n строк и n столбцов, если граф имеет n вершин. Элементы матрицы 
равны количеству ребер, соединяющих соответствующие вершины.
Пример:
Дата добавления: 2015-12-17; просмотров: 23; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!