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

Примеры.

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

Утверждение. , где - минимальная из степеней вершин графа G.

1. .

Если =0, то граф G – несвязен, поэтому =0. Пусть >0. отметим те ребер, которые нужно удалить, чтобы граф G разделился на несколько компонент связности. На каждом из этих ребер отметим произвольно по одной вершине. Всего будут отмечены не более вершин.

Удалим отмеченные вершины. Вместе с ними будут удалены все отмеченных ребер, так что граф G распадется. Возможно, что для разделения графа на несколько компонент связности требуется удалить ещё меньше вершин. Значит, .

2. .

Если в графе G есть изолированная вершина, он несвязен, =0. Если >0, то, после удаления ребер, инцидентных вершине наименьшей степени, она станет изолированной, превратится в отдельную компоненту связности. Возможно, что для разделения графа G на две компоненты связности, требуется удалить ещё меньше ребер, поэтому .

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