Определите, какие из следующих утверждений верны: (1) Число связности графа меньше числа его вершин. (2) Если после удаления ребра число связности графа не изменилось, то удаленное ребро входило в цикл. (3) Если на множестве вершин произвольного графа

Ниже приведён пошаговый разбор каждого из утверждений.

──────────────────────────────

1. Утверждение (1): «Число связности графа меньше числа его вершин.»

• Определение: Число связности графа (κ(G)) – это минимальное количество вершин, удаление которых приводит к разбиению графа на несвязные части (или делает его несвязным).
• Замечание: Из известных теорем следует, что для любого связного графа с n вершинами справедливо неравенство κ(G) ≤ n – 1. При этом если норма ведётся для тривиальных случаев, то даже если граф состоит из одной вершины (при которой принято считать κ(G) = 0), то 0 1. ...