Связные графы

Определение 1: Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути не существует, вершины называются не связными.Так, на рисунке любая пара вершин, взятая из набора А,Б,В,Г,Д,будет связной, т.к. от любой из них к любой можно "пройти" по ребрам графа. Пары вершин, одна из которых взята из набора А,Б,В,Г,Д, а другая из набора Е,Ж,З,не будут связными, т.к. от одной к другой "пройти" по ребрам не удается.

Определение 2:

Граф называется связным, если любая пара его вершин — связная.

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

На рисунке, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным.

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

Примерами мостов на рисунке могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.