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

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

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

Для точного определения графа вспомним понятие предиката. Пусть Р (x, y, z) – трехместный предикат, т. н. «упорядоченная тройка» элементов, находящихся в некотором отношении Р. Тогда точное определение графа состоит в том, что это совокупность двух множеств и предиката, указывающего, какую пару элементов первого множества соединяет тот или иной элемент второго множества. Считается, что задан граф G(X;V;Р), если задано множество V ≠  и множество X, причем (V  X ≠ ), и трехместный предикат Р, определенный на всех таких упорядоченных тройках элементов vi, vj и х, для которых vi  V, vj  V и х  X. При этом элементы множества V называют вершинами графа, а элементы множества X – ребрами. Высказывание P(vi; x; vj) читается так: ребро х соединяет вершину vi с вершиной vj, или соединяет упорядоченную пару vj vj вершин.

Предикат Р называют инцидентором графа. Иначе можно сказать, что граф – совокупность двух множеств V и X, между элементами которых определено отношение инцидентности, причем каждый элемент х  X инцидентен ровно двум элементам vi  V и vj  V.

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

х х1 х2

vi vj vi vj

а. б.

Рис. 4.2

Говорят, что ребро х, соединяющее вершины vi, и vj ,– инцидентно этим вершинам, а сами вершины – инцидентны. Об этом говорит сайт https://intellect.icu . Если порядок расположения вершин не существенен, т.е. инцидентор графа можно записать как P(vi; x; vj) и как P(vj; x; vi), то х считается неориентированным ребром, а граф называется неориентированным графом, или неорграфом. В этом случае, инцидентные ребру вершины являются равноправными (рис. 4.2а).

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

Если такое соотношение определяется графом, то порядок расположения вершин в таком графе существенен. В этом случае инцидентные каждому ребру вершины являются неравноправными и инцидентор должен быть записан однозначно [P(vi; x; vj)]. Ребро х называют ориентированным ребром или дугой графа, исходящей из вершины vi и входящей в вершину vj, а граф называют ориентированным или орграфом. При этом vi называется начальной вершиной (началом), a vj – конечной вершиной (концом) дуги х. Направление дуги обозначается стрелкой. Если начальная вершина совладает с конечной, т.е. ребро или дуга графа инцидентна одной и той же вершине, то такая дуга называется петлей (рис. 4.2б). В этом случае граф называется графом с петлями, или псевдографом.

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

а) б)

Рис. 4.3

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

а) б) в)

Рис. 4.4

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

Рис. 4.5

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

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

Рис. 4.6 Рис. 4.7

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

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

Локальной степенью ориентированного графа G в данной вершине vi будет величина ρ(vi), равная общему числу ребер и дуг, входящих и выходящих из этой вершины. Для орграфа локальная степень определится по формуле

ρ(vi) = ρ+ (vi) + ρ– (vi),

гдеρ+ (vi) – положительная полустепень (сумма исходящих дуг),

ρ– (vi) – отрицательная полустепень (сумма входящих дуг).

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

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