Теория графов

Теория графов Набор – неупорядоченная система объектов из некоторого множества, в котором один и тот же объект может встречаться несколько раз  Множество V={a1, a2,…} и набор E из неупорядоченных пар объектов ai , a j из V называется графом G(V,E) a1, a2,… вершины графа ai , a j  a2 a1 ребра графа a3 a4 a6 a5 a7 смежные вершины инцидентное ребро смежные ребра кратные ребра мультиграф  V  a1, a2 , a3 , a4 , a5 , a6 , a7  E  (a1, a2 ), (a2 , a2 ), (a4 , a5 ), (a5 , a6 ), (a5 , a6 ), (a6 , a7 ), (a5 , a7 ) геометрическая реализация графа G(V,E) Теорема 1. Каждый конечный граф G(V,E) можно реализовать в трехмерном евклидовом пространстве. … a3 a2 a5 a6 ориентированный граф (орграф)  a3 a2 a4 a1    ai , a j  E a j , ai  E a5 a6 a7     Aai ,a j  ai1 , ai2 , ai2 , ai3 ,..., ais1 , ais ai1  ai ais  a j путь (маршрут) a4 a1 a7 Aa4 ,a6  a4 , a5 , a5 , a7 , a7 , a6  Цепь, простая цепь, циклический путь, цикл, контур, простой цикл ai , ai  - петля Aa2 ,a2  a2 , a2  Aa5 ,a5  a5 , a6 , a6 , a7 , a7 , a5  Связный граф, псевдограф полный граф Компонента связности Структура смежности Изоморфные графы ai a1 a2 смежные a2 a1 вершины K4 a3 a4 a5 a6 a7 a5 a4 a6 a7 a5 a7 a5 a6 Матрица смежности AG a1 a2 a3 a4 a5 a6 a7 a1  0  a2  1 a3  0 AG  a  4 0 a5  0  a6  0 a7  0 графа G(V,E) a2 1 0 0 0 0 0  1 0 0 0 0 0 0 0 0 0 0 0  a1 2  0 0 0 1 0 0 a2 0 0 1 0 2 1 1  0 0 0 2 0 1 0 0 0 1 1 0  a 1 a3 a5     1, если ai , a j  E , Aij   0, если ai , a j  E. a6 a1 a2 a3 a4 a5 a6 a7 a1  0  a2  1 a4 a7 a3  0 AG  a  4 a3 a a6 4 0 5 a5  0  5 3 6 7 a6  0 a7  0 a4 a7 Матрица инцидентности графа G(V,E) 1 a1   1  1, если ребро e j исходит из вершины ai , a2  1    1, если ребро e j заходит в вершину ai B a3  0 Bij   G a 4 0 и не является петлей,  a5  0 0, если вершина a не инцидентна ребру e . i j   a6  0 a7  0 2 1 3 0 0 0 0 0 0  1 0 0 0 0 0 0 0 0 0 0 0  0 0 0 1 0 0 0 0 0 0 1 1  0 0 0 1 0 0 0 0 0 0 1 0  4 5 6 7 0  0 0 0 0 0 0 0 0 0 0  1 0 0 0 0 1 1 1 1 0  0 1  1 0  1 0 0 0  1 1  deg a1  1 - концевая, висячая Степень вершины графа G(V,E) deg a deg a2  3 a2 a3 a6 a5 deg a3  0 - изолированная вершина deg a4  1 - концевая, висячая deg a5  4  deg a  2m a1 a4 - лемма о рукопожатиях aV (G ) a7 deg  a - полустепень захода a2 deg  a - полустепень исхода deg a  deg  a  deg  a deg a7  2 deg a6  3 a1 a3 a6 a5 a4 a7  (G) - минимальная степень вершин графа  (G)  0 (G) - максимальная степень вершин графа V  n - порядок графа G(V,E) G(n,m) (G)  4 deg ai  di d j1  d j2  ...  d jn   d  d j1 , d j2 ,...,d jn вектор степеней d  (0,1,1,2,3,3,4) d1  d2  ...  dn  d регулярный граф степени d  (a, b) - расстояние между вершинами a и b  (a, b)  0  a  b  (a, b)  0 матрица расстояний P  (a, b)   (b, a)  (a, b)   (a, c)   (c, b) 1 2 3 4 5 6 2 1 3 6 1 0 1 2 3 2 1 e(1)  3 2 1 0 1 2 2 1 e(2)  2 P3 2 1 0 1 2 1 4 3 2 1 0 1 2 e(3)  2 5 2 2 2 1 0 1 6 1 1 1 2 1 0 5 pi, j   (ai , a j ) e(4)  3 e(5)  2 e(6)  2 4 e(a)  max (a, b), b V  - эксцентриситет вершины a. diam(G)  maxe(a), a  V  - диаметр графа diam(G)  3 r (G)  min e(a), a V  r (G)  2 e(a)  diam(G) e(a)  r (G) - радиус графа - периферийная вершина - центральная вершина {1,4} центр графа {2,3,5,6}