Реферат: Операции на графах

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

Пусть 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’₂ теорему 2, найдем матрицу смежности вершин графа G’₁ Ç G’₂ как A’₁ Ç A’₂ . Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X₁ Ç X₂ , а множество ребер определяется, как E₁ Ç E₂ , что соответствует операции пересечения графов.

Пример 2. Выполнить в матричной форме операцию пересечения графов G₁ и G₂ , представленных на рис. 2.

Составим матрицы смежности вершин исходных графов.