Emaranhamento (medida gráfico) - Entanglement (graph measure)
Em teoria gráfico , emaranhamento de um grafo orientado é um número medir quão fortemente os ciclos do gráfico estão interligados. Ele é definido em termos de um jogo matemático em que n policiais tentam capturar um ladrão, que escapa ao longo das bordas do gráfico. Semelhante a outras medidas de gráficos, tais como classificação ciclo , alguns problemas algorítmicos, por exemplo jogo paridade , podem ser eficientemente resolvidos em gráficos de emaranhamento limitada.
Definição
O jogo de emaranhamento é jogado por n tiras de encontro a um ladrão de um grafo orientado G . Inicialmente, todas as bobinas estão fora do gráfico e o ladrão selecciona um vértice de partida arbitrário v de L . Mais adiante, os jogadores se movem por sua vez. Em cada mover os policiais quer ficar onde estão, ou colocar um deles no vértice atualmente ocupado pelo assaltante. O ladrão deve mover-se de seu vértice atual, ao longo de uma borda, para um sucessor que não é ocupado por um policial. O ladrão deve mover se nenhum policial é segui-lo. Se não houver um sucessor livre para que o ladrão pode se mover, ela é capturada, e os policiais vencer. O ladrão ganha se ela não pode ser capturado, ou seja, se a peça pode ser feito para durar para sempre.
Um grafo G tem emaranhamento n se n policiais ganhar no jogo emaranhamento em G , mas n - 1 policiais perder o jogo.
Propriedades e aplicações
Gráficos de emaranhamento zero e um pode ser caracterizada como se segue:
- emaranhado de G é 0 se e somente se G é acíclico
- emaranhamento de L é 1, se e somente se L não é acíclico, e em cada componente fortemente ligado de L existe um nó cuja remoção faz com que o componente acíclico.
Emaranhamento também tem sido uma noção fundamental para comprovar que a hierarquia variável do modal cálculo mu é rigorosa.
Referências
links externos
Você pode jogar o jogo emaranhamento on-line on tPlay .