Связность графа

Граф G называется связным, если для любых двух его вершин существует путь, их соединяющий. В противном случае граф G называется несвязным. На рис. 3.8 представлен несвязный граф

Несвязный граф

Любой несвязный граф является совокупностью таких связных графов, которые облада­ют следующим свойством: никакая вершина одного из них не связана путем ни с какой верши­ной другого. Каждый из этих графов называется компонентой графа G. В данном примере граф состоит из двух связных компонентов.

Ребро а называется мостом графа G, если граф, получив­шийся из G после удаления ребра а (такой граф обозна­чается G\ а), содержит больше компонент, чем граф G. Ребро а графа G является мостом тогда и только тогда, когда а не принадлежит ни одному циклу.

Плотность графа характеризуется коэффициентом плотности А — отношением числа ребер (L) в анализируемом графе к числу ребер в полном графе с тем же числом вершин (g):

Коэффициент плотности варьируется в промежутке от 0 до 1, 0 ≤ Δ ≤ 1. Единичная плотность соответствует полному графу, нулевая — графу, в котором все вершины изолированные.

Частным случаем графов являются деревья. Они характеризуются тем, что содержат минималь­ное число ребер, необходимое для связности.

При этом

• любое ребро дерева представляет собой мост,

• l = g-1;

• существует только один путь между любыми двумя вершинами.

 

Ориентированные графы: основные понятия

Если рассматривается множество упорядоченных пар 1_к = (n_i, п_j) из множества точек N={n₁., п_g }, и на каждом ребре из множества Z= { l₁,...,l_z } задается направление, то граф G_d = (N,Z) называется ориентированным.. Если же на каждом ребре из множества Z= { l₁,...,l_z } направле­ние не задается, то граф G = (N, Z) называется неориентированным графом, или просто графом.

Примеры ориентированного графа

 

В ориентированном графе для каждой вершины различаются входящие и исходящие ребра. По­этому для характеристики отношений, связанных с конкретной вершиной, используют два по­казателя:

• степень захода d_m, которая равна числу ребер, входящих в вершину; и

• степень исхода d_oul, которая равна числу ребер, исходящих из вершины.

Плотность ориентированного графа характеризуется коэффициентом плотности Δ: