ся петлею.
Орієнтований граф - граф, у якого вершини з'єднуються напрямними стрілками.
Графи можна розглядати з урахуванням або без урахування орієнтації його дуг.
Різновиди графів
В
Нуль-граф - граф (X, U) , складається тільки з ізольованих вершин.
Однорідний граф - якщо ступеня всіх вершин графа однакові і P + (x) = P - (x) = 0. p> симетричних граф - граф, в якому дві будь суміжні вершини з'єднані тільки двома протилежно орієнтованими дугами.
Антісімметріческій - граф, в якому кожна пара суміжних вершин з'єднана тільки в одному напрямку.
Повний - граф, в якому будь-яка пара вершин з'єднана однаковим числом дуг.
мультіграф - граф, в якому хоча б дві суміжні вершини з'єднані більш ніж однією дугою. Найбільше число дуг, що з'єднують суміжні вершини графа називається кратністю.
Підмножини графів <В
Подграфом графа G (X, U) називається граф G (A, U A ) , який визначається наступним чином:
1. Вершинами A подграфа G (A, U A ) є деяка підмножина вершин графа G (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. Перетин гра...
