double arrow

Вопрос 2- 4. Основные понятия теории графов

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

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

В теории графов используется понятие мультимножества — неупорядоченной совокупности элементов, в которой могут быть одинаковые элементы. Граф задается множеством V и мультимножеством Е, элементами которого являются пары элементов множества V. Обычно граф записывают в виде G(V, E). Элементы множества V часто называют вершинами. Пусть граф имеет п вершин, например V = {v, v,..., v }. Общеприняты следующие соглашения. Если пары (v., v.) и (v., v) не различают при любых i и j, то граф называют неориентированным, а элемент мультимножества Е — ребром. Если пары (v., v.) и (v., v.) различают при любых i и j, то граф называют ориентированным, а элемент мультимножества Едугой. В остальных случаях граф называют смешанным.

Граф, в котором Е является мультимножеством (существуют две вершины, которые соединены более чем одним ребром или дугой), называется мулътиграфом.

Наиболее часто рассматривают неориентированные графы, не имеющие кратных ребер и не имеющие петель (пар (v., v.)).

Пример задания неориентированного графа G(V, E):

V= {1,2,3,4,5}, E={(1,2), (2,3), (3,4)}.

Более наглядным является геометрическое представление графа. Вершинам графа ставят в соответствие точки плоскости, а ребрам (дугам) — линии (ориентированные линии), соединяющие эти точки. В качестве примера можно рассмотреть геометрическую интерпретацию рассмотренного выше графа G.

Рассмотрим некоторые понятия теории графов.

Вершины v. и v. графа G(V, Е) называются смежными, если в Е имеется пара (v., v). Вершина v инцидентна ребру (v., v). Степенью вершины графа называется число ребер, инцидентных ей.

Пусть V — подмножество множества V, может быть и совпадающее с V, и пусть Е' — подмножество множества Е. Граф G'(V,E) называется подграфом графа G(V, E), если E не содержит элементов (ребер или дуг), инцидентных вершинам, не принадлежащим множеству V.

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

Маршрут называется открытым, если его начальная и конечная вершины различны, в противном случае он называется замкнутым.

Маршрут называется цепью, если все его ребра различны.

Открытая цепь называется путем, если все ее вершины различны.

Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.

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

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

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

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

Задание графа описанием его составляющих V и Е не всегда является оптимальным для решения на компьютере задач о его свойствах.

Рассмотрим два наиболее используемые способа представления графов.

Матрица смежности. Граф с п вершинами задается булевой квадратной (n, n)-матрицей, в которой элемент пересечения i-й строки и j-го столбца равен 1, если существует пара (v., v.) (иначе этот элемент равен 0). Отметим, что степень вершины v. равна сумме элементов i-й строки.

Матрица инцидентности. Граф с п вершинами и R ребрами задается булевой (n, R)-матрицей, строкам (столбцам) которой сопоставлены вершины (ребра)графа. Элемент пересечения i-й строки и j-го столбца равен 1, если i-я вершина графа инцидентна j-му ребру (иначе этот элемент равен 0). Матрица инцидентности полезна для решения сетевых задач.

Рассмотрим некоторые часто используемые в информатике типы графов.

Неориентированный граф без петель называется полным, если каждая его вершина смежна со всеми остальными вершинами. Отметим, что полный граф с п вершинами имеет п(п - 1)/2 ребер.

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

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

деревья, в которых степень всех вершин, кроме корня, не превосходит 3;степень корня не превосходит 2. Отметим, что дерево является двудольным графом.

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

Одним из применений теории графов в нашем курсе является определение типов структур данных и типов организации баз данных.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: