Введение в теорию графов

Графы и способы их представления

Разбить на страницы
Показывать лекцию целиком

Введение

В последние годы особую важность приобрели те разделы математики, которые имеют отношение к развитию цифровых устройств, цифровой связи и цифровых вычислительных машин. Базой для преподавания этих дисциплин наряду с классическими методами анализа непрерывных физических моделей стали алгебраические, логические и комбинаторные методы исследования различных моделей дискретной математики.

Значительно возросла популярность теории графов – ветви дискретной математики. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" – в электронике, "социограммы" – в социологии и экономике, "молекулярные структуры" – в химии, "дорожные карты", электрические или газовые распределительные сети и т. д.

Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов – это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться. Графическая интерпретация различных моделей графов дана на Так в виде ориентированных графов можно представить любую логическую или функционально - логическую схему (,а). На таких графовых моделях можно, например, оценить быстродействие схемы. Блок-схема алгоритма может быть представлена вероятностным графом (,б), который позволяет оценить временные характеристики алгоритма, затраты процессорного времени, трудоемкость и другие. Графом типа "дерево" можно отобразить практически любую структуру организации или предприятия (,в).

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

В рамках этих исследований были разработаны многие, неизвестные ранее теоретико-графовые понятия. Теория графов имеет большую привлекательность для специалистов в области проектирования для построения эффективных алгоритмов и анализа их сложности. Использование аппарата теории графов оказало существенное влияние на разработку алгоритмов конструкторского проектирования схем. Непосредственное и детальное представление практических систем, таких, как распределительные сети, системы связи, приводит к графам большого размера, успешный анализ которых зависит в равной степени, как от эффективных алгоритмов, так и от возможностей компьютерной техники. Поэтому в настоящее время основное внимание сосредоточено на разработке и описании компьютерных алгоритмов анализа графов. В связи с этим основной упор в данном учебном пособии делается на машинные способы представления графов и алгоритмы решения задач на графах, легко реализуемых на ЭВМ.

(рис 1.1) a

Графы и способы их представления

Основные определения

Граф задается множеством точек или вершин х1, х2, ..., хn и множеством линий или ребер a1, a2, ... , am, соединяющих между собой все или часть точек. Формальное определение графа может быть дано следующим образом.

Графом называется двойка вида

G = (X, A),

где X = {xi}, i = 1, 2, ..., n – множество вершин графа, A = {ai}, i = 1, 2,... , m – множество ребер графа.

Графы могут быть ориентированными, неориентированными и смешанными (). Если ребра у множества ,а).

(рис 1.2) Виды графов: а – ориентированный граф G

Если ребра не имеют ориентации, то граф называется неориентированным (,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным (,в). В случае, когда ,г).

Дуга ,а) дуга a1 задается парой вершин (x2, x1), а дуга а3 парой (x2, x3). Если хn, хk – концевые вершины дуги ai, то говорят, что вершины хn и хk инцидентны дуге ai или дуга ai инцидентна вершинам хn и хk.

Дуга, у которой начальная и конечная вершины совпадают, называется петлей. В графе ,в) дуга a7 является петлей.

Каждая вершина орграфа хi может характеризоваться полустепенью исхода d0(хi) и полустепенью захода dt(хi).

Полустепенью исхода вершины ,а) характеристики полустепеней исхода следующие: d0(х1)=1, d0(х2)=2, d0(х3)=2, d0(х4 )=1.

Полустепенью захода вершины хi — dt(хi) называется количество дуг, входящих в эту вершину. Например, для орграфа G1: dt(х1)=2, dt(х2)=1, dt(х3)=2, dt(х4 )=1.

Очевидно, что сумма полустепеней исхода всех вершин графа, а также сумма полустепеней захода всех вершин графа равна общему числу дуг графа, т. е.

$$\sum ^{n}_{i=1}d_{0}(x_{i})=\sum ^{n}_{i=1}d_{t}(x_{i})=m$$

где n – число вершин графа, m – число дуг.

Каждая вершина неориентированного графа хi может характеризоваться степенью вершины d(хi).

Степенью вершины ,б) характеристики степеней следующие: d(х1)=2, d(х2)=3, d(х3)=3, d(х4 )=2.

Способы описания графов

Теоретико-множественное представление графов

Граф описывается перечислением множества вершин и дуг. Примеры описания приведены для орграфов на и .

G4 = (Х, А),

где Х = {хi}, i = 1, 2, 3, 4 – множество вершин; А = {ai }, i = 1, 2, ..., 6 – множество дуг, причем А = {(х1, х2), (х4, х2), (х2, х4 ), (х2, х3), (х3, х3), (х4 , х1)}.

(рис 1.3) Орграф G4

G5 = (X, A),

где X = {B, C, D, E, F} – множество вершин графа, A = {ai}, i = 1, 2, ..., 5 – множество дуг графа, причем a1 = (F, B), a2 = (F, D), a3 = (B, E), a4 = (E, C), a5 = (C, D).

