Впервые в работе Л.Эйлера, где он описывал решение математических развлекательных задач, головоломок,и задачу о семи Кенигсбергских мостах(1736): можно ли пройти по каждому из 7 мостов один раз и

Элементы теории графов.

Впервые в работе Л.Эйлера, где он описывал решение математических развлекательных задач, головоломок,и задачу о семи Кенигсбергских мостах(1736): можно ли пройти по каждому из 7 мостов один раз и вернуться в исходную точку. Эйлер доказал, что задача решения не имеет.

Семь мостов: a,b,c,d,e,f,g. Каждый мост-ребро, вершина- часть суши.

Рис1.

Широкое развитие теория графов получила в 50-х г.г. XX века в связи со становлением кибернетики, развитием электроники и вычислительной техники. Существенный вклад в теорию графов (в первой половине XX века) внесли немец. ученые Кирхгоф(методы расчета электрических цепей) и..

Пусть на плокости задано некоторое множество вершин X и множество U соединяющих их дуг.

Опр. Графом называется бинарное отношение множеств X и U: G=(X,U)

Дуги могут соединять все или некоторые вершины(рис2)
Вершины: a,b,c,d,e,f,g,h;
Дуги: (a,h), (c,b), (d,c), (c,d), (d,d), (c,e), (e,d), (g,h).

Рис2.

Примеры графов: карта дорог на местности, схемы соединения приборов, генеологическое дерево, задача коммивояжера и т.д.

Опр. Две вершины a,b называются смежными если они различны и существует дуга, идущая из «a» в «b».

Опр. Дуга и называется инцидентной вершине a, если она зоходит в эту вершину или исходит из нее.

Путем в графе G называется такая последовательность дуг, в которой конец каждой последующей дуги совпадает с началом предыдущей.

Длина пути- число входящих в этот путь дуг.

Пусть может быть конечным и бесконечным. Путь в котором ни одна дуга не проходится дважды, называется элементарным.

При изображении графа геометрические св-ва ребра(длина, кривизна и т.д) и взаимное расположение вершин являются несущественными(рис3)

Рис3.

Граф незывается правильным, если его ребра не имеют общих точек, отличных о вершин графа. На рис3: G2-правильный, G1- неправильный, т.к. ребра (1;3) и (2:4) имеют общую точку, не являющуюся вершиной графа.

Для любого графа существует его правильная реализация в пространстве, но не любой граф можно правильно реализовать на плоскости. Правильно реализованные на плоскости графы наз плоскими.

Чтобы реализовать неплоские графы в пространстве в микроэлектронике создали технологию многослойных печатных плат.

Ребра, инцидентные одной и той же паре вершин наз параллельными или кратными(рис4).Ребра x,y,z параллельны.

Рис4.

Граф называется полным, если каждая пара его вершин соединена ребром и граф не содержит петель и кратных ребер.

Опр. Граф наз ориентированным, если указано направление дуг и неориентированным, если такое направление не указано.

Граф называется петлей, если его начало и конец совпадают.

Степенью (валентностью) вершины называют число инцидентных ей ребер. Кратностью пары вершин называется число соединяющих их ребер или дуг.

Подграфом графа G наз граф, в который входит лишь часть вершины графа G вместе с их дугами (рис 2 подграф отмечен пунктирным контуром)

Частным графом графа G наз граф, в который входит лишь часть дуг вместе с вершинами.

Пример: Карта дорог России- граф, дороги Татарстана- его подграф, а главные дороги- частный граф.

Примечание: Граф явл-ся полностью заданным, если нумерация его вершин и ребер зафиксирована. Графы, отличающиеся только нумерацией вершин называется изоморфными. Изоморфные-отношение эквивалентности на графах, т.е. оно рефлексивно, симметрично, транзитивно. В математике «изоморфизм»- похожесть.однотипных объектов: G1 G2 (рис5)

Рис5

Очевидно, каждое ребро связано с двумя вершинами. Первая теорема в теории графов, установленная Эйлером, гласит:

Для вершин орграфа(графа с ориентированными ребрами) определяются две локальные степени:

- число ребер с началом в вершине V.

- число ребер входящих в вершину V.

Петля дает вклад 1 в обе степени.

Матрица смежности S: элементы матрицы- количество ребер, проходящих через данную вершину.

0 1 0 0

S= 0 0 1 1

1 0 0 1

0 0 0 0

Граф полный, т.к. каждая пара вершин соединена ребром. Указаны расстояния между пунктами. Из пункта М нужно развести почту в остальные пункты. Как выбрать кратчайший маршрут?

Построим новый граф:

Дата добавления: 2015-10-21