Les graphes triangulés

Les algorithmes

La théorie de la complexité s’intéresse à l’étude formelle de la difficulté des problèmes en informatique. Elle est basée sur les travaux d’Edmonds[13] et de Cook[24]. L’objectif de calculer la complexité d’un algorithme, est d’obtenir un ordre de grandeur du nombre d’opérations élémentaires nécessaires pour que l’algorithme fournisse la solution du problème à l’utilisateur. Ceci permet de comparer la performance des algorithmes. La notion de rapidité d’un algorithme est très importante si l’on envisage des applications pratiques. Toutefois, jusqu’au milieu du XXe siècle, la notion de rapidité d’un algorithme était vague et ne faisait pas l’objet de recherches pour elle-même.

Finalement le développement de la théorie de la complexité algorithmique depuis le milieu des années 1960 a placé la notion de rapidité d’un algorithme au coeur de questions très difficiles et profondes.

Problèmes, algorithmes, complexité

Un problème est défini par la donnée d’un objet mathématique représenté par un nombre fini de symboles (l’instance ou l’entrée) et d’une question dont la réponse dépend uniquement de l’instance. Si la réponse à la question ne peut être que « oui » ou « non », on parle de problème de décision.

D’une manière simple, un algorithme est une description de longueur finie, dans un langage de programmation, d’une suite finie d’opérations élémentaires (le calcul) ne dépendant que de l’instance et fournissant une réponse à la question (la sortie). La complexité de l’algorithme est le nombre d’opérations élémentaires nécessaires à l’exécution de l’algorithme pour une instance de taille n (nombre de symboles nécessaire à sa représentation) dans le pire des cas. Nos estimations de complexité seront toujours données à une constante multiplicative près à l’aide de la notation de Landau O. Un algorithme est de complexité O(f(n)) où f est une fonction mathématique, s’il existe une constante c telle que le nombre d’opérations nécessaires pour exécuter l’algorithme sur une instance de taille n est inférieur à c × f(n). Un algorithme est dit (en temps) polynomial si sa fonction de complexité est en O(nk) avec k _ 1 fixé. Dans ce cas, l’algorithme est considéré comme efficace.

Généralités sur le LexBFS

L’algorithme LexBFS est un algorithme très utilisé, pour des problèmes divers, et donne souvent de bon résultat. Il fournit un ordre _(1), _(2), …, _(n) des sommets du graphe donné en entrée, et cet ordre est souvent un schéma d’élimination, c’est-à-dire que le sommet _(i) a une propriété particulière dans le sous-graphe induit par {_(i), _(i + 1), …, _(n)} (pour tout i). 0000000000 Pour donner la description de l’algorithme, supposons que chaque sommet a une étiquette, qui est une suite décroissante d’entiers (au début les étiquettes sont considérées vides). Les sommets sont pris l’un après l’autre, comme dans l’algorithme de parcours en largeur classique, sauf que pour choisir à un moment donné parmi plusieurs sommets candidats, on applique un critère de comparaison on préfère les sommets dont les voisins déjà visités l’ont été très tôt. Pour exprimer cela, on attribue à chaque sommet une sorte de poids (d’autant plus grand que le sommet a été visité tôt) et on met dans l’étiquette de chaque sommet la liste (décroissante) des poids de ses voisins déjà visités. Ensuite, on choisit à chaque étape le sommet dont l’étiquette est maximum par ordre lexicographique (cet ordre est l’ordre du dictionnaire, où les lettres sont remplacées par des chiffres). Nous présentons ci-dessous l’algorithme en bref, le graphe sera supposé connexe (si jamais il ne l’est pas, on tire les conclusions sur chacune de ses composantes connexes).

Le graphe lignes d’un graphe biparti est parfait. Les graphes bipartis sont parfaits puisque la bipartition induit deux classes de couleur et par conséquent !(H) = _(H) dans tout sous-graphe induit H. L’idée de la démonstration de la conjecture forte est que tout graphe de Berge ou bien fait partie d’une classe de graphes parfaits parmi quatre classes élémentaires connues ( les graphes bipartis, leurs compléments, les graphes lignes de graphes bipartis et leurs compléments) ou bien a un type de séparation qui ne peut pas se produire dans un graphe minimalement imparfait à savoir par exemple l’étoile déconnectante que nous allons étudier prochainement pour démontrer que les graphes faiblement triangulés sont parfaits. On donne la preuve de la conjecture forte sur quelques classes particulières des graphes.

Graphes triangulés Une des caractérisations des graphes triangulés est justement par l’absence de cycles de longueur au moins 4 sans corde, donc en particulier un graphe triangulé ne possède pas de trou.

On peut remarquer ensuite que la classe des graphes triangulés est héréditaire, et il suffit donc de prouver que les anti-trous ne sont pas triangulés. Si Ck est un anticycle, avec k _ 5, et x l’un de ses sommets, alors x est relié à tous les sommets du graphe sauf ses voisins sur le cycle Ck. En particulier, x est relié à y et à un voisin z de y mais z et y ne sont pas reliés, donc x ne peut pas être simplicial. Ainsi, dès qu’un graphe contient un anti-cycle de longueur au moins 5, donc en particulier les anti-trous, il n’est pas triangulé.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Notions de base
1.1 Les graphes
1.1.1 Définitions
1.1.2 Graphes connexes
1.1.3 Arbres
1.1.4 Graphes bipartis
1.2 Les algorithmes
1.2.1 Problèmes, algorithmes, complexité
1.2.2 Les problèmes P, NP et NP-complets
2 Les graphes triangulés
2.1 Ordre d’élimination simplicial
2.1.1 Séparateur minimal
2.1.2 Sommet simplicial
2.2 Algorithme de reconnaissance
2.2.1 Généralités sur le LexBFS
2.2.2 Correction
2.2.2.1 Application de l’algorithme sur un exemple
3 Les graphes faiblement triangulés
3.1 Définition et propriétés
3.2 Caractérisation des graphes faiblement triangulés
3.2.1 Détection de 2-paire
3.2.2 Algorithme de reconnaissance
3.2.3 Application de l’algorithme sur un exemple
4 Coloration
4.1 Définitions
4.2 La classe des graphes parfaits
4.3 Coloration des graphes faiblement triangulés
4.3.1 L’opérateur de contraction
4.3.2 Algorithme OPT
5 Application