Grau mínimo do "gráfico em árvore"

Dado um gráfico , defina o gráfico de árvore como um gráfico cujos vértices são as árvores abrangentes de , e há uma aresta entre duas árvores, se uma pode ser obtida uma da outra, substituindo uma única aresta. Isto é, há uma aresta , se existem duas bordas de tal modo que . $G$ $T(G)$ $G$ $(T_1, T_2)$ $x, y \in G$ $T_1 - x = T_2 - y$

Minha pergunta é a seguinte: existem limites inferiores ou superiores não triviais no grau do vértice com grau mínimo em ? $T(G)$

Nota: editei a pergunta (última linha) um pouco para torná-la menos ambígua.

graph-theory tree corwin
fonte

Sua definição de vantagem não faz sentido. Você quer dizer "existe uma aresta entre

se existe duas bordas

tal que

T_{1}

$T_1$

T_{2}

$T_2$

x, y \in G

$x, y \in G$

T_{1} - x + y = T_{2}

$T_1 - x + y = T_2$

Tyson Williams

Sim, desculpe, eu quis dizer arestas.

Corwin 25/09/11

é uma árvore, seu gráfico de árvore

é um único vértice com grau 0. Por outro lado, se

é um gráfico completo, todo vértice em

tem grau

. O que exatamente você quer dizer com "não trivial"?

G

$G$

T (G)

$T(G)$

G

$G$

T (G)

$T(G)$

Θ (n^{2})

$\Theta(n^2)$

Jeffε

também é claramente maior que a conectividade de

menos 1. Isso é trivial? Você deve expandir sua pergunta com o que você já sabe sobre o problema, para que possamos julgar o que você considera trivial e o que você não considera.

G

$G$

Artem Kaznatcheev

@Jeffe Eu não acho que

para um grafo completo está correto. Tomemos, por exemplo, uma árvore que seja uma linha. A remoção de uma extremidade da árvore irá desligar a árvore em dois grupos

. Agora existem

arestas que podem ser adicionadas para torná-lo uma árvore novamente. Ao assumir todas as bordas dessa árvore, vemos que existem

árvores próximas.

Θ (n^{2})

$\Theta(n^2)$

S

$S$

T

$T$

| S | \cdot | T |

$|S|\cdot|T|$

Θ (n^{3})

$\Theta(n^3)$

corwin

Respostas:

Se tiver vértices e arestas, para qualquer árvore de abrangência de , cada uma das arestas que não estão em pode ser trocada por nenhuma das arestas no caminho em entre os pontos finais do borda não-árvore. Assumindo que não é um multigráfico, isso gera pelo menos trocas diferentes; isto é, todo tem grau pelo menos $G$ $n$ $m$ $T$ $G$ $m-n+1$ $T$ $T$ $G$ $2(m-n+1)$ $T$ $2(m-n+1)$ .

Esse limite é rígido: se tem um vértice adjacente a todos os outros e é a árvore de abrangência que consiste em todas as arestas incidentes em , então o caminho em entre os pontos finais de cada aresta não-árvore tem comprimento exatamente dois , para que cada aresta que não seja de árvore participe de exatamente dois swaps e tenha um grau exatamente $G$ $v$ $T$ $v$ $T$ $T$ $T$ $2(m-n+1)$ .

Por outro lado, se tem perímetro (menor comprimento do ciclo) , então o caminho em qualquer árvore entre os pontos finais de qualquer aresta não arborizada, juntamente com essa aresta, forma um ciclo que deve ter comprimento pelo menos , de modo que o grau mínimo no gráfico da árvore deve ser pelo menos $G$ $g$ $T$ $g$ $(g-1)(m-n+1)$ . Esse limite é restrito para alguns gráficos, como os gráficos de ciclo, os gráficos bipartidos completos e os gráficos de Moore, pois esses gráficos contêm árvores de abrangência para as quais todas as arestas que não são de árvore induzem ciclos de comprimento iguais à circunferência.

No entanto, encontrar o grau mínimo do gráfico em árvore para um determinado gráfico arbitrário (equivalentemente, encontrar uma árvore de abrangência minimizando a soma dos comprimentos dos ciclos induzidos por arestas que não são árvores) é NP-completo: consulte Deo, Prabhu e Krishnamoorthy, "Algoritmos para gerar ciclos fundamentais em um gráfico", ACM TOMS 1982 . Portanto, é improvável encontrar limites como esses que sejam justos para todos os gráficos.

David Eppstein
fonte

Obrigado pela excelente resposta. Podemos encontrar um limite superior apertado, correto para todos os gráficos?

Corwin 26/09/11

Além disso, existe um limite superior conhecido na circunferência de um gráfico conectado com

vértices e

arestas?

n

$n$

m

$m$

Corwin 26/09/11