Grafo cordale
Da Wikipedia, l'enciclopedia encyclopedia
Nel campo matematico della teoria dei grafi, un grafo è cordale se ciascuno dei suoi cicli di quattro o più vertici ha una corda, che è uno spigolo che non fa parte del ciclo ma connette due vertici di quest'ultimo. In modo equivalente, ogni ciclo indotto nel grafo dovrebbe avere al più tre nodi. I grafi cordali possono anche essere caratterizzati come i grafi che hanno ordinamenti di eliminazione perfetta, come i grafi nei quali ciascun separatore minimale è una cricca, e come i grafi d'intersezione dei sottoalberi di un albero. Essi sono chiamati talvolta grafi a circuito rigido[1] o grafi triangolati.[2]
I grafi cordali sono un sottoinsieme dei grafi perfetti. Possono essere riconosciuti in tempo polinomiale, e parecchi problemi che sono difficili su altre classi di grafi come la colorazione dei grafi possono essere risolti in tempo polinomiale quando l'entrata è cordale. L'ampiezza d'albero di un grafo arbitrario può essere caratterizzata dalla dimensione delle cricche nei grafi cordali che la contengono.