Операции на графах

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра информатики

РЕФЕРАТ

На тему:

«Операции на графах»

МИНСК, 2008

Операции на графах позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).

Объединение графов .

Пусть G₁ (X₁ ,E₁ ) и G₂ (X₂ ,E₂ ) – произвольные графы. Объединением G₁ È G₂ графов G₁ и G₂ называется граф с множеством вершин X₁ È X₂ , и с множеством ребер (дуг) E₁ È E_{2 .}

Рассмотрим операцию на примере графов G₁ (X₁ ,E₁ ) и G₂ (X₂ ,E₂ ) , приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X₁ = {x₁ , x₂ , x₃ } и X₂ = {x₂ , x₃ , x₄ } , а множество вершин результирующего графа определится как X = X₁ È X₂ = {x₁ , x₂ , x₃ , x₄ } . Аналогично определяем множества дуг графа:

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

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

Результирующий граф G(X,E) = G₁ (X₁ ,E₁ ) ÈG₂ (X₂ ,E₂ ) также приведен на рис. 1.

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

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

G₁ È (G₂ È G₃ ) = (G₁ È G₂ ) È G₃ – свойство ассоциативности.

Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема.

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

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

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

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать