Матрица смежности и матрица инцидентности графа. Эксцентриситеты вершин; радиусы графов; диаметры графов; периферийные и центральные вершины; диаметральные цепи графов.

Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инцидентности.

Представление графа с помощью квадратной булевой матрицы, отражающей смежность вершин, называется матрицей смежности, где

Матрица смежности - квадратная матрица порядка n, где n- число вершин.

Хотя формально каждая вершина всегда смежна сама с собой, в матрице смежностей ставят m_kk= 0, если у неё нет петли, и m_kk= 1, если есть одна петля. Если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят нули. Матрица смежности неориентированного графа является симметричной относительно главной диагонали.

Матрица инцидентности отражает инцидентность вершин и рёбер.

Это таблица состоящая из n строк (вершины) и m столбцов (рёбра), в которой:

b_ij=1, если вершина V_i инцидентна ребру X_j

b_ij=0, если вершина V_i не инцидентна ребру X_j

Расстоянием между двумя вершинами называется минимальная длина из всех возможных путей между этими вершинами при условии, что существует хотя бы один такой путь

В таблице расстояний фиксируется расстояние между вершинами графа.

Эксцентриситетом вершины v в связном графе G(V,E) называется максимальное расстояние от вершины v до других вершин графа G.

Радиусом графа G называется наименьший из эксцентриситетов вершин.

Вершина v называется центральной, если ее эксцентриситет совпадает с радиусом графа.

Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути не существует, вершины называются несвязными.

Граф называется связным, если любая пара его вершин - связная. Граф называется несвязным, если в нём есть хотя бы одна несвязная пара вершин.

Граф G можно разбить на непересекающиеся множества V_i по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств – несвязны. Тогда все подграфы V_i (классы эквивалентности) графа G называют связными компонентами, или компонентами связности. Связный граф имеет одну компоненту связности.

Цикломатическим числом графа G называется число

ν(G) = m(G)+c(G)- n(G),

где m(G) – число его ребер; c(G) – число связных компонент графа; n(G) – число вершин графа.