A conectividade em grafos nos permite modelar conexões entre vértices de um grafo através das ideias de passeio. A definição de conectividade varia de acordo com o tipo (orientado ou não orientado) do grafo.
Dado um grafo não orientado , dizemos que um vértice está conectado ou ligado a um vértice se e somente se existe um caminho em com início em e término em .
Um grafo não vazio é conexo quando quaisquer dois de seus vértices estão conectados.
Componentes
As componentes de um grafo são os subgrafos conexos de que são maximais na relação “é subgrafo de”, ou seja, são os maiores subgrafos conexos possíveis que compõe . Isso implica que cada componente de um grafo é essencialmente um grafo independente, sem conexão com as outras componentes. Note que, se um grafo é conexo, então ele possui apenas uma componente (o próprio ).
Dessa forma, é possível afirmar que um grafo é conexo se e somente se ele exatamente uma componente conexa, caso contrário ele é dito desconexo. Note que o grafo vazio não é conexo nem desconexo, pois não possui vértices. Um grafo sem arestas é dito totalmente desconexo.
Aresta e vértice de corte
Uma aresta de corte é uma aresta de um grafo que, se removida, gera um grafo que tem uma componente conexa a mais em relação a .
Um vértice de corte é um vértice de um grafo que, se removido, gera um grafo que tem uma componente conexa a mais em relação a .
Conectividade em grafos orientados
Nos grafos orientados a conectividade entre dois vértices deve valer para os dois sentidos.
Um grafo orientado é fortemente conexo se para quaisquer dois vértices existe um passeio orientado de para e de para .
As componentes fortemente conexas de um grafo orientado são os subgrafos fortemente orientados de que são maximais na relação “é subgrafo de”.