Triangulação de gráfico

O gráfico de triangulação é um problema de algoritmos e teoria de grafos .

Triangulação de um gráfico

Definição

Noção

Estamos trabalhando em um gráfico não direcionado . Um gráfico é triangulado se qualquer ciclo de comprimento maior que 3 admitir uma corda. Também é considerado cordal .

Problema de algoritmo

A triangulação de um gráfico não triangulado consiste em torná-lo triangulado. A triangulação de um gráfico não é única e a busca pela triangulação ótima (no sentido do número mínimo de arestas adicionadas) é um problema NP-Completo .

Algoritmo

soit G un graphe non orienté tantque il reste des sommets non marqués sommet <- Choisir un Sommet Relier deux à deux les voisins de sommet Marquer(sommet)

Melhoria e heurística

O algoritmo acima é extremamente simplista. Consiste em percorrer todos os vértices, conectar os vizinhos do vértice aos pares e, em seguida, "removê-lo" do gráfico. Isso para todas as cúpulas. Complexidade sem contar o tempo da escolha do topo. Este algoritmo não encontra uma triangulação ótima (no sentido do número de arestas adicionadas). Ele apenas permite que você encontre uma triangulação do gráfico. O(não){\ displaystyle O (n)}

Escolha de heurísticas

Podemos ver que a eficiência do algoritmo depende de como tirar os vértices. Podemos, portanto, trazer heurísticas diferentes para melhorar muito o resultado.

Heurísticas com pontuação

A pontuação é calculada de acordo com o número de vizinhos de um vértice e o número de seus vizinhos conectados dois a dois. Portanto, tentamos a cada vez pegar o topo onde o número de arestas a serem adicionadas é o menor.

svsore=deg∗deg-2∗nãoombreVoeuseunãoReeueue{\ displaystyle score = deg * deg-2 * connectedNightNumber}

Com deg igual ao grau do vértice e númeroVoisin Conecta o número de vizinhos ligados dois a dois do vértice em questão.

Heurísticas especializadas

Embora a heurística com pontuação seja eficaz, geralmente é necessário desenvolver suas próprias heurísticas de acordo com o gráfico. Por exemplo, levando em consideração suas peculiaridades simétricas.

Testando se um gráfico é triangulado

O algoritmo mais usado para verificar se um gráfico está triangulado é uma varredura de largura lexicográfica (chamada Lex-BFS ). Este algoritmo começa numerando cada um dos vértices na ordem definida no algoritmo que é linear . O(m+não){\ displaystyle O (m + n)}

Algoritmo

Entrée Un graphe orienté G=(V,ε){\displaystyle G=(V,\varepsilon )} Sortie La numérotation lambda des sommets de G Pour sommet x ∈ V{\displaystyle x\ \in \ V} étiquette(x)=0 FinPour Pour i=n jusqu'à 1 Choisir un sommet non numéroté x∈V{\displaystyle x\in V} d'étiquette lexicographique maximum λ(i)←x{\displaystyle \lambda (i)\leftarrow x} Pour voisin non numéroté y de x Ajouter i à étiquette(y) FinPour FinPour

LexBfs em um gráfico

Notas e referências