Le problème du couplage parfait de poids minimum dans un graphe G peut être résolu en un temps proportionnel au cube de n, où n dénote le nombre de sommets de G. Lorsque les sommets de G sont 2n points du plan (n points rouges et n points bleus), que les arêtes de G sont celles qui relient les points rouges aux points bleus et que le poids de l'arête {x,y} est la distance entre x et y, on obtient le problème du couplage géométrique biparti. Comme ce problème peut être résolu par la méthode du simplexe, nous avons conçu un logiciel permettant de comparer l'efficacité de quelques critères de sélection de l'arête entrante. Le but ultime de cette étude est de trouver un critère pour lequel la méthode du simplexe calcule une solution optimale en un temps proportionnel au carré de n (ou en moins de temps).

Le problème du stable maximum consiste à trouver, dans un graphe G donné, un sous-ensemble de sommets induisant un sous-graphe vide de cardinalité maximale. Sa cardinalité est apppelée nombre de stabilité et est notée alpha(G). Soit T une transformation associant le graphe T(G) au graphe G. S'il existe une constante k telle que alpha(T(G)) = alpha(G) + k pour tout graphe G, on dit que la transformation T est exacte. On peut élaborer une stratégie qui emploie ce type de transformations pour résoudre le problème du stable maximum. Nous étudions cette stratégie et présentons une méthode empirique permettant de l'évaluer. Nous présentons aussi des résultats expérimentaux concernant l'utilisation de trois transformations différentes.

Le programme Graffiti (Fajtlowicz, 1987), qui est un système de génération automatique de conjectures, a engendré la conjecture que la distance moyenne dans un graphe simple non orienté était au plus égale au nombre de stabilité du graphe. Cette conjecture a été prouvée par Fan Chung en 1988. En 1994, Dankelmann a donné une preuve plus simple et plus générale de ce résultat. Nous présentons les résultats d'une étude sur la relation entre la distance moyenne entre deux sommets du graphe G et la cardinalité maximale d'un sous-graphe induit biparti de G.

Pour répondre aux besoins croissants en communication et en diversification des services, les réseaux modernes sont munis de grandes capacités de transmission. Dans ce contexte, la panne d'une liaison ou d'un équipement du réseaux peut avoir des conséquences techniques et économiques désastreuses La conception de réseaux résistants aux pannes est donc une nécessité pour les opérateurs de télécommunications. Des modèles de sécurisation permettant une utilisation efficace des ressources du réseau seront présentés durant l'exposé. La politique de sécurisation appliquée est le reroutage partiel de bout en bout avec réutilisation des capacités. Cette méthode de réacheminement sera expliquée. Les modèles proposés permettent de déterminer simultanément les capacités des liaisons, le routage en régime normal et le reroutage pour les pannes simples des liaisons et des équipements. La complexité du problème de la sécurisation des réseaux avec le reroutage partiel de bout en bout et la réutilisation des capacités sera alors examinée. Finalement, des heuristiques permettant d'obtenir des bornes inférieures et des bornes supérieures pour le problème seront présentées, ainsi que des résultats numériques obtenus pour des instances de réseaux concrets. L'impact sur les résultats des choix des chemins du routage initial et des contraintes imposées aux chemins de secours sera également examiné.