| Так, на рисунке любая пара вершин, взятая из набора А,Б,В,Г,Д,будет связной, т.к. от любой из них к любой можно "пройти" по ребрам графа. Пары вершин, одна из которых взята из набора А,Б,В,Г,Д, а другая из набора Е,Ж,З,не будут связными, т.к. от одной к другой "пройти" по ребрам не удается.
| 
|
Определение 2:
Граф называется связным, если любая пара его вершин — связная.
Граф называется несвязным, если в нем есть хотя бы одна несвязная пара вершин.
На рисунке, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным.
Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.
| Примерами мостов на рисунке могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.
| 
|
2014-02-02
928
