Sobre propriedades da matriz de adjacência quando um gráfico é plano

21

1- Existem propriedades específicas para a matriz de adjacência quando um gráfico é plano?
2- Existe algo especial para calcular a matriz de adjacência permanente quando um gráfico é plano?

marjoonjan
fonte
8
Faça pelo menos uma verificação ortográfica antes de escrever suas perguntas. Não é palanr, é planar
Suresh Venkat
:)) OK Sureh, prometo fazer! :)
marjoonjan
E o gráfico planar bipartido?
Mohammad Al-Turkistany
Pessoalmente, não me importo com o gráfico planar bipartido, mas se é algo em sua mente, é bem-vindo! compartilhe por favor!
Marjoonjan
A computação de um gráfico plano bipartido é permanente e fácil?
T ....

Respostas:

25

A computação determinante e permanente de gráficos planares é tão difícil quanto computá-los em gráficos gerais. Eles estão completos para GapL e #P, respectivamente. Veja este artigo de Datta, Kulkarni, Limaye, Mahajan para mais detalhes.

Shiva Kintali
fonte
A computação de um gráfico plano bipartido é permanente e fácil?
T ....
@Arul Sim, pelo algoritmo FKT en.wikipedia.org/wiki/FKT_algorithm
Tyson Williams
15

É mais uma propriedade da matriz de incidência do que a matriz de adjacência, mas uma propriedade importante dos gráficos planares é que eles são exatamente os gráficos cujo gráfico matróide é o dual de outro gráfico matróide. A relação com as matrizes de incidência é que o gráfico matróide descreve conjuntos de colunas independentes na matriz.

David Eppstein
fonte
9

Há uma propriedade da matriz de distância (e não a matriz de adjacência) de gráficos planares restritos que podem ser de interesse, a propriedade Monge . A propriedade Monge (devido a Gaspard Monge) para gráficos planares significa essencialmente que certos caminhos mais curtos não podem se cruzar. Consulte Wikipedia: Matriz de Monge para obter uma descrição formal da propriedade Monge. Djidjev (WG 1996) ( artigo no site de Djidjev ) e Fakcharoenphol e Rao (FOCS 2001) ( Vídeo ) mostram como explorar as propriedades não cruzadas em algoritmos de caminho mais curto.

Christian Sommer
fonte
6

Não tenho certeza de que tipo de propriedades você procura, mas o raio espectral dos gráficos planares é uma dessas quantidades (o valor absoluto máximo de um valor próprio da matriz adjacente). Veja, por exemplo, este documento .

Suresh Venkat
fonte
6

Embora não esteja diretamente relacionado à sua pergunta, você pode querer examinar o trabalho sobre seqüências de graus de gráficos planares. Não há caracterizações conhecidas de quando uma sequência de graus é a sequência de graus de um gráfico plano. No entanto, existem vários documentos interessantes sobre esses assuntos, incluindo:

http://www.jstor.org/pss/2100346

Joseph Malkevitch
fonte