(рис 1.4) Орграф G5

Задание графов соответствием

Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины.

Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).

Отображением вершины хi — Г(хi) является множество вершин, в которые существуют дуги из вершины хi, т. е. $$Г(х_{i}) = \{ х_{j}:\exists дуга (х_{i}, х_{j})\in A\}$$.

Так для орграфа на описание заданием множества вершин и соответствия выглядит следующим образом:

G4=(X, Г),

где X = {хi}, i = 1, 2, ..., 4 – множество вершин, Г(х1) = { х2 }, Г(х2) = { х3, х4 }, Г(х3) = { х3 }, Г(х4) = { х1, х2 } – отображения.

Для неориентированного или смешанного графов предполагается, что соответствие ,б Г(х2) = { х1, х3, х5 }, Г(х4) ={ х3, х5} и т. д.

Матричное представление графов

Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.

Матрица смежности – это квадратная матрица размерностью n x n, (где n – число вершин графа ), однозначно представляющая его структуру.

A = {aij}, i, j = 1, 2, ..., n, а каждый элемент матрицы определяется следующим образом:

aij = 1, если $$\exists$$ дуга (хi, хj),

aij = 0, если нет дуги (хi, хj).

Если элемент на диагонали (i=j) равен единице, значит, вершина i имеет петлю.

Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n – количество вершин графа, а m – количество дуг графа. Обозначается матрица инциденций B = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m .

Каждый элемент матрицы определяется следующим образом:

bij = 1, если хi является начальной вершиной дуги aj,

bij = –1, если хi является конечной вершиной дуги aj,

bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.

Таким образом, нулевой столбец j в матрице инциденций свидетельствует о том, что дуга aj яляется петлей.

На , а,б приведен граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов ,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = { х2, х5}.

(рис 1.5) Орграф и его матричное представление: а – орграф; б – матрица смежности; в – матрица инциденций

Для графа на ,а матрица инциденций приведена на ,в. Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент равный 1 и один – равный – 1, либо все элементы столбца равны 0.

Для неориентированного графа, матрица инциденций определяется так же, за исключением того, что все элементы, равные –1, заменяются на 1.

Страницы:

Введение

В последние годы особую важность приобрели те разделы математики, которые имеют отношение к развитию цифровых устройств, цифровой связи и цифровых вычислительных машин. Базой для преподавания этих дисциплин наряду с классическими методами анализа непрерывных физических моделей стали алгебраические, логические и комбинаторные методы исследования различных моделей дискретной математики.

Значительно возросла популярность теории графов – ветви дискретной математики. Графы встречаются во многих областях под разными названиями: "структуры" в гражданском строительстве, "сети" – в электронике, "социограммы" – в социологии и экономике, "молекулярные структуры" – в химии, "дорожные карты", электрические или газовые распределительные сети и т. д.

Родившись при решении головоломок и игр, таких, например, как задача о кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Для специалистов по вычислительной технике, информационным системам и системам цифровой связи теория графов – это удобный язык выражения понятий из этой области; многие результаты теории графов имеют непосредственную связь с задачами, с которыми им приходится сталкиваться. Графическая интерпретация различных моделей графов дана на Так в виде ориентированных графов можно представить любую логическую или функционально - логическую схему (,а). На таких графовых моделях можно, например, оценить быстродействие схемы. Блок-схема алгоритма может быть представлена вероятностным графом (,б), который позволяет оценить временные характеристики алгоритма, затраты процессорного времени, трудоемкость и другие. Графом типа "дерево" можно отобразить практически любую структуру организации или предприятия (,в).

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

В рамках этих исследований были разработаны многие, неизвестные ранее теоретико-графовые понятия. Теория графов имеет большую привлекательность для специалистов в области проектирования для построения эффективных алгоритмов и анализа их сложности. Использование аппарата теории графов оказало существенное влияние на разработку алгоритмов конструкторского проектирования схем. Непосредственное и детальное представление практических систем, таких, как распределительные сети, системы связи, приводит к графам большого размера, успешный анализ которых зависит в равной степени, как от эффективных алгоритмов, так и от возможностей компьютерной техники. Поэтому в настоящее время основное внимание сосредоточено на разработке и описании компьютерных алгоритмов анализа графов. В связи с этим основной упор в данном учебном пособии делается на машинные способы представления графов и алгоритмы решения задач на графах, легко реализуемых на ЭВМ.

(рис 1.1) a

Графы и способы их представления

Основные определения

Граф задается множеством точек или вершин х1, х2, ..., хn и множеством линий или ребер a1, a2, ... , am, соединяющих между собой все или часть точек. Формальное определение графа может быть дано следующим образом.

Графом называется двойка вида

G = (X, A),

где X = {xi}, i = 1, 2, ..., n – множество вершин графа, A = {ai}, i = 1, 2,... , m – множество ребер графа.

Графы могут быть ориентированными, неориентированными и смешанными (). Если ребра у множества ,а).

(рис 1.2) Виды графов: а – ориентированный граф G

Если ребра не имеют ориентации, то граф называется неориентированным (,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным (,в). В случае, когда ,г).

Дуга ,а) дуга a1 задается парой вершин (x2, x1), а дуга а3 парой (x2, x3). Если хn, хk – концевые вершины дуги ai, то говорят, что вершины хn и хk инцидентны дуге ai или дуга ai инцидентна вершинам хn и хk.

Дуга, у которой начальная и конечная вершины совпадают, называется петлей. В графе ,в) дуга a7 является петлей.

Каждая вершина орграфа хi может характеризоваться полустепенью исхода d0(хi) и полустепенью захода dt(хi).

Полустепенью исхода вершины ,а) характеристики полустепеней исхода следующие: d0(х1)=1, d0(х2)=2, d0(х3)=2, d0(х4 )=1.

Полустепенью захода вершины хi — dt(хi) называется количество дуг, входящих в эту вершину. Например, для орграфа G1: dt(х1)=2, dt(х2)=1, dt(х3)=2, dt(х4 )=1.

Очевидно, что сумма полустепеней исхода всех вершин графа, а также сумма полустепеней захода всех вершин графа равна общему числу дуг графа, т. е.

$$\sum ^{n}_{i=1}d_{0}(x_{i})=\sum ^{n}_{i=1}d_{t}(x_{i})=m$$

где n – число вершин графа, m – число дуг.

Каждая вершина неориентированного графа хi может характеризоваться степенью вершины d(хi).

Степенью вершины ,б) характеристики степеней следующие: d(х1)=2, d(х2)=3, d(х3)=3, d(х4 )=2.

Способы описания графов

Теоретико-множественное представление графов

Граф описывается перечислением множества вершин и дуг. Примеры описания приведены для орграфов на и .

G4 = (Х, А),

где Х = {хi}, i = 1, 2, 3, 4 – множество вершин; А = {ai }, i = 1, 2, ..., 6 – множество дуг, причем А = {(х1, х2), (х4, х2), (х2, х4 ), (х2, х3), (х3, х3), (х4 , х1)}.

(рис 1.3) Орграф G4

G5 = (X, A),

где X = {B, C, D, E, F} – множество вершин графа, A = {ai}, i = 1, 2, ..., 5 – множество дуг графа, причем a1 = (F, B), a2 = (F, D), a3 = (B, E), a4 = (E, C), a5 = (C, D).

(рис 1.4) Орграф G5

Задание графов соответствием

Описание графов состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины.

Соответствием Г называется отображение множества Х в Х, а граф в этом случае обозначается парой G = (X, Г).

Отображением вершины хi — Г(хi) является множество вершин, в которые существуют дуги из вершины хi, т. е. $$Г(х_{i}) = \{ х_{j}:\exists дуга (х_{i}, х_{j})\in A\}$$.

Так для орграфа на описание заданием множества вершин и соответствия выглядит следующим образом:

G4=(X, Г),

где X = {хi}, i = 1, 2, ..., 4 – множество вершин, Г(х1) = { х2 }, Г(х2) = { х3, х4 }, Г(х3) = { х3 }, Г(х4) = { х1, х2 } – отображения.

Для неориентированного или смешанного графов предполагается, что соответствие ,б Г(х2) = { х1, х3, х5 }, Г(х4) ={ х3, х5} и т. д.

Матричное представление графов

Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.

Матрица смежности – это квадратная матрица размерностью n x n, (где n – число вершин графа ), однозначно представляющая его структуру.

A = {aij}, i, j = 1, 2, ..., n, а каждый элемент матрицы определяется следующим образом:

aij = 1, если $$\exists$$ дуга (хi, хj),

aij = 0, если нет дуги (хi, хj).

Если элемент на диагонали (i=j) равен единице, значит, вершина i имеет петлю.

Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n – количество вершин графа, а m – количество дуг графа. Обозначается матрица инциденций B = {bij}, i = 1, 2, ..., n, j = 1, 2, ..., m .

Каждый элемент матрицы определяется следующим образом:

bij = 1, если хi является начальной вершиной дуги aj,

bij = –1, если хi является конечной вершиной дуги aj,

bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.

Таким образом, нулевой столбец j в матрице инциденций свидетельствует о том, что дуга aj яляется петлей.

На , а,б приведен граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов ,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = { х2, х5}.

(рис 1.5) Орграф и его матричное представление: а – орграф; б – матрица смежности; в – матрица инциденций

Для графа на ,а матрица инциденций приведена на ,в. Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент равный 1 и один – равный – 1, либо все элементы столбца равны 0.

Для неориентированного графа, матрица инциденций определяется так же, за исключением того, что все элементы, равные –1, заменяются на 1.

Предыдущее занятие Следующее занятие
Вернуться к учебному плану
^