Основные понятия теории графов

Графы, их характеристика и типы

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

• — множество населенных пунктов, связанных дорогами;
• — множество точек потребления ресурсов на производственном предприятии, связанных логистическими потоками со складами и между собой;
• — иерархия подчиненности (между сотрудниками, подразделениями и т. д.).

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

Множество G, объединяющее непустое множество вершин V и множество связей U. называется графом.

где V = {гц, v₂,…, t'_n}, п — количество вершин; U = {и_ь и₂,…, г^}, т — количество связей. В общем случае п Ф т. Между элементами множества V устанавливаются связи щ = (vj, vк), т.с. связь щ связывает вершины Vj и v^.

Граф называется нащхшленнылг (ориентированным), если каждая связь имее^гг начальную и конечную вершины (рис. 8.1). Переход из вершины гд в вершину v₂ есть, а наоборот нет. В направленном графе связь называется дугой.

Рис. 8.1. Направленный граф.

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

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

Рис. 8.2. Ненаправленный граф.

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

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

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

Последовательность дуг, таких, что конец предыдущей дуги совпадает с началом последующей, называется путем т на графе (имеется в виду ориентированный граф). Последовательность дуг может быть различной, например (см. рис. 8.1): гп = («^ щ),

тпг = гп₃ = (щ, и2, и₃, и₄, и₅).

Замкнутый путь называется контуром, если начало и конец пути находятся на одной и той же вершине (т₂ и га₃). Если граф ненаправленный, то термин «путь» заменяется цепью, а контур — циклом.

Длиной пути направленного взвешенного графа называется сумма весов всех дуг, входящих в данный путь, например, /(т₂) = 1(щ) + 1(щ) + 1(щ).

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

Направленный граф называется:

• — сильно связанным, если любая вершина достижима из любой другой (граф на рис. 8.1);
• — слабо связанным (односторонне связанным), если для любых двух вершин с* и Vj хотя бы одна из них достижима из другой (граф на рис. 8.1, если убрать дугу щ)-,
• — несвязанным, если существует вершина, которая недостижима ни из одной вершины графа (ни из одной вершин нельзя достигнуть вершины в графе на рис. 8.3).

Рис. 8.3. Несвязанный граф

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

Вершина Vj и дуга Uj называются инцидентнъши, если вершина гц принадлежит этой дуге Uj. В противном случае — не инцидентными. Дуга отрицательно инцидентна вершине, если дуга входит в вершину (рис. 8.4, а). Дуга положительно инцидентна вершине, если дуга выходит из вершины (рис. 8.4, б).

Рис. 8.4. Инцидентные вершина и дуга Степень вершины — количество дуг, инцидентных данной вершине. Количество отрицательно инцидентных дуг называется полу степенью захода вершины, а количество положительно инцидентных дуг — полустепенью исхода вершины. Если степень вершины равна нулю, то эта вершина изолирована.

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

Если в графе G — {КС/} из множества V удалить часть вершин, а из множества U часть дуг, инцидентных этим удаленным вершинам (нс может быть дуги с одной вершиной), то получается подграф G' = {V, С/'}, где V С V, U' С U. На рис. 8.5 приведен подграф, полученный из графа, приведенного на рис. 8.1, у которого удалены вершина V4 и дуги гц, щ.

Рис. 8.5. Подграф.

Если в графе G = {V, U} из множества U удалить часть дуг, а из множества V не удалить ни одной вершины (вершина может быть без дуги), то получается частичный граф G' = {V, С/'}, где U' С U. На рис. 8.6 приведен частичный граф, полученный из графа (см. рис. 8.1), у которого удалена дуга щ.

Рис. 8.6. Частичный граф.

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

Рис. 8.7. Граф типа дерево (а) и сеть (б).