Tour eulerià sense girs en U en un graf orientat simple. Eulerian tour without U-turns in a simple digraph

Q¨ UESTII ´ O,vol. 22, 3, p. 471-489, 1998 TOUR EULERI` A SENSE GIRS EN U EN UN GRAF ORIENTAT SIMPLE D. SOLER FERN´ ANDEZ Universitat Polit`ecnica de Val`encia  Sigui G = ( V ; A ) un graf orientat euleri` a simple, hi estudiem la recerca d’un tour euleri` a sense girs en U, ´ es a dir, sense rec´ orrer consecutivament parells d’arcs ( u ; v ) ; ( v ; u ) , u ; v 2 V. Desconeguda la complexitat d’aquest problema, generalitzem un resultat d’un cas particular resolt en temps polinomial, proporcionantuna condici´ o sota la qual es pot construir en temps polinomial un tour euleri` a sense girs en U sobre G. Aquesta condici´ o es basa, a m´ es a m´ es, en l’eliminaci´ o de v` ertexs candidats a contenir girs en U en un tour euleri` a amb m´ ınim nombre d’ells. Eulerian tour without U-turns in a simple digraph Paraules clau: Gir en U, graf orientat U-euleri`a, H-subgraf. Classificaci´ o AMS: 68R05,68R10 *Universitat Polit`ecnica de Val`encia. Departament de Matem`atica Aplicada. Cam´ı de Vera, 14. 46071 Val`encia. –Rebut l’abril de 1997. –Acceptat el setembre de 1998. 471 1. INTRODUCCI ´ O I CONCEPTES PREVIS Sigui G = ( V ; A ) un graf orientat, el problema de trobar-hi un tour euleri`a (tour que recorre casdascun dels arcs exactament una vegada), ´es un problema cl`assic i senzill de Teoria de Grafs. ´ Es suficient veure que G´es connex i que el nombre d’arcs que arriben a v(d + ( v ) ) coincideix amb el nombre d’arcs que surten de v(d ? ( v ) ) 8 v 2 V. Es diu aleshores que G´es euleri`a i existeixen diverses t`ecniques per trobar-hi un tour euleri`a, potser la m´es coneguda sigui la regla de Fleury. Aquest problema serveix de base per a la resoluci´o d’altres problemes m´es complexos amb aplicacions importants al camp de la investigaci´o operativa: transport de mercaderies, recollida d’escombraries, llevaneus, repartiment de correu, etc. L’estudi es complica si imposem la restricci´o que el tour euleri`a no recorri consecutivament parells d’arcs ( u ; v ) ; ( v ; u ) ,u ; v 2 V, ´es a dir, que no realitzi girs en U, girs que s´on els prohibits per antonom`asia en problemes reals de rutes de vehicles. No tot graf orientat euleri`a admet un tour euleri`a sense girs en U i si l’admet, les t`ecniques cl`assiques de recerca d’un tour euleri`a no garanteixen trobar-ne un sense girs en U. A m´es a m´es, el nombre de tours eulerians distints en un graf orientat no ´es polinomial en la grand`aria del graf com demostra Fleischner (1983). Per simplificar les refer`encies en aquest problema, direm que un graf orientat ´es Ueuleri` asi admet un tour euleri`a sense girs en U, al qual anomenarem tour U-euleri` a. Estudiem en aquest article el problema de recon`eixer si un graf orientat ´es U-euleri`a, i ens restringim al cas que el graf orientat sigui simple (sense arcs repetits). Aquest problema l’anomenarem Problema del Graf Orientat U-euleri`a (PGOU) i abreviarem l’expressi´o graf orientat euleri` a simple per g.o.e.s. Com veurem en la secci´o seg¨uent, el PGOU es pot resoldre sense necessitat d’enumerar els tours eulerians del graf orientat fins trobar-ne un sense girs en U; el problema rau en qu`e aquesta resoluci´o consumeix un temps exponencial en la grand`aria del graf orientat. La clau es troba, per tant, en saber si el PGOU ´es un problema polinomial o NP-complet. Aquesta q¨uesti´o no t´e resposta de moment, malgrat els nostres esforc¸os al respecte, encara que donada la complexitat del PGOU, tot sembla indicar que ´es NP-complet. L’objecte d’aquest article ´es, per tant, donar una condici´o suficient de g.o.e.s. Ueuleri`a, verificable en temps polinomial i amb les menors restriccions possibles. Per a tal efecte, generalitzarem un cas particular del PGOU resolt en temps polinomial per Thomassen (1990), el qual exposarem tamb´e en la secci´o seg¨uent. Al llarg d’aquest treball farem ´us de les notacions i definicions b`asiques seg¨uents, donades totes elles sobre un g.o.e.s. G = ( V ; A ) : 472 ? Anomenarem invers d’un arc, un arc paral  lel i de sentit contrari que connecta el mateix parell de v`ertexs. ? Denotarem per U(v) el nombre de parelles d’arcs inversos incidents amb el v`ertex vde G. ? Anomenarem v` ertex final un v`ertex vamb d + ( v ) = U ( v ) = 1. ? Direm que els v`ertexs v = u0 ; u1 ; : : : ; uk + 1 = w,k  0 formen un cam´ı maximal doble en G si acompleixen les tres condicions seg¨uents: 1) (d + ( v ) 6 = 2 o U ( v ) 6 = 2) i (d + ( w ) 6 = 2 o U ( w ) 6 = 2). 2) ( ui ; ui + 1 ) ; ( ui + 1 ; ui ) 2 A i = 0 ; 1 ;::: ; k. 3) Si k  1, d + ( ui ) = U ( ui ) = 2i = 1 ;::: ; k. Si k  1 als v`ertexs uii = 1 ;::: ; kels anomenarem v` ertexsinteriors del cam´ı maximal doble. ? Sigui v 2 Vamb d + ( v )  3 i sigui Tun tour euleri`a en G.Tpassa pel v`ertex v almenys tres vegades. Siguin a1a2,a3a4ia5a6tres transicions (girs) de Ten v, fetes en aquest ordre, amb a1 ;::: a6 2 A. Anomenarem 3-intercanvi l’operaci´o de permutar aquests girs en vpels girs a1a4,a3a6ia5a2(veure Figura 1). &% '$ &% '$ = ) vv a1a1 a2a2 a4a4 a5a5 a6a6 a3a3   @ @ @R @ @ @R? ? ? ? ? ? ? ? ? ? ? ? @ @ @I @ @ @I     H H H H Figura 1. Exemple de 3-intercanvi a un v`ertex v. Noteu que un 3-intercanvi ens proporciona un nou tour euleri`a en G. 2. CAS PARTICULAR I RESOLUCI ´ O DEL PGOU EN TEMPS EXPONENCIAL El PGOU generalitza un altre problema de Teoria de Grafs anomenat Problema del doble recorregut fort i que consisteix en: donat un graf no orientat connex, saber si 473 cont´e una cadena tancada que recorre cadascuna de les seves arestes exactament dues vegades, una en cada sentit i no de manera consecutiva (sense realitzar girs en U). Aquesta cadena tancada rep el nom de doble recorregut fort. El problema del doble recorregut fort va ser plantejat per Ore (1951) i el primer resultat te`oric sobre aquest problema va ser donat per Troy (1966), qui va demostrar que donat un graf no orientat G, amb tots els seus v` ertexs amb grau inferior a 4, no cont´ e un doble recorregut fort si el nombre de v` ertexs de G amb grau 3 ´ es m´ ultiple de 4. Altres autors, com Brenner i Lindon (1984) i Eggleton i Skilton (1984) van tractar el problema del doble recorregut fort, per`o va ser Thomassen (1990) qui, en les seves paraules, va resoldre el vell problema plantejat per Ore, en demostrar el teorema seg¨uent, fent ´us d’alguns resultats obtinguts per Xuong (1979): Teorema 1. Donat un graf connex no orientat G, els enunciats seg¨ uents s´ on equivalents: 1) G admet un doble recorregut fort. 2) G no cont´ e v` ertexs amb grau 1 i cont´ e un arbre generador T, tal que tota component connexa de G ? T amb un nombre imparell d’arestes, cont´ e un v` ertex v amb grau major que 3 en G. La import`ancia d’aquesta caracteritzaci´o, de la qual farem ´us a la secci´o cinquena, rau en l’exist`encia d’un algorisme polinomial que troba tal arbre o decideix que no existeix. Thomassen demostra l’exist`encia de l’algorisme anterior basant-se en l’exist`encia d’un algorisme polinomial per resoldre el Problema de la Paritat en matroids gr`afiques, algorisme donat per Gabow i Stallmann (1986), encara que aquesta demostraci´o cont´e algunes falles. Benavent i Soler (1998a) proporcionen una versi´o corregida d’aquesta demostraci´o i, basant-se en ella, donen un algorisme que en temps polinomial troba el doble recorregut fort o decideix que tal recorregut no existeix. Per tant, el problema del doble recorregut fort ´es un cas particular del PGOU —´es suficient desdoblar cada aresta del graf no orientat en dos arcs de sentits oposats (veure exemple en Figura 2)— resolt en temps polinomial. Com hem dit a la secci´o anterior, malgrat els nostres esforc¸os al respecte, no saben si el PGOU ´es polinomial o NP-complet, per`o almenys el sabem resoldre en temps exponencial mitjanc¸ant la seva transformaci´o al Problema del Circuit Hamiltoni`a que, recordem, consisteix a saber si un graf orientat G = ( V ; A ) admet un circuit que passi per cadascun dels v`ertexs de Vexactament una vegada (circuit hamiltoni`a). Aquest problema ´es NP-complet i existeixen diversos m`etodes per a la seva resoluci´o. Laporte (1992) recopila els coneguts fins a la data. 474 El PGOU sobre un graf orientat euleri`a no necess`ariament simple G = ( V ; A ) es transforma f`acilment al Problema del Circuit Hamiltoni`a en la forma seg¨uent: Construir un graf orientat G 0 = ( V 0 ; A 0 ) on V 0 es correspon biun´ıvocament amb A (va 2 V 0 si i sols si a 2 A) i l’arc ( va ; vb ) pertany a A 0 si, i sols si, a = ( i ; j ) ,b = ( j ; k ) i k 6 = i, ´es a dir, cada arc de G 0 es correspon amb un gir no en U en el graf orientat G.´ Es f`acil veure que Gadmet un tour U-euleri`a si, i sols si, G 0 admet un circuit hamiltoni`a, essent evident la transformaci´o del circuit hamiltoni`a en G 0 al tour U-euleri`a en G. l l l l 6 6 ? ? - -  ? ? ? ? ? ? ? ? ? ? ? ? @ @ @ @ @ @R @ @ @ @ @ @I l l l l = ) ? ? ? ? ? ? @ @ @ @ @ @ Figura 2. Exemple de transformaci´o d’un problema del doble recorregut fort en un PGOU. 3. H-SUBGRAFS Un graf orientat simple U-euleri`a ha d’acomplir dues condicions b`asiques: no contenir v`ertexs finals i contenir almenys un v`ertex vamb d + ( v ) 6 = 2 o U ( v ) 6 = 2 (no ser un cicle doble). En aquesta secci´o veiem una altra condici´o necess`aria que ha d’acomplir tal graf orientat. ´ Es per aix`o que donem la definici´o seg¨uent: Definici´ o 2. Sigui G = ( V ; A ) un g.o.e.s. i siguin u ; v 2 V amb d + ( u ) = d + ( v ) = 2i U(u)=U(v)=1 tals que existeix en G un cam´ ı maximal doble u = u0 ; u1 ;::: ; uk + 1 = v amb k  0. Anomenaren H-subgraf de G un subgraf de G format per tots els v` ertexs d’aquest cam´ ı maximal doble, junt amb tots els arcs incidents i v` ertexs adjacents als v` ertexs esmentats. A u i v els anomenarem v` ertexs intermedis del H-subgraf. j j j j j j j j j j j j j j w t w t k s k s u v u v 6 6 -  ? ? 6 6 - ........ ........ -  ? ? Figura 3. Formes de H-subgraf. 475 La Figura 3 ens mostra els dos tipus de H-subgrafs que poden apar`eixer en un g.o.e.s., segons que k = 0 o k > 0. Noteu que en aquests H-subgrafs es podr`a donar eventualment un dels dos casos seg¨uents: a) k = s i = o w = ti b) k = t i = o w = s. Un tour euleri`a amb m´ınim nombre de girs en U sobre un g.o.e.s. no pot realitzar dos girs en U en un v`ertex interior d’un cam´ı maximal doble que contingui per un extrem un v`ertex vamb d + ( v ) = 2 i U ( v ) = 1. En cas contrari, creuant ambd´os girs en U, obtindr´ıem dos circuits que en creuar-se en vdonarien un tour euleri`a amb un gir en U menys. De fet, es podr`a veure m´es endavant amb un raonament similar, que un tour euleri`a amb m´ınim nombre de girs en U sobre un g.o.e.s. no contindr`a girs en U als v`ertexs interiors d’un cam´ı maximal doble, independentment de com siguin els seus v`ertexs extrems. Per tant, cada vegada que aparegui un H-subgraf del segon tipus (k > 0), es podr`a transformar en un altre del primer tipus (k = 0) comprimint el cam´ı maximal doble en dos arcs inversos que uneixin els v`ertexs intermedis del H-subgraf. Si abans de realitzar aquesta compressi´o, exist´ıs al graf orientat original l’arc (u ; v) o l’arc (v ; u) (per`o no els dos ja que U ( u ) = U ( v ) = 1), substitu¨ım l’arc (u ; v) ( (v ; u) ) per la cadena (u ; u 0 ),(u 0 ; v)((v ; v 0 ),(v 0 ; u) ) on v 0 (u 0 ) ser`a un nou v`ertex amb grau de sortida i grau d’arribada 1. El motiu d’aquesta substituci´o ´es que el nou graf orientat continu¨ı essent simple, sense lloc a confusi´o a l’hora de realitzar o no girs en U. A partir d’ara suposarem doncs, i sense p`erdua de generalitat, que tots els H-subgrafs tenen els seus v`ertexs intermedis adjacents per dos arcs inversos. Definici´ o 3. Considerem un H-subgraf d’un g.o.e.s. i suposem que u i v s´ on els seus v` ertexs intermedis i (u,v),(v,u), (u,k),(w,u),(s,v) i (v,t) els arcs del H-subgraf. Anomenarem trencament del H-subgraf al desdoblament del seus v` ertexs intermedis en u 0 i u 00 i en v 0 i v 00 respectivament, de manera que obtenim dos camins sense v` ertexs interiors en com´ u ( s ; v 0 ; u 00 ; k ) i ( w ; u 0 ; v 00 ; t ) (veure Figura 4). j j j j j j j j j j j j j j w t w’ t k s k s u v u 0 v 00 u 00 v 0 6 6 -  ? ? 6 6 ? ?  - = ) Figura 4. Trencament d’un H-subgraf. En trencar un H-subgraf, eventualment es podria desconnectar el graf orientat original. Donat un g.o.e.s. G, denotem per HGel nombre de components fortament connexes 476 (c.f.c.) que apareixen al graf orientat resultant de trencar tots els seus H-subgrafs. Convenim que HG = 1 si Gno t´e H-subgrafs. HGest`a ben definit, ja que no dep`en de l’ordre en qu`e es produeix el trencament dels H-subgrafs, en no tenir dos H-subgrafs distints, v`ertexs intermedis comuns. Teorema 4. Tot tour euleri` a en un g.o.e.s. G t´ e almenys HG ? 1girs en U en v` ertexs intermedis de H-subgrafs. Demostraci´ o. Suposem que existeix un tour euleri`a en Gamb kgirs en U en v`ertexs intermedis de H-subgrafs, essent k < HG ? 1. Si trenquem cadascun dels H-subgrafs on el tour no ha realitzat un gir en U en un dels seus v`ertexs intermedis, no es desconnecta el graf G. Com que cada vegada que es trenca un H-subgraf s’afegeix com a molt una c.f.c. al nombre d’existents, si trenquem tots els H-subgrafs de G tindrem com a m`axim k + 1 c.f.c. amb k + 1 < HG, fet que ´es absurd per definici´o de HG.  j j j j j j j j j j j j (a) (b) 6 ?   ? 6 ? 6 6 ?  - 6 ? ? 6    *   *   * H H H Hj H H H Hj H H H Hj     H H H HY (b’) (a’) h h h h h h h h h h h h h h h h h h h h h h h h -    6 ? 6 ? 6 ? -  -  - - - - ? ?@ @R     A A A AU     A A A AU Figura 5. Trencament dels H-subgrafs de dos grafs orientats similars amb resultats diferents. 477 Per tant, tenim la condici´o necess`aria de graf orientat simple U-euleri`a seg¨uent: Corol  lari 5. Si G ´ es un graf orientat simple U-euleri` a, aleshores HG = 1. En la Figura 5 es constaten clarament els resultats del Teorema 4 per a dos grafs orientats eulerians pr`acticament id`entics. Mentre que al graf orientat (a) HG = 1, al graf orientat (b) HG = 3. En trencar els H-subgrafs de (a) obtenim directament un tour U-euleri`a. En canvi, ´es evident que tot tour euleri`a en (b) realitzar`a almenys dos girs en U per unir les tres c.f.c. resultants de trencar els seus H-subgrafs. 4. V` ERTEXS SENSE GIRS EN U Suposat que un g.o.e.s. acompleix les tres condicions necess`aries per a ´esser U-euleri`a esmentades a la secci´o anterior, veurem en aquesta secci´o en quins tipus de v`ertexs tenim la garantia que un tour euleri`a amb m´ınim nombre de girs en U no hi realitzi girs en U. Per tal motiu necessitarem demostrar alguns resultats. Teorema 6. Sigui G = ( V ; E ) un g.o.e.s. i T un tour euleri` a en ell. Existeix un tour euleri` a T 0 en G que no realitza girs en U als v` ertexs i amb, b´ e d + ( i ) > 3, b´ e d + ( i ) = 3 i U ( i ) = 1, i que realitza els mateixos girs que T a la resta de v` ertexs. Demostraci´ o. Suposem que Trealitza el gir en U ( j ; i )( i ; j ) i que comenc¸a en aquest gir. Sigui ( u ; i )( i ; v ) el gir seg¨uent per ide T. Considerem els dos casos de l’enunciat: – Si d + ( i ) > 3, existeix almenys un altre gir per ide T ( w ; i )( i ; k ) amb k 6 = u, que per l’ordre establert va despr´es del ( u ; i )( i ; v ) . Si realitzem el 3-intercanvi f ( j ; i )( i ; j ) ; ( u ; i )( i ; v ) ; ( w ; i )( i ; k ) g ! f ( j ; i )( i ; v ) ; ( u ; i )( i ; k ) ; ( w ; i )( i ; j ) g obtenim un altre tour euleri`a sobre Gsense almenys el gir en U ( j ; i )( i ; j ) . – Si d + ( i ) = 3 i U ( i ) = 1, sigui ( w ; i )( i ; k ) el tercer gir de Tper realitzar en i, aqu´ı ´es evident que k 6 = u, per tant, si realitzem el mateix 3-intercanvi que al cas anterior, obtenim un altre tour euleri`a sobre Gsense el gir en U ( j ; i )( i ; j ) . Si repetim aquest procediment les vegades que necessitem, obtindrem un tour euleri`a T 0 en Gque acompleix les condicions del teorema.  478 Per altra banda, a la Figura 6 donem les diferents formes en qu`e pot apar`eixer un v`ertex vamb d + ( v ) = 2 i U ( v ) = 1 en un g.o.e.s. sense v`ertexs finals: 1) 4) 2) 5) 3) 6) h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h v v v v v v w w w w w d + ( w )  4 - - - - - - - - - - - -  6 ? 6 ? 6 ? 6 ? 6 ? 6 ? 6 ?   1   ) P P Pq P P Pi   1   ) P P Pq A AK   A AK   1 P P Pq Figura 6. Formes en qu`e pot apareixer un v`ertex vamb d + ( v ) = 2 i U ( v ) = 1 en un g.o.e.s. sense v`ertexs finals. En un tour euleri`a amb m´ınim nombre de girs en U en un g.o.e.s., mai apareixer`a un gir en U al v`ertex vals casos 1 i 2 de la Figura 6, ja que cas d’apar`eixer en vun gir en U, si es creua amb l’altre gir per l’esmentat v`ertex, s’obtenen dos circuits que coincideixen al v`ertex w. A continuaci´o, aquests dos circuits es poden unir en wi pel Teorema 6, un 3-intercanvi adequat faria desapar`eixer els girs en U que es formaren en w. Als casos 3 i 4 de la Figura 6, si apliquem la t`ecnica esmentada per als casos 1 i 2, si es formara un gir en U en w, un estudi detallat de totes les possibilitats ens diu que no tenim la garantia que un 3-intercanvi el fera desapar`eixer. El cas 5, ja que als v`ertexs interiors d’un cam´ı maximal doble no es realitzen girs en U, es redueix a la resta de casos, depenent de l’altre v`ertex w, extrem del cam´ı maximal doble que comenc¸a en v. El cas 6 ha estat estudiat a la secci´o anterior. D’all`o que hem dit per als casos 1, 2 i 5 obtenim el resultat seg¨uent: Teorema 7. Sigui G=(V,A) un g.o.e.s. i sigui v = u0 ; u1 ;::: ; uk + 1 = w un cam´ ı maximal doble en G, amb k  0, d + ( v ) = 2,U ( v ) = 1i, b´ e d + ( w )  4, b´ e d + ( w ) = 3iU ( w ) = 1. Cap tour euleri` a amb m´ ınim nombre de girs en U sobre G, realitza girs en U als v` ertexs d’aquest cam´ ı maximal doble. 479 [7] Laporte, G. (1992). «The Traveling Salesman Problem: An Overview of Exact and Aproximate Algorithms».European Journal of Operational Research,59, 231-247. [8] Ore, O. (1951). «A Problem Regarding the Tracing of Graphs».Elem. Math.,6, 3, 49-53. [9] Thomassen, C. (1990). «Bidirectional Retracting-free Double Tracing and Upper Embeddability of Graphs».Journal of Combinatorial Theory, Series B,50, 2, 198-207. [10] Troy, D.J. (1966). «On Traversing Graphs».Amer. Math. Monthly,73, 497-499. [11] Xuong, N.H. (1979). «How to Determine the Maximun Genus of a Graph». Journal of Combinatorial Theory, Series B,26, 217-225. 486 ENGLISH SUMMARY EULERIAN TOUR WITHOUT U-TURNS IN A SIMPLE DIGRAPH D. SOLER FERN´ ANDEZ Universitat Polit`ecnica de Valencia  Let G = ( V ; A ) be a simple directed Eulerian graph, here we study if G admits an Eulerian tour without U-turns, that is, without traversing consecutively pairs of arcs ( u ; v ) ; ( v ; u ) u ; v 2 V. This problem can be solved by transforming it into a Hamiltonian circuit problem, but we do not know its complexity despite our efforts, so in this paper we give a condition under which we can find, in polynomial time, an Eulerian tour without U-turns in G. To give this condition, on the one hand, we generalize a result about a particular case solved in polynomial time (the one known as the strong doubletracing problem), on the other, we try to identifyvertices inwhich an Eulerian tour with a minimum number of U-turns, will make no U-turns. Keywords: U-turn, U-Eulerian digraph, H-subgraph. AMS Classification: 68R05,68R10 *Universitat Polit`ecnica de Val`encia. Departament de Matem`atica Aplicada. Cam´ı de Vera, 14. 46071 Val`encia. –Received April 1997. –Accepted Setember 1998. 487 Let G = ( V ; A ) be a simple Eulerian digraph, we study if it contains an Eulerian tour without U-turns (without traversing consecutively pairs of arcs ( u ; v ) ; ( v ; u ) ,u ; v 2 V). Such a tour is called a U-Eulerian tour and if the answer is positive, we say that Gis U-Eulerian. We do not know the complexity of this problem, but we can solve it in exponential time by transforming it into a Hamiltonian Circuit Problem. The purpose of this paper is then, to give a simple sufficient condition that can be checked in polynomial time, to verify that a simple Eulerian digraph is U-Eulerian. This condition makes use of a particular case solved in polynomial time, which occurs when the digraph Gis the result of splitting each edge of a simple non directed graph G  into two arcs of opposite direction. In this case, Thomassen (1990) proves that G is U-Eulerian iff G  has no end-vertices and it contains a spanning tree T  such that every connected component of G  ? T  has an even number of edges or contains a vertex vwith d ( v ) > 3 in G  . Checking the existence of tree T  and constructing (if such be the case) the U-Eulerian tour, takes polynomial time. Let v 2 V, we denote by U ( v ) the number of pairs of arcs ( u ; v ) ; ( v ; u ) , with uadjacent to v. We will suppose without loss of generality that Gdoes not have vertices vwith d + ( v ) = U ( v ) = 2. Let u ; v 2 Vwith d + ( v ) = d + ( u ) = 2, U ( u ) = U ( v ) = 1 and ( u ; v ) ; ( v ; u ) 2 A, we call Hsubgraph, the subgraph of Gformed by u ; v, its incident arcs and its adjacent vertices. Breaking this H-subgraph means splitting uand vinto two respective pairs of vertices u 0 ; u” and v 0 ; v” such that if ( u ; v ) ; ( v ; u ) ; ( u ; k ) ; ( w ; u ) ; ( s ; v ) ; ( v ; t ) 2 A, we obtain two paths in Gwithout common interior vertices ( s ; v 0 ; u” ; k ) and ( w ; u 0 ; v” ; t ) . Let HGbe the number of connected components of Gobtained by breaking all its H-subgraphs, if HG 6 = 1, then Gis not U-Eulerian. If HG = 1 and Ghas no final vertices (vertices vwith d + ( v ) = U ( v ) = 1), then the only vertices that determine if an Eulerian tour in Gwith a minimum number of U-turns is not U-Eulerian, form a set of vertices vwith d + ( v ) = 3 and U ( v ) > 1 and, besides, there is a subset of such vertices, denoted by MGwhich contains ”very bad”vertices if U-turns are to be avoided. Let G 0 = ( V ; E 0 ) be a non directed graph such that ( u ; v ) 2 E 0 iff ( u ; v )( v ; u ) 2 Aand let G” = ( V ; E” ) be another non directed graph such that ( u ; v ) 2 E” iff d + ( u ) = d + ( v ) = 3, U ( u ) > 1, U ( v ) > 1 and ( u ; v ) ; ( v ; u ) 2 A. The following theorem generalizes the result of Thomassen as a sufficient condition for a U-Eulerian simple digraph and can also be checked in polynomial time: 488 Theorem. Let G = ( V ; A ) be a simple Eulerian digraph without final vertices, HG = 1 and MG = / 0. G is U-Eulerian if each connected componet G 0 iof G 0 verifies one of the two following conditions: (a) G 0 iis not a cycle and it contains a spanning tree T 0 isuch that each connected component of G 0 i ? T 0 icontains an even number of edges or a vertex of degree greater than 3 in G 0 i. (b) Every connected component G 00 ikof G 00 contained in G 0 iis not a cycle and it has a spanning tree T 00 iksuch that eachconnected component of G 00 ik ? T 00 ikcontains an even number of edges. 489