Связность графов. Говорят, что две вершины в графе связаны, если существует соединяющая их (простая) цепь

Говорят, что две вершины в графе связаны, если существует соединяющая их (простая) цепь. Граф, в котором все вершины связаны, называется связным.

Отношение связанности вершин является эквивалентностью. Классы эквива­лентности по отношению связанности называются компонентами связности гра­фа. Число компонент связности графа G обозначается k (G). Граф G является связным тогда и только тогда, когда k (G) = 1. Если k (G) > 1, то G — несвязный граф. Граф, состоящий только из изолированных вершин (в котором k (G) = p (G) и r (G) = 0), называется вполне несвязным или пустым.

Виды графов

Тривиальные и полные графы

Граф, состоящий из одной вершины, называется тривиальным. Граф, состоящий из простого цикла с k вершинами, обозначается C_k, например С ₃ – треугольник.

Граф, в котором каждая пара вершин смежна, называется полным. Полный граф с р вершинами обозначается К_р, он имеет максимально возможное число ребер

.

Полный подграф некоторого графа называется кликой этого графа.