Связность

В связном графе любые две вершины соединены (простой) цепью.

Компоненты связности –

связные части графа.

Несвязный граф, имеет две компоненты связности.

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

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

Максимальные неразделимые подграфы графа называются его блоками.

Пример.

Вершины u, v – точки сочленения, и других точек сочленения нет.

Ребро х – мост, и других мостов нет.

Подграфы {a, b, u, w}, {c, d, v}, {e, f, v} – блоки, и других блоков нет.

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

Пусть G(V, E) – орграф, v₁ и v₂ – его вершины. Говорят, что две вершины v₁ и v₂ связаны в орграфе G, если они связаны в графе G’, полученном из G отменой ориентации ребер. Если все вершины в орграфе связаны, то орграф называется связным. Орграф называется односторонне связным, если для любой пары вершин существует путь между ними хотя бы в одну сторону. Говорят, что две вершины v₁ и v₂ сильно связаны в орграфе G, если существует путь (ориентированная цепь) из v₁ в v₂ и из v₂ в v₁. Если все вершины в орграфе сильно связаны, то орграф называется сильно связным.

Пример.

Сильная (слева) связность и связность.

Компоненты сильной связностиорграфа – его сильно связные подграфы.

Три сильно связные компоненты орграфа, который сам не является сильно связным.

Конденсация орграфа – орграф, которые получается стягиванием каждой компоненты сильной связности в точку.

Конденсация графа, изображенного выше.

Планарность

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

Граф планарен тогда и только тогда, когда он не содержит в качестве подграфов ни К₅, ни К_{3, 3}.