Примеры. Меры связности графа. Вершинная и реберная связность

Меры связности графа. Вершинная и реберная связность

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

=0, если граф G несвязен; =1, если граф G имеет точку сочленения;

, если (G – полный граф с p вершинами).

Определение. Если , то граф G называют k -связным.

На рис. 3 приведен пример 2-связного графа.

Рис. 3

Определение. Реберной связностью графа G называется наименьшее число ребер, удаление которых приводит к несвязному графу.

Дата добавления: 2014-01-05