Conexos
Dado um grafo G
dizemos que dois vértices v1, v2
estão conectados em G se existir
uma cadeia em G com extremidade
inicial v1
e extremidade final v2 .
Por convenção todo o vértice está conectado
consigo mesmo.
Um grafo G diz-se um conexo
se todo o par de vértices estiver
conectado em G.
A relação estar conectado a é uma relação
de equivalência. Significa isto que
- todo o vértice está conectado a si mesmo.
(reflexividade)
- Se um vértice está conectado a um segundo vértice (através de
uma cadeia m) então também
o segundo está conectado ao primeiro
(através da cadeia
inversa
m-1).
(simetria)
- Se um vértice está conectado a um segundo
(através de uma cadeia m), que por sua vez
está conectado a um terceiro vértice
(através de outra cadeia q), então o
o primeiro está conectado ao terceiro
(através da cadeia
justaposta m*q).
(transitividade)
Proposição
Se dois vértices v1, v2
estão conectados em G então existe uma cadeia elementar em G
com extremidades v1 e v2 .
Prova
A componente conexa de um vértice é, por definição,
o subgrafo gerado
pelo conjunto de todos os outros vértices
(incluindo o próprio) que lhe estão conectados.
Porque a relação "estar conectado a" é uma relação de
equivalência os conjuntos de vértices das
componentes conexas são
disjuntos dois a dois e todo o grafo G
fica decomposto nas suas componentes conexas.
Um grafo é conexo se e sómente se tiver uma única
componente conexa.