Операции над графами

Естественно стремиться представить структуру рассматриваемого графа с помощью графов меньшего размера и более простой структуры. Полезно дать краткие обозначения для тех графов, которые при этом часто встречаются. Уже были введены обозначения для полного графа Кр и его дополнения Кр', простого цикла Сnи простой цепи Pn, а также полного двудольного графа Km,n.

В этом разделе графы G1 и G2 имеют непересекающиеся множества вершин V1 и V2 и непересекающиеся множества ребер X1 и Х2.

ОбъединениемG1G2 таких графов называется граф множеством вершин, которого является V=V1V2 , а множество ребер есть X = X1X2

Соединениеграфов, введенное Зыковым — обозначается G1+G2,состоит из G1G2 и всех ребер, соединяющих V1 и V2. В частности, Кm,n = Km+Кn- Эти операции иллюстрируются на рисунке , где G1 = K2=P2 и G2=K1,2=P3

Если G — связный граф, то через nG обозначается граф сnкомпонентами, каждая из которых изоморфна G. Каждый граф можно записать в виде UniGi, где Gi отличается отGj, для i! =j . Например, несвязный граф, представленный на рисунке можно записать в виде 4К1ЗК22K3К1,2

Имеется несколько операций над графами G1 и G2, которые образуют граф G с множеством вершин, равным декартову произведению Vl X V2. Среди нихпроизведение(или декартово произведение),композиция (илилексикографическое произведение).

Чтобы определить произведение G1xG2 рассмотрим любые две вершины u=(u1, u2) и v = (v1,v2) из V = V1 X V2. Вершиныuи v смежны в G1XG2 тогда и только тогда, когда [u1=v1 и u2adj v2] или [u2=v2 и u1adj u1]. Произведение графов G1=P2 и G2=P3 показано на рисунке

КомпозицияG= G1[G2] также имеет V= Vi x V2 в качестве множества вершин и вершинаu=(u1,u2) смежна сv=(v1,v2) тогда и только тогда, когда [u1asj v1] или [u1=v1 и u2adj v2]. Для графовG1 и G2, представленных на рисунке, две композиции G1 [G2] и G2[G1], которые, очевидно, не изоморфны, показаны на рисунке

Если G1 и G2 — это (p1,q1) - и (p2,q2)-графы соответственно, то для каждой из определенных выше операций можно найти число вершин и число ребер в получающемся графе (см. таблицу 2.2).

число вершин число ребер

Объединение p1+p2 q1 + q2

Соединение p1+p2 q1+q2+p1p2

Произведение p1p2 p1q2+p2q1

Композиция p1p2 p1q2+p2p2q1

Полный n-дольный граф K(p1, p2, ...,pn)определяется как последовательное соединение Kp1+Kp2+...+KPn - Ясно, что в этом графеpi ; вершин иpipj ребер.

Важный класс графов, называемых кубами, наиболее естественно описывается с помощью произведений. Рекурсивно определяется п-мерный кубQn: Q1=K2 и Qn=K2xQn-1. Таким образом,Qn имеет 2ⁿвершин, которые можно представлять наборами а1...аn, гдеan равно 0 или 1. Две вершины (или точки) кубаQn смежны, если их двоичные представления отличаются только в одной позиции (в одном разряде).Q2 иQ3 показаны на рисунке.

Если графы G и H таковы, что отождествление любой вершины графа G с произвольной вершиной графа Н приводит к одному и тому же графу (с точностью до изоморфизма), то граф, получаемый с помощью описанного отождествления вершин, обозначим через GН.

Блоки

Некоторые связные графы можно сделать несвязными, удалив одну вершину, которая называется точкой сочленения. Выделение таких вершин сильно помогает в изучении структуры связного графа. Ребра с аналогичным свойством называются мостами. Части рассматриваемого графа вместе с его точками сочленения - это его блоки. После определения этих трех понятий будут введены и изучены два новых графа, связанных с данным графом - граф его блоков и граф его точек сочленения.