Génération de fronts d’ondes focalisants localement plans 

Dans ce chapitre, nous allons voir ce qui a et´e fait par rapport `a la question du k-linkage. Pour ce faire, nous explorerons successivement les aspects algo-rithmiques, combinatoires et applicatifs du k-linkage. Pratiquement toutes les ´etudes men´ees sur le sujet, jusqu’`a aujourd’hui ont et´ faites sur des graphes non colori´es.

Au milieu et vers la fin des ann´ees 1970, on assiste `a une belle production scientifique d’un certain nombre de papiers sur la complexit´ du k-linkage. Cette p´eriode ´etait tr`es propice pour faire des ´etudes de complexit´ algo-rithmique car elle arrive juste apr`es les importantes avanc´ees au niveau du formalisme sur la th´eorie de la complexit´e, obtenues suite aux travaux de Stephen Cook [13] et de Richard Karp [24, 25]. Sur cette lanc´ee, Even, Itai et Shamir [14] montrent que le probl`eme du (k + 1)-arˆete-li´e avec k chaˆınes el´ementaires entre deux sommets s1 et t1 et une chaˆıne el´ementaire entre deux sommets s2 et t2, est N P -complet. Dans ce cas pr´ecis, les k paires de sommets se r´eduisent en une seule paire de sommets s1 et t1. On sent ici l’utilisation du th´eor`eme de Menger qui permet de r´epondre `a cette ques-tion de trouver k chaˆınes disjointes pour deux sommets. L’autre probl`eme g´en´eral qui consiste `a trouver k chaˆınes deux `a deux sommet-disjointes ou arˆete-disjointes entre k paires de sommets (s1, t1), (s2, t2), · · · , (sk, tk), est ´egalement N P -complet. La preuve peut se faire par r´eduction du probl`eme du (k + 1)-arˆete-li´e pr´ec´edent o`u les k + 1 chaˆınes deux `a deux sommet-disjointes ou arˆete-disjointes sont requises entre les k + 1 paires de sommets (s1, t1), (s1, t1), · · · , (s1, t1), (s2, t2). Cependant, il y a eu quelques r´esultats posi-tifs de complexit´e, notamment grˆace Y. Perl et Y. Shiloach, qui ont etudi´ le probl`eme du 2-li´e [31]. Ils consid`erent quatre versions du probl`eme cor-respondant aux cas suivants : le graphe G est orient´ ; G n’est pas orient´ ; les chaˆınes sont sommet-disjointes ; les chaˆınes sont arˆete-disjointes. Ils font les r´eductions polynomiales suivantes du probl`eme 2-li´e : le cas non orient´ arˆete-disjointes se r´eduit au cas non orient´ sommet-disjoints qui se r´eduit lui-mˆeme au cas orient´ sommet-disjoints qui est ´equivalent au cas orient´ arˆete-disjoints. Plus loin, ils montrent que dans le cas d’un graphe orient´ sans cycle, le probl`eme 2-li´e est polynomial d’ordre de grandeur O(|V | |E|). Cependant, de fa¸con g´en´erale, pour un graphe orient´e, le probl`eme reste N P -complet pour k = 2 [15]. Dans un autre papier paru [37] un an plus tard, Y. Shiloach montre que ce probl`eme 2-li´e, se r´esout de fa¸con polyno-miale pour les graphes non-orient´es avec le mˆeme ordre de grandeur que pr´ec´edemment. Au mˆeme moment presque, P.D. Seymour [36] obtient de bonnes caract´erisations et de bons algorithmes non seulement pour k = 2 mais surtout lorsque (s1, t1), (s2, t2), · · · , (sk, tk) se r´eduisent en trois sommets distincts. Il s’appuie sur le th´eor`eme de Mader pour la solution. Cette recherche de chaˆınes sommet-disjointes ou arˆete-disjointes, se poursuit dans les ann´ees suivantes. Ainsi au milieu des ann´ees 1990, nous no-tons les remarquables travaux de Andrei Z. Broder et ses collaborateurs. Ils prouv`erent,dans un premier temps, des conditions suffisantes pour l’existence de k ≤ (logn)k chaˆınes arˆete-disjointes dans les graphes expansibles [10], puis ils pr´esent`erent un algorithme polynomial randomis´e pour trouver le nombre optimal de chaˆınes arˆete-disjointes dans des graphes al´eatoires [9]. Nous n’oublierons pas de mentionner le c´el`ebre papier de Neil Robertson et de P.D. Seymour [35], dans lequel, ils montrent que, pour un entier k fix´e, il existe un algorithme polynomial pour r´esoudre le probl`eme du k-linkage, en utilisant le concept r´evolutionnaire de mineur des graphes. Leur algorithme utilise des constantes tr`es ´enormes qui ne facilitent pas sa praticabilit´e. La preuve de correction de leur algorithme s’´ecrit ´egalement sur plus de trois cents pages. Cependant, en consid´erant k, comme un param`etre d’entr´ee, le probl`eme demeure N P -complet [25]. On voit d´ej`a, `a travers ces quelques exemples, toute la d´elicatesse qu’il y a, `a ´etudier le probl`eme du k-linkage, mais ´egalement, on peut bien appr´ecier la profondeur d’analyse des r´esultats mis `a notre disposition par ces illustres chercheurs.

Face au caract`ere N P -complet du k-linkage, beaucoup d’algorithmes d’ap-proximation ont vu le jour. Ainsi, pour une classe de graphes particuli`ere, `a savoir les graphes planaires denses, Jon Kleinberg et Eva Tardos [28, 29], obtiennent un algorithme d’approximation de facteur constant, pour le probl`eme de recherche du nombre maximum de chaˆınes disjointes. Le premier auteur cit´e a fait beaucoup de recherches sur les algorithmes d’approxima-tion concernant les chaˆınes disjointes [26]. Mˆeme s’il existe un algorithme d’approximation de ratio O( m) pour les graphe non orient´es, il est prouv´e qu’il est difficile d’approximer le probl`eme du nombre maximum de chaˆınes arˆete-disjointes pour les graphes orient´es, avec m1/2− , pour > 0 ,o`u m est la taille du graphe [17]. Ces taux d’approximation seront am´elior´es `a la fois pour les graphes orient´es ou non [11]. Pour les graphes planaires de degr´ pair, Kleinberg [27] obtient un algorithme d’approximation avec un taux O(log2n). Cette difficult´e d’approximation s’applique ´egalement dans les graphes non orient´es, pour le cas k-linkage avec sommets disjoints [4].

Les aspects th´eoriques de la question du k-li´e ont et´ etudi´es par un nombre important d’auteurs. Les diff´erentes contributions ont permis des avanc´ees notables en th´eorie des graphes surtout au niveau de la connexit´ et des graphes extr´emaux. Parmi ces auteurs, nous citerons K. Kawarabaya-shi [20, 21] avec des co-auteurs qui ont eu `a d´eterminer des conditions mini-males sur le degr´e, pour qu’un graphe non colori´e soit k-li´e. Auparavant les techniques utilis´ees ´etaient de d´eterminer des fonctions f(k) telles que, si le graphe est f(k)-connexe, on conclut qu’il est k-li´e. Plus tard Bollobas et Tho-mason [7] prouv`erent qu’on peut trouver des fonctions f(k) lin´eaires en k pour d´eterminer qu’un graphe est k-li´e s’il est f(k)-connexe. Ils ont montr´e que tout graphe 22k-connexe est k-li´e. Cette borne lin´eaire sera am´elior´ee dans [20] et ramen´ee `a 12k-connexe comme condition suffisante pour un graphe d’ˆetre k-li´e. Paul Wollan et Thomas Robin [38] vont la ramener `a 10k. Des r´esultats g´en´eralisant le probl`eme du k-li´e vont ˆetre obtenus par Gould et les autres dans [16].

Les domaines d’applications des graphes arˆete-colori´es dans la vie r´eelle, sont multiples et vari´es : les r´eseaux au sens large (transports, t´el´ecommuni-cations,…), la robustesse des r´eseaux, la bio-informatique, · · · . En ajoutant la contrainte alternance de couleurs dans les chaˆınes, on enrichit non seule-ment la th´eorie mais aussi les aspects applicatifs. Ainsi sans entrer dans les d´etails, nous noterons les travaux significatifs de Pevzner [32, 33] en biolo-gie g´en´etique o`u ses mod`eles sont construits sur les arˆetes colori´ees. Jose R. Correa et Michel X. Goemans [22] ont travaill´e dans les communications de donn´ees et syst`emes informatiques parall`eles qui sont largement utilis´es dans les r´eseaux clos, `a travers des structures d’alternance de couleurs des arˆetes. La mod´elisation par les arˆetes colori´ees est ´egalement utilis´ee pour le contrˆole de programme informatique et des ´etudes d´emographiques [19].

La litt´erature scientifique sur l’´etude de la complexit´ algorithmique du probl`eme du k-li´e est assez fournie pour les graphes non colori´es. Cependant, en ce qui concerne les graphes arˆete-colori´es, les r´ef´erences bibliographiques sont tr`es rares. Dans ce lot de raret´e, on peut noter le papier de Yannis Manoussakis [30] dans lequel cette question a et´ abord´ee. Dans une section de son papier, il ´etablit trois int´eressants th´eor`emes sur les graphes arˆete-colori´es complets, qu’on va rappeler.

Th´eor`eme 2.4.1. [30] Il existe un algorithme O(nk), pour trouver si possible, k chaˆınes el´ementaires altern´ees deux `a deux sommet-disjointes xi − yi dans Knc , i = 1, · · · , k.

Th´eor`eme 2.4.2. [30] Il existe un algorithme O((n7/ log n)1/2), pour trouver si possible, k chaˆınes el´ementaires altern´ees deux `a deux arˆete-disjointes xi − yi dans Knc , i = 1, · · · , k.

Th´eor`eme 2.4.3. [30] Le probl`eme suivant est NP-complet :

Instance : Un graphe complet Knc, un ensemble ordonn´e de p couleurs dis-tinctes C = {c1, c2, · · · , cp}, p ≥ 4, une fonction c : E(Knc) → C, quatre sommets x1, y1, x2, y2 ∈ Knc .

Question : Knc poss`ede-t-il deux chaˆınes altern´ees sommet-disjointes Pi : xi−yi, i = 1, 2, dont les arˆetes sont colori´ees d’une fa¸con telle que la s´equence de couleurs hc1, c2, · · · , cpi est r´ep´et´ee dans chaque chaˆıne altern´ee Pi ?

La preuve de ce dernier th´eor`eme est bas´ee sur la r´eduction du probl`eme du 2-li´e dans un graphe orient´e, qui est connu comme ´etant NP-complet. Le cas k = 1 est trait´e dans le mˆeme papier o`u il est prouv´e polynomial. Des r´esultats similaires ont et´ trouv´es dans d’autres articles de Yannis Manous-sakis avec d’autres auteurs [12]. Ils y ´etudient le probl`eme de trouver dans un graphe arˆete-colori´e, une chaˆıne altern´ee joignant deux sommets donn´es et passant par des sommets donn´es. Ils montrent que ce probl`eme est NP-complet dans le cas de graphes 2-arˆete-colori´es.

On en citera un qui s’apparente `a notre question [12] en reposant le probl`eme CP :

Instance : Un graphe Gc 2-arˆete-colori´e, trois sommets distincts x, y, z ∈ V (Gc)

Question : Existe-il dans Gc une chaˆıne propre d’extr´emit´es x et y qui passe par z ?

Th´eor`eme 2.4.4. [12] le probl`eme CP est NP-complet

Compte tenu de tous ces r´esultats de complexit´e, il ´etait important, d’´etudier des conditions suffisantes pour un graphe c-arˆete-colori´e d’ˆetre k-li´e.