| 摘要 |
<p>L'invention concerne un procédé d'application automatique d'étiquettes pour un tracé ou carte de graphe donné. Même si, dans la pratique, une étiquette est habituellement associée à une ligne (arête), un point (noeud) ou une aire, ledit procédé peut être étendu pour générer une solution d'étiquetage pour n'importe quel élément graphique avec une représentation géométrique explicite (en deux ou trois dimensions). Ce procédé apporte dans un premier temps une solution d'étiquetage pour un ensemble d'éléments graphiques G, par élimination d'un sous-ensemble de l'ensemble d'application possibles d'étiquettes pour un quelconque élément de G, et par limitation du problème d'étiquetage, au plus, à un problème d'adaptation d'un graphe biparti. Ensuite, s'il y a dans G des éléments graphiques non affectés à une application d'étiquettes, un algorithme de retour en arrière peut être utilisé pour améliorer l'espace disponible pour les éléments graphiques étiquettés. Il peut être montré que le problème d'étiquettage est de type NP si aucun élément graphique dans G n'est une ligne ou un point. Il en résulte que le problème d'application d'étiquettes à des éléments graphiques (GFLP) ne peut être résolu en temps polynominal, mais requiert l'application de connaissances heuristiques bien définies.</p> |
