Referência para uma classe de gráficos que preserva as distâncias do subgráfico quando solicitadas

12

Digamos que um gráfico tenha a propriedade se seus vértices puderem ser ordenados maneira que o gráfico induzido pelos vértices tenha $G$ $M$ $v_1, v_2, \ldots v_n$ $H_i$ $\{v_1, \ldots, v_i\}$ para todos . Em outras palavras, adicionar o próximo vértice em nossa ordem não afeta a métrica da distância do gráfico atual. $dist_{H_i} (v_j, v_k) = dist_G(v_j, v_k)$ $j,k \leq i$

Um exemplo desse gráfico é a grade regular . $n \times n$

Essa propriedade ou classe de gráficos tem um nome? Eles foram estudados?

reference-request graph-theory mich
fonte

Um exemplo simples de um gráfico que não não têm essa propriedade é o

-Ciclo para

. Isso ocorre porque, para qualquer pedido, os subgráficos

devem ser conectados e, portanto, no momento

,

é uma linha de comprimento

e, portanto, alguns dois vértices são distância

distância.

k

$k$

k \geq 5

$k \ge 5$

H_{i}

$H_i$

i = ⌊ k / 2 ⌋ + 2 < k

$i = \lfloor k/2 \rfloor +2 < k$

H_{i}

$H_i$

i - 1

$i-1$

i - 1 > ⌊ k / 2 ⌋

$i-1 > \lfloor k/2 \rfloor$

Andrew Morgan

Por outro lado, um candidato natural para encontrar uma boa ordem

é fazer um BFS a partir de uma escolha arbitrária de

. Ao ver

como a árvore BFS com algumas arestas extras, parece que o único obstáculo para ter propriedade

é para lá para ser algo "como" um

-Ciclo para

em

. Com "like", quero dizer que existe uma

ciclo

v_{1}, \dots, v_{n}

$v_1, \ldots, v_n$

v_{1}

$v_1$

G

$G$

M

$M$

k

$k$

k \geq 5

$k \ge 5$

G

$G$

k

$k$

com

modo que

em

. Se chamamos esse ciclo de "mínimo", então é verdade que a propriedade

é equivalente à inexistência de ciclos mínimos de comprimento de pelo menos 5?

v_{1}, \dots, v_{k}, v_{k + 1} = v_{1}

$v_1, \ldots, v_k, v_{k+1}=v_1$

k \geq 5

$k \ge 5$

d (v_{i}, v_{j}) = | i - j |

$d(v_i,v_j) = |i-j|$

G

$G$

M

$M$

Andrew Morgan

1

Um cubo tem um ciclo induzido e isométrico de 6 (remova dois vértices opostos do cubo; o que resta é o ciclo 6), mas pode ser encomendado de maneira a preservar a distância (por exemplo, BFS). Portanto, suas

motos nem sempre são obstáculos. Este exemplo também mostra que a remoção avulsa de vértices que preservam distâncias pode ficar paralisada, mesmo quando alguma outra ordem funciona.

k

$k$

David Eppstein

8

Parece que você está perguntando sobre gráficos admitindo uma ordem de eliminação que preserva a distância, que forma uma classe de gráficos estudados neste artigo:

http://epubs.siam.org/doi/abs/10.1137/S0895480195291230?journalCode=sjdmec

JimN
fonte

2

Também disponível gratuitamente na página do autor: lif-sud.univ-mrs.fr/%7Echepoi/dpo.ps

Florent Foucaud

8

Eu não tenho uma resposta para toda a sua classe de gráficos, mas três subclasses de gráficos que têm esta propriedade são os gráficos distância-hereditária , grafos cordais e gráficos medianos .

$v_1$

Os gráficos de acordes são aqueles que possuem uma ordem com a propriedade de que cada vértice sucessivo, quando adicionado, possui um clique para seus vizinhos. Essa ordem obviamente preserva a distância.

Da mesma forma, os gráficos medianos (incluindo seu exemplo de grade) têm a propriedade de que, para qualquer pedido de amplitude inicial, cada vértice possui uma vizinhança de hipercubo no momento em que é adicionado. (Veja as páginas 76–77 de Eppstein et al., "Media Theory", Springer, 2008). Novamente, essa propriedade significa que a adição não pode alterar as distâncias entre os vértices anteriores.

Há uma classe de gráficos para a qual eu não conheço um nome, que generaliza tanto os gráficos acordais quanto os hereditários à distância, que podem ser reconhecidos em tempo polinomial e que possuem sua propriedade. Eles são os gráficos conectados que podem ser construídos a partir de um único vértice adicionando vértices um a um, em que os vizinhos de cada novo vértice são um subconjunto de uma das vizinhanças fechadas do gráfico anterior. Eles são quase (mas não exatamente) iguais aos gráficos desmontáveis, a diferença é que o novo vértice não precisa estar adjacente ao vértice cuja vizinhança está sendo copiada. Uma ordem de eliminação de um gráfico acorde é uma construção desse tipo em que cada novo vértice escolhe um subconjunto de cliques de uma vizinhança. Da mesma forma, os gráficos hereditários à distância têm uma construção desse tipo em que os vizinhos de cada novo vértice são uma vizinhança fechada inteira, uma vizinhança aberta ou um único vértice. Cada novo vértice não pode alterar as distâncias dos vértices anteriores, portanto, essa sequência de construção tem a propriedade que você está procurando.

Se você definir um vértice v como "removível", se puder ser o último nesta sequência (ele possui uma vizinhança aberta que é um subconjunto da vizinhança fechada de outra pessoa), a remoção de outros vértices removíveis não altera a removibilidade de v : se vizinhança de v é um subconjunto de u's e removemos u como tendo uma vizinhança que é um subconjunto de w's, então v ainda é removível porque sua vizinhança ainda é um subconjunto de w's. Portanto, as seqüências de etapas de remoção que podemos seguir para fazer um gráfico voltar ao zero, formando um antimatóide, e uma dessas seqüências pode ser encontrada no tempo polinomial por um algoritmo ganancioso que remove repetidamente um vértice removível sempre que ele pode encontrar um. A reversão da saída desse algoritmo fornece a sequência de construção para o gráfico fornecido. O gráfico do cubo fornece um exemplo de gráfico que possui sua propriedade (um gráfico mediano), mas não é construtível dessa maneira. Penso que os gráficos medianos que podem ser construídos dessa maneira são exatamente os gráficos quadráticos (que incluem as grades regulares). Os gráficos que possuem uma sequência de construção desse tipo também incluem todos os gráficos que possuem um vértice universal, como os gráficos de roda , portanto (diferentemente dos gráficos de acordes e dos gráficos hereditários à distância), eles não são perfeitos e não são fechados sob subgráficos induzidos.

David Eppstein
fonte

a propriedade dessa classe de gráficos que você não tem certeza lembra uma ordem de eliminação da dominação. Este artigo parece relevante para a pergunta original: epubs.siam.org/doi/abs/10.1137/…

JimN

Acho que a ordem de eliminação do domínio pode ser a mesma coisa que a possibilidade de exclusão. Mas você deve vincular esse artigo a uma resposta real, porque sua "ordem de eliminação para preservação da distância" parece ser exatamente o que a pergunta original está pedindo.

David Eppstein

Referência para uma classe de gráficos que preserva as distâncias do subgráfico quando solicitadas

Respostas: