Bridge (teoria dos gráficos) - Bridge (graph theory)

Um gráfico com 16 vértices e 6 pontes (destacadas em vermelho)

Um gráfico conectado não direcionado sem bordas de ponte

Na teoria dos grafos , uma ponte , istmo , aresta de corte ou arco de corte é uma aresta de um gráfico cuja exclusão aumenta o número de componentes conectados do gráfico . Equivalentemente, uma aresta é uma ponte se e somente se não estiver contida em nenhum ciclo . Para um gráfico conectado, uma ponte pode determinar exclusivamente um corte . Um gráfico é considerado sem ponte ou sem istmo se não contiver pontes.

Este tipo de ponte deve ser distinguido de um significado não relacionado de "ponte" na teoria dos grafos, um subgrafo separado do resto do gráfico por um subconjunto especificado de vértices; consulte o Glossário de termos da teoria dos grafos § ponte .

Árvores e florestas

Um gráfico com nós pode conter no máximo pontes, já que adicionar arestas adicionais deve criar um ciclo. Os gráficos com exatamente pontes são exatamente as árvores , e os gráficos em que cada aresta é uma ponte são exatamente as florestas . ${\ displaystyle n}$ ${\ displaystyle n-1}$ ${\ displaystyle n-1}$

Em todo grafo não direcionado, existe uma relação de equivalência nos vértices de acordo com a qual dois vértices estão relacionados entre si sempre que houver dois caminhos disjuntos de aresta conectando-os. (Cada vértice está relacionado a si mesmo por meio de dois caminhos de comprimento zero, que são idênticos, mas, no entanto, arestas disjuntas.) As classes de equivalência desta relação são chamadas de componentes conectados por 2 arestas , e as pontes do gráfico são exatamente as arestas cujas endpoints pertencem a diferentes componentes. A árvore de blocos de pontes do gráfico tem um vértice para cada componente não trivial e uma aresta para cada ponte.

Relação com conectividade de vértice

As pontes estão intimamente relacionadas com o conceito de vértices de articulação , vértices que pertencem a todo caminho entre algum par de outros vértices. Os dois pontos finais de uma ponte são vértices de articulação, a menos que tenham grau 1, embora também seja possível para uma borda sem ponte ter dois vértices de articulação como pontos finais. De forma análoga aos gráficos sem ponte sendo conectados por 2 arestas, gráficos sem vértices de articulação são conectados por 2 vértices .

Em um gráfico cúbico , cada vértice de corte é um ponto final de pelo menos uma ponte.

Gráficos sem ponte

Um gráfico sem ponte é um gráfico que não possui nenhuma ponte. As condições equivalentes são que cada componente conectado do gráfico tenha uma decomposição em orelha aberta , que cada componente conectado seja conectado por 2 arestas ou (pelo teorema de Robbins ) que cada componente conectado tenha uma orientação forte .

Um importante problema aberto envolvendo pontes é a conjectura de dupla cobertura do ciclo , de Seymour e Szekeres (1978 e 1979, independentemente), que afirma que todo grafo sem ponte admite um multi-conjunto de ciclos simples que contém cada aresta exatamente duas vezes.

Algoritmo de descoberta de ponte de Tarjan

O primeiro algoritmo de tempo linear para encontrar as pontes em um gráfico foi descrito por Robert Tarjan em 1974. Ele executa as seguintes etapas:

Encontre uma floresta extensa de ${\ displaystyle G}$
Crie uma floresta enraizada a partir da floresta abrangente ${\ displaystyle F}$
Atravesse a floresta na pré - ordem e numere os nós. Os nós pais na floresta agora têm números menores do que os nós filhos. ${\ displaystyle F}$
Para cada nó na pré-encomenda (denotando cada nó usando seu número de pré-pedido), faça: ${\ displaystyle v}$ $v$
- Calcule o número de descendentes da floresta para este nó, adicionando um à soma dos descendentes de seus filhos. ${\ displaystyle ND (v)}$
- Compute , o rótulo de pré-pedido mais baixo acessível por um caminho para o qual todos, exceto a última aresta, permanecem dentro da subárvore enraizada . Este é o mínimo do conjunto que consiste no rótulo de pré-encomenda de , nos valores de nos nós filhos de e nos rótulos de pré-encomenda de nós alcançáveis por arestas que não pertencem a . ${\ displaystyle L (v)}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle L (w)}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle F}$
- Da mesma forma, calcule o maior rótulo de pré-encomenda acessível por um caminho para o qual todas, exceto a última aresta, permanecem dentro da subárvore enraizada . Este é o máximo do conjunto que consiste na etiqueta de pré-encomenda de , nos valores de em nós filhos de e nas etiquetas de pré-ordem de nós alcançáveis por arestas que não pertencem a . ${\ displaystyle H (v)}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle H (w)}$ ${\ displaystyle v}$ ${\ displaystyle v}$ ${\ displaystyle F}$
- Para cada nó com nó pai , se e então a aresta de para é uma ponte. ${\ displaystyle w}$ ${\ displaystyle v}$ ${\ displaystyle L (w) = w}$ ${\ displaystyle H (w) <w + ND (w)}$ ${\ displaystyle v}$ ${\ displaystyle w}$

Localização de pontes com decomposições em cadeia

Um algoritmo de localização de pontes muito simples usa decomposições em cadeia . As decomposições em cadeia não só permitem calcular todas as pontes de um gráfico, mas também permitem ler cada vértice de corte de G (e a árvore de corte de bloco de G ), fornecendo uma estrutura geral para testar 2 arestas e 2 vértices -conectividade (que se estende a testes de conectividade de 3 arestas e 3 vértices em tempo linear).

Decomposições em cadeia são decomposições especiais em orelha dependendo de uma árvore DFS T de G e podem ser calculadas de forma muito simples: Deixe cada vértice ser marcado como não visitado. Para cada vértice v em números DFS ascendentes 1 ... n , atravesse cada borda posterior (ou seja, cada borda que não esteja na árvore DFS) que incide av e siga o caminho das bordas da árvore de volta à raiz de T , parando em o primeiro vértice marcado como visitado. Durante essa travessia, cada vértice percorrido é marcado como visitado. Assim, uma travessia para no máximo em v e forma um caminho ou ciclo direcionado, começando com v; chamamos esse caminho ou ciclo de cadeia . A i ésima cadeia encontrada por este procedimento é conhecida como C _i . C = C ₁ , C ₂ , ... é, em seguida, uma decomposição da cadeia de L .

Os seguintes caracterizações, em seguida, permitir que a ler fora várias propriedades de L a partir de C de forma eficiente, incluindo todas as pontes de L . Seja C uma decomposição em cadeia de um grafo simples conectado G = (V, E) .

L é 2-aresta-ligada se e somente se as cadeias em C partição E .
Uma aresta de e em L é uma ponte, se e somente se e não está contido em qualquer cadeia em C .
Se G for conectado por 2 arestas, C é uma decomposição em orelha .
L é 2-vértice-conectado se e somente se L tem um grau mínimo de 2 e C ₁ é o único ciclo de C .
Um vértice v em um grafo conectado por 2 arestas G é um vértice de corte se e somente se v for o primeiro vértice de um ciclo em C - C ₁ .
Se G é conectado por 2 vértices, C é uma decomposição em orelha aberta .

Bridgehead

Cabeças de ponte de uma ponte que separa as regiões A e B na teoria dos grafos

Para um gráfico conectado , uma ponte pode se separar em região e região , ou seja, o corte . Os vértices e são as duas cabeças de ponte de e . é a ponta de ponte próxima de e a ponta de ponte distante de e vice-versa para . ${\ displaystyle G}$ ${\ displaystyle e}$ ${\ displaystyle G}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle (A, B)}$ ${\ displaystyle \ alpha \ in e \ cap A}$ ${\ displaystyle \ beta \ in e \ cap B}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle \ alpha}$ ${\ displaystyle A}$ ${\ displaystyle B}$ ${\ displaystyle \ beta}$

Languages

In other projects