gráfico conectado por k -edge - k-edge-connected graph
Em teoria gráfico , um ligado gráfico é k -Edge-ligada se ele permanece ligado sempre menos do que k bordas são removidos.
A conectividade de aresta de um gráfico é o maior k para o qual o gráfico é conectado por ke .
A conectividade de borda e a enumeração de gráficos conectados por k -edge foi estudada por Camille Jordan em 1869.
Definição formal
Deixe ser um gráfico arbitrário. Se o subgrafo estiver conectado para todos onde , então G é conectado por k -edge. A conectividade de borda de é o valor máximo k tal que G é conectado por k -edge. O menor conjunto X , cuja remoção desliga L é um corte mínimo em L .
A versão de conectividade de arestas do teorema de Menger fornece uma caracterização alternativa e equivalente, em termos de caminhos disjuntos de arestas no grafo. Se e somente se cada dois vértices de G formarem os pontos finais de k caminhos, nenhum dos quais compartilhe uma aresta um com o outro, então G é conectado por k - aresta . Em uma direção, isso é fácil: se um sistema de caminhos como este existe, então cada conjunto X com menos de k arestas é separado de pelo menos um dos caminhos, e o par de vértices permanece conectado um ao outro mesmo após X ser excluído . Na outra direção, a existência de um sistema de caminhos para cada par de vértices em um grafo que não pode ser desconectado pela remoção de algumas arestas pode ser provada usando o teorema de corte mínimo de fluxo máximo da teoria de fluxos de rede .
Conceitos relacionados
O grau de vértice mínimo fornece um limite superior trivial na conectividade de borda. Isto é, se um gráfico é k -Edge-ligado, em seguida, é necessário que k ≤ δ ( G ), onde δ ( G ) é o grau mínimo de qualquer vértice v ∈ V . Obviamente, deletar todas as arestas incidentes em um vértice, v , desconectaria v do gráfico.
Conectividade de borda é o conceito duplo de circunferência , a duração do ciclo mais curto em um gráfico, no sentido de que a circunferência de um grafo planar é a conectividade de borda de seu grafo dual e vice-versa. Esses conceitos são unificados na teoria da matróide pela circunferência de uma matróide , o tamanho do menor conjunto dependente da matróide. Para uma matróide gráfica , a circunferência da matróide é igual à circunferência do gráfico subjacente, enquanto para uma matróide co-gráfica é igual à conectividade da borda.
Os gráficos de 2 arestas também podem ser caracterizados pela ausência de pontes , pela existência de uma decomposição em orelha ou pelo teorema de Robbins segundo o qual esses são exatamente os gráficos que têm uma orientação forte .
Aspectos computacionais
Existe um algoritmo de tempo polinomial para determinar o maior k para o qual um grafo G é conectado por k -edge. Um algoritmo simples iria, para cada par (u, v) , determinar o fluxo máximo de u para v com a capacidade de todas as arestas em G definida como 1 para ambas as direções. Um gráfico é conectado por k -edge se e somente se o fluxo máximo de u para v for pelo menos k para qualquer par (u, v) , então k é o menor fluxo de uv entre todos (u, v) .
Se n for o número de vértices do gráfico, este algoritmo simples faria iterações do problema de fluxo máximo, que pode ser resolvido a tempo. Portanto, a complexidade do algoritmo simples descrito acima é total.
Um algoritmo melhorado resolverá o problema de fluxo máximo para cada par (u, v) onde u é arbitrariamente fixo enquanto v varia em todos os vértices. Isso reduz a complexidade e é válido, pois, se houver um corte de capacidade menor que k , ele separará u de algum outro vértice. Ele pode ser ainda melhorado por um algoritmo de Gabow que é executado no pior dos casos .
A variante Karger-Stein do algoritmo de Karger fornece um algoritmo aleatório mais rápido para determinar a conectividade, com tempo de execução esperado .
Um problema relacionado: encontrar o subgráfico de extensão mínimo conectado por k -aresta de G (isto é: selecione o mínimo possível de arestas em G para o qual sua seleção está conectada por k -aresta) é NP-difícil .
