Determinando a conectividade de um gráfico.

Question

Recentemente me deparei com o Teorema / Algoritmo de Havel-Hakimi que nos diz se um gráfico simples com uma determinada sequência de graus pode existir. No entanto, isso não nos diz se o gráfico está conectado ou não.

Existe algum procedimento que pode nos dizer sobre o critério acima que não requer o desenho do gráfico em si, ou seja, usando sua seqüência de graus?

Answer 1

Para uma determinada sequência $d_1, d_2, \dots, d_n$ para ser a sequência de graus de um gráfico conectado, precisamos de três coisas:

1. É gráfico: isto é, é a sequência de graus de algum gráfico (simples). Isso pode ser verificado com o algoritmo Havel-Hakimi.
2. $d_1 + d_2 + \dots + d_n \ge 2(n-1)$; isso nos diz que há pelo menos$n-1$ bordas, o mínimo necessário para o gráfico ser conectado.
3. $\min\{d_1, d_2, \dots, d_n\} \ge 1$; isso nos diz que não há vértices isolados.

Essas três condições também são claramente necessárias e acabam sendo suficientes.

Para provar isso, começamos com qualquer gráfico que tenha essa sequência de graus. Se não estiver conectado, reduziremos o número de componentes conectados até que esteja.

Se um gráfico com pelo menos $n-1$bordas não tem ciclos, então ele deve ser conectado (e uma árvore). Então, se nosso gráfico não estiver conectado, ele tem um ciclo. Deixei$vw$ser qualquer ponta do ciclo; deixei$xy$ser qualquer aresta que não esteja no mesmo componente do ciclo. (Os outros componentes não podem ser vértices isolados, pela condição 3, então eles devem conter pelo menos uma aresta.)

Excluir bordas $vw$ e $xy$, e substituí-los por bordas $vx$ e $wy$. (Essas arestas não estavam lá antes, porque seus pontos finais estavam em diferentes componentes conectados.) Esta operação não muda nenhum grau; no entanto, reduz o número de componentes conectados em$1$. Antes,$v,w$ estavam em um componente conectado e $x,y$estavam em outro. Agora,$v$ e $w$ ainda estão conectados (desde $vw$ parte de um ciclo); $x$ e $y$ fazem parte desse componente agora, e então tudo estava conectado a $x$ ou para $y$.

Se continuarmos fazendo isso, eventualmente, acabaremos com um gráfico conectado.