(X, U);
2. Відображенням кожної вершини подграфа є перетин відображення тієї ж вершини у графі G (X, U) зі всім підмножиною вершин A подграфа G (A, U A ).
Частковим графом для графа G (X, U) називається граф G (X, U) , в якому містяться всі вершини і деякий підмножина дуг вихідного графа.
Частковий подграф - це частковий граф від подграфа.
Фактором графа G (X, U) називається частковий граф G (X, U) , в якому кожна вершина має полустепені результату і заходу, рівними одиниці, маються одна заходящая і одна виходить дуги.
Базисним графом називається орієнтований частковий граф, утворений з вихідного видаленням петель і замикаючих дуг.
язність графа
У загальному випадку граф може бути представлений декількома окремими графами, що не мають загальних дуг. Тоді граф G (X, U) називається незв'язних, а кожен з складових його графів G 1 , G 2 , ... G n - компонентами зв'язності. Граф називається зв'язковим, коли кожну його вершину можна з'єднати з будь-якої іншої його вершиною деякої ланцюгом.
Операції над графами
1. Об'єднання графів
G 3 (X 3 , Гх 3 ) = G 1 (X 1 , Г1х 1 ) Г€ G 2 ( X 2 , Г2х 2 ) , де X 3 = X 1 Г€ X 2 , а Гx 3 = Г1x 1 Г€ Г2x 2
Приклад (Рис 1.1).
Рис 1.1
2. Перетин графів
G 3 (X 3 , Гх 3 ) = G 1 (X 1 , Г1х 1 ) Г‡ G 2 ( X 2 , Г2х 2 ) , де X 3 = X 1 Г‡ X 2 , а Гx 3 = Г1x 1 Г‡ Г2x 2
Приклад (рис 1.2).
Рис 1.2
4. Пряме (декартово) твір графів.
Прямим твором множин Х {x 1 ....... x n } і Y називається безліч Z, елементами якого є всілякі пари виду x i , y j , де x i ГЋX, y j ГЋY. Позначають: Z = X x Y.
G 3 (X 3 , Гх 3 ) = G 1 (X 1 , Г1х 1 ) Г‡ G 2 ( X 2 , Г2х 2 ) , де X 3 = X1 Г‡ X2, а Гx 3 = Г1х1 Г‡ Г2х2
Приклад. (Рис 2.3)
G 1 (X, Гх) = G 1 (X 1 , Гх 1 ) G 2 (Y, Гy) = G
