3. Основные операции над графами, неравенства для числа вершин, ребер и компонент связности графа.

Графом Gназывается пара (V,E), где– непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Утверждение. Если в графе количество вершинn≥ 2, то в нем найдутся хотя бы две вершины с одинаковой степенью.

Утверждение. Для любого графаG= (V,E) сnвершинами иmребрами справедливо равенство т.е. сумма степеней всех вершин графа равна удвоенному количеству ребер.

К графам или отдельным его элементам могут применяться следующие операции:

• добавление ребра, соединяющего две несмежные вершины;

• удаление ребра (концы ребра сохраняются);

• добавление вершины;

• удаление вершины (вместе с инцидентными ей ребрами);

• отождествление двух несмежных вершин (все ребра, инцидентные отождествляемым вершинам, сохраняются и становятся инцидентными полученной вершине; если при этом возникают кратные ребра, они заменяются одним ребром);

• подразбиение ребра [u,v] (сначала добавляются новая вершина w и новые ребра [u,w], [w,v], затем удаляется ребро [u,v]);

• стягивание ребра [u,v] (сначала удаляется ребро [u,v], а затем вершины u и v отождествляются);

• объединение графов и(в результате получается графU, вершинами и ребрами которого являются вершины и ребра графови).

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

Определение. Говорят, что граф состоит изkкомпонент связности, если его можно представить как объединениеkсвязных графов, не имеющих общих вершин.

Определение. Мостом в графе называется ребро, при удалении которого увеличивается количество компонент связности этого графа.

Утверждение 1. Количество реберmв любом связномn-вершинном графе удовлетворяет неравенствам.

Утверждение 2. Еслиn-вершинный граф состоит изkкомпонент связности, то количество его реберmудовлетворяет неравенствам.