Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
vych_metody_moe (1).docx
Скачиваний:
4
Добавлен:
01.03.2025
Размер:
619 Кб
Скачать
☆

16. Основные понятия и определения теории графов

Теория графов - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Графом G называют пару множеств (V, E), где V – множество вершин графа (точек); E – семейство ребер графа (отрезков или дуг, соединяющих вершины в пары): V={v1,v2,v3,…,vn};E={e1,e2,e3,…,em};Пример графа: То есть, элементы множества V называются вершинами графа. Элементы множества E  ребрами графа. Ребра вида (v,v), в которых первый элемент и второй совпадают, называются петлями. Или, если концевые вершины ребра совпадают, то ребро образует петлю (дугу, начало и конец которой совпадают). Если пара (v1,v2) E − ребро, то v1 и v2 называются концами этого ребра. В этом случае вершины v1 и v2 называются смежными в графе, а само ребро (v1, v2) называется инцидентным вершинам v1 и v2.

Пусть в графе есть ребро (v1,v2), тогда можно считать, что в нем есть ребро (v2,v1). Если при этом указанные ребра не различать (т. е. (v1,v2)= (v2,v1), пары считаются неупорядоченными), то граф называется неориентированным графом. Если в графе есть несколько одинаковых ребер вида (v1,v2) , то такое ребро называют кратным.

Графы можно изображать графически. Вершины изображаются точками, ребра изображаются линиями соединяющие соответствующие вершины. Число вершин графа называют порядком графа и обозначают V= n. Граф будем обозначать парой G = (V, E).

Граф G называется помеченным, если его вершинам приписаны числа 1, 2, …, п, где п − порядок графа. Граф можно задать с помощью матрицы размера n x n: А(G)=[aij], где эта матрица симметрична с нулями по главной диагонали. Она

называется матрицей смежностей графа G = (V, E). Ребра графа могут быть ориентированными или неориентированными. При изучении бинарных отношений были использованы графы, все ребра которых ориентированы. Такие графы называют ориентированными графами или орграфами. Если вершины vi и vj (i≠j) соединены ребром ek= (vi,vj), то их называют смежными вершинами. Если ребра ek, el имеют общую вершину, то их называют смежными ребрами. Если вершина vi является концом ребра ej, то vi называют вершиной, инцидентной ребру ej, а ej– ребром, инцидентным вершине vi.

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

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

в любом графе число вершин с нечетными степенями четно.

17. Способы задания графа. Матрицы смежностей и инциденций.

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

Число вершин графа называют порядком графа и обозначают /V/= n. Граф будем обозначать парой G = (V, E). Граф G называется помеченным, если его вершинам приписаны числа 1, 2, …, n, где n − порядок графа.

В приведенном выше примере графа матрица смежностей такова:

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

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

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

Цепь – это маршрут без повторяющихся ребер.

Путь – это цепь, все вершины которой (за исключением, быть может, начальной и конечной) различны.

Цикл – это цепь, у которой совпадают начальная и конечная вершины, а все остальные различны

Граф называют связным, если из каждой его вершины существует путь в любую другую его вершину. Граф, рассмотренный в примере, является, связным. Если удалить из него ребро , то он потеряет связность и распадется на компоненты: одна из компонент будет содержать вершину Д и петлю , вторая компонента – вершины А,В,С,Е, связанные между собой всеми оставшимися ребрами.

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

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

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]