Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 4 стр.

                                4

Опр. Если W-подмножество вершин графа G, то его смежным множеством
  Adj(W) называют множество всех вершин, не принадлежащих W и смежных
  с какой-либо вершиной из W.
                              Adj(W) ∩ W=∅.
Опр. Путем называется последовательность вершин u1, u2,..., um+1 такая, что
  каждые две вершины ui, ui+1 являются смежными. Число m (число ребер,
  соединяющих вершины u1, um+1) называется длиной пути.
Опр. Говорят, что вершины u, v соединены путем, если существует путь, для
  которого вершины u, v являются концевыми.
Опр. Расстоянием d(u,v) между вершинами u, v называется длина кратчайшего
  пути, соединяющего эти вершины.
Опр. Наибольшее расстояние между любыми двумя вершинами графа
  называется диаметром.
Опр. Наибольшее расстояние от вершины u до любой другой вершины графа
  называется эксцентриситетом вершины u: e(u).
    Таким образом, D ia m G = ma x{e (u i )} (u i ∈ V)
                                    i

Опр. Если эксцентриситет вершины совпадает с диаметром графа, то та-
  кая вершина называется периферийной.
Опр. Вершина u называется псевдопериферийной (ППВ), если для любой вер-
  шины v∈V такой, что d(u,v)=e(u), будет выполнено e(v)=e(u).
Замечание. ППВ легче находить, чем периферийные, так как эффективных
  алгоритмов отыскания периферийных вершин нет.
Опр. Замкнутый путь называется циклом.
Опр. Граф называется связным, если для любых двух вершин этого графа
  существует соединяющий их путь.
Опр. Связный граф, не имеющий циклов, называется деревом.
Опр. Граф G(V′,E′) называется подграфом графа G(V,E), если V′⊆V, E′⊂E.
Опр. Подграф G(V′,E′) называется частичным графом, если V′ состоит из
  некоторых вершин графа G, а E′ включает в себя все ребра графа G, соеди-
  няющие эти вершины: V′⊂ V, E′={(u,v) ∈ E: u∈ V′, v∈ V′}.
    Если граф не является связным (т. е. несвязный граф), то у него есть две
(или более) компоненты связности, каждая из которых является связным
частичным графом.
Опр. Разделителем называется множество вершин, удаление которых
  вместе с инцидентными им ребрами приводит к появлению несвязного графа
  (или к увеличению числа связных компонент, если граф уже был несвязным).
Опр. Если разделитель состоит из одной вершины, то он называется
  разрезающей вершиной. Если ее удалить, то граф распадется на несколько
  связных компонент.
Опр. Кликой называется такой подграф, у которого любые две вершины
   смежные.