Графы и их применение

     Пересечение графов

     Пусть G₁(X₁,E₁) и G₂(X₂,E₂) – произвольные графы. Пересечением G₁ÇG₂ графов G₁ и G₂ называется граф с множеством вершин X₁ÇX₂ с множеством ребер (дуг) E = E₁ÇE₂

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

     G₁ÇG₂  = G₂ÇG₁– свойство коммутативности;

     G₁Ç (G2ÇG3) = (G1ÇG2) Ç G₃ – свойство ассоциативности.

     Для того чтобы операция пересечения  была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X=Æ). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E=Æ). Пустой граф обозначается символом Æ. Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X₁ÇX₂=Æ. В этом случае говорят о непересекающихся графах.

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

     X₁ = {x₁, x₂, x₃}; X₂ = {x₁, x₂, x₃, x₄};

     X = X₁ÇX₂ = {x₁, x₂, x₃}.

     Аналогично  определяем множество E дуг результирующего графа:

     E₁ = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₂, x₃), (x₃, x₂)};

     E₂ = {(x₁, x₃), (x₂, x₁), (x₂, x₃), (x₂, x₄), (x₃, x₁)};

     E = E₁ÇE₂ = {(x₁, x₃), (x₂, x₁)}.

     Теорема. Пусть G₁ и G₂ – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A₁ и A₂ – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1ÇG2 является матрица A = A₁ÇA₂ образованная поэлементным логически умножением матриц A₁ и A₂.

     Рассмотрим  выполнение операции пересечения для  графов с несовпадающим множеством вершин.

     Пусть G₁(X₁,E₁) и G₂(X₂,E₂)  – графы без параллельных ребер, множества X₁ и X₂ вершин графов не совпадают, а A₁ и A₂ – матрицы смежности вершин графов. Для таких графов операция пересечения может быть выполнена так.

     В соответствии с определением операции пересечения графов найдем множество  вершин результирующего графа как X₁ÇX₂. Построим вспомогательные графы G’₁ и G’₂, множества вершин которых есть множество X₁ÇX₂, а множество ребер (дуг) определяется множествами E’₁ и E’₂ всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’₁ и A’₂ смежности вершин этих графов могут быть получены из матриц A₁ и A₂ путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество X1ÇX2.

     Применив  к графам G’₁ и G’₂ теорему, найдем матрицу смежности вершин графа G’₁ÇG’₂ как A’₁ÇA’₂. Очевидно, что полученной матрице смежности вершин  соответствует граф, множество вершин которого равно X₁ÇX₂, а множество ребер определяется, как E₁ÇE₂, что соответствует операции пересечения графов. 

     Композиция  графов

     Пусть G₁(X,E₁) и G₂(X,E₂) — два графа с одним и тем же множеством вершин X. Композицией G₁(G₂) графов G₁ и G₂ называется граф с множеством вершин E, в котором существует дуга (x_i,x_j) тогда и только тогда, когда существует дуга (x_i,x_k), принадлежащая множеству E₁, и дуга (x_k,x_j), принадлежащая множеству E₂.

     Рассмотрим  выполнение операции композиции G₁(G₂) на графах, изображенных на рис. 4. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (x_i, x_k), принадлежащие графу G₁, во втором — ребра (x_k, x_j), принадлежащие графу G₃, а в третьем — результирующее ребро (x_i, x_j) для графа G₁(G₂).

     Заметим, что дуга (x₁,x₃) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x₁,x₃) учитывается только один раз, т.е. E = {(x₁,x₁), (x₁,x₃), (x₂,x₁), (x₂,x₃)}

     На  рис. 4 изображены графы G₁ и G₂ и их композиции G₁(G₂). На этом же рисунке изображен граф G₂(G₁).

     Декартово произведение графов. Пусть G₁(X,E₁) и G₂(Y,E₂) — два графа. Декартовым произведением G₁(X,E₁)´G₂(Y,E₂) графов G₁(X,E₁) и G₂(X,E₂) называется граф с множеством вершин X´Y, в котором дуга (ребро), идущая из вершины (x_iy_j) в (x_ky_l), существует тогда и только тогда когда существует дуга (x_ix_k), принадлежащая множеству дуг E₁ и j = l или, когда существует дуга (y_j,y_l), принадлежащая множеству E₂ и i = k.

      Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z₁=(x₁y₁), z₂₌(x₁y₂), z₃=(x₁y₃), z₄=(x₂y₁), z₅=(x₂y₂), z₆=(x₂y₃). 

       Определим множество дуг результирующего  графа. Для этого выделим группы вершин множества Z,  компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X, и три группы, имеющие совпадающие компоненты из Y. Рассмотрим группу вершин результирующего графа, которые имеют общую компоненту x₁: z₁=(x₁y₁), z₂₌(x₁y₁), z₃=(x₁y₃). Согласно определению операции декартова произведения графов, множество дуг между этими вершинами определяется связями между вершинами множества Y. Таким образом, дуга (y₁,y₁) в графе G2 определяет наличие дуги (z₁,z₁) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.