Реферат: Поиск клик в графах

Фактором графа G(X,U) называется частичный граф G(X,U) , в котором каждая вершина обладает полустепенями исхода и захода, равными единице, имеются одна заходящая и одна исходящая дуги.

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

Связность графа

В общем случае граф может быть представлен несколькими отдельными графами, не имеющими общих дуг. Тогда граф G(X,U) называется несвязным, а каждый из составляющих его графов G₁ , G₂ ,...G_n - компонентами связности. Граф называется связным, когда каждую его вершину можно соединить с любой другой его вершиной некоторой цепью.

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

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

G₃ (X₃ ,Гх₃ ) = G₁ (X₁ ,Г1х₁ ) È G₂ (X₂ ,Г2х₂ ) , где X₃ =X₁ È X₂ , а Гx₃ =Г1x₁ È Г2x₂

Пример (Рис 1.1).

Рис 1.1

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

G₃ (X₃ ,Гх₃ ) = G₁ (X₁ ,Г1х₁ ) ÇG₂ (X₂ ,Г2х₂ ) , где X₃ =X₁ Ç X₂ , а Гx ₃ =Г1x₁ Ç Г2x₂

Пример (рис 1.2).

Рис 1.2

4. Прямое (декартово) произведение графов.

Прямым произведением множеств Х{x₁ .......x_n } и Y называется множество Z, элементами которого являются всевозможные пары вида x_i , y_j , где x_i ÎX, y_j ÎY. Обозначают: Z=X x Y.

G₃ (X₃ ,Гх₃ ) = G₁ (X₁ ,Г1х₁ ) ÇG₂ (X₂ ,Г2х₂ ) , где X₃ =X1 Ç X2, а Гx₃ =Г1х1 Ç Г2х2

Пример. (рис 2.3)

G₁ (X,Гх)=G₁ (X₁ ,Гх₁ ) G₂ (Y,Гy)= G₂ (X₂ ,Гх₂ )

X={x₁ x₂ x₃ } Y={y₁ y₂ }

Гх₁ =0 Гу₁ ={y₁ y₁ }

Гх₂ ={x₁ x₃ } Гу₂ ={y₁ }

Гх₃ =0

Z=X x Y={x ₁ y₁ , x₁ y₂ , x₂ y₁ , x₂ y₂ , x₃ y₁ , x₃ y₂ }

Z={z₁ z₂ z₃ z₄ z₅ z₆ }

Рис 2.3

7. Расширение графа.

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

8. Сжатие графа.

Сжатие графа - это превращение элементарного пути, соединяющего две любые вершины графа, в линию.

9. Стягивание графа.