Walid Belkhir

Luigi Santocanale

Undirected Graphs of Entanglement 2

Entanglement is a complexity measure of directed graphs that origins in fixed point theory. This measure has shown its use in designing efficient algorithms to verify logical properties of transition systems. We are interested in the problem of deciding whether a graph has entanglement at most k. As this measure is defined by means of games, game theoretic ideas naturally lead to design polynomial algorithms that, for fixed k, decide the problem. Known characterizations of directed graphs of entanglement at most 1 lead, for k = 1, to design even faster algorithms. In this paper we give two distinct characterizations of undirected graphs of entanglement at most 2. With these characterizations at hand, we present a linear time algorithm to decide whether an undirected graph has this property.

Introduction

Entanglement is a complexity measure of finite directed graphs introduced in [START_REF] Berwanger | Entanglement-a measure for the complexity of directed graphs with applications to logic and games[END_REF][START_REF] Berwanger | Games and Logical Expressiveness[END_REF] as a tool to analyze the descriptive complexity of the Propositional Modal µ-calculus. Roughly speaking, its purpose is to quantify to what extent cycles are intertwined in a directed graph. Its game theoretic definition -by means of robbers and cops -makes it reasonable to consider entanglement a generalization of the tree-width of undirected graphs [START_REF] Seymour | Graph searching and a min-max theorem for treewidth[END_REF] to another kind of graphs, a role shared with other complexity measures appeared in the literature [START_REF] Gottlob | Hypertree decompositions: A survey[END_REF][START_REF] Johnson | Directed tree-width[END_REF][START_REF] Safari | d-width: a more natural measure for directed tree width[END_REF][START_REF] Berwanger | Dag-width and parity games[END_REF].

A peculiar aspect of entanglement, and also our motivation for studying it among the other measures, is its direct filiation from fixed point theory. Its first occurrence takes place within the investigation of the variable hierarchy [START_REF] Berwanger | On the variable hierarchy of the modal mucalculus[END_REF][START_REF] Berwanger | The variable hierarchy of the µ-calculus is strict[END_REF] of the Propositional Modal µ-Calculus [START_REF] Kozen | Results on the propositional µ-calculus[END_REF]. The latter, hereby noted L µ , is nowadays a well known and appreciated logic, capable to express many computational properties of transition systems while allowing their verification in some feasible way. As a µ-calculus [START_REF] Arnold | Rudiments of µ-calculus[END_REF] L µ increases the expressive power of Hennessy-Milner logic, i.e. multimodal logic K, by adding to it least and greatest fixed point operators that bind monadic variables. Showing that there are µ-formulas φ n that are semantically equivalent to no formula with less than n bound variables is the variable hierarchy problem for a µ-calculus. Such a hierarchy is also meaningful in the simpler setting of iteration theories [START_REF] Bloom | Iteration theories[END_REF].

The relationship between entanglement and the number of bound variables in a µ-term might be too technical to be elucidated here. Let us say, however, that entanglement roughly is a syntactic analogous of the variable hierarchy, the latter being defined only w.r.t. a given semantics. To argue in this direction, the relevant fact is Proposition 14 of [START_REF] Berwanger | Entanglement-a measure for the complexity of directed graphs with applications to logic and games[END_REF], stating that the entanglement of a directed graph is the minimal feedback of its finite unravellings.

A second important topic in fixed point theory is the model checking problem for L µ . The main achievement of [START_REF] Berwanger | Entanglement-a measure for the complexity of directed graphs with applications to logic and games[END_REF] states that parity games whose underlying graphs have bounded entanglement can be solved in polynomial time. This is a relevant result for the matter of verification, since model checking L µ is reducible in linear time to the problem of deciding the winner of a parity game. Berwanger's result calls for the problem of deciding whether a graph has entanglement at most k, a problem which we address in this paper. When settled, we can try to exploit the main result of [START_REF] Berwanger | Entanglement-a measure for the complexity of directed graphs with applications to logic and games[END_REF], for example by designing algorithms to model check L µ that may perform well in practice. We shall argue that, for fixed k, deciding whether a graph has entanglement at most k is a problem in the class P. The algorithms solving these problems can be combined to show that deciding the entanglement of a graph is in the class EXPTIME. We have no reasons to believe that the problem is in NP. Let us mention on the way that a problem that we indirectly address is that of solving parity games on undirected graphs. These games can be solved in linear time if Eva's and Adam's moves alternate. Yet, the complexity of the problem is not known if consecutive moves of the same player are allowed.

In this paper we show that deciding whether an undirected graph G belongs to U 2 , the class of undirected graphs of entanglement at most 2, can be solved in time O(|V G |). We shall present an algorithm that crucially depends on two characterizations of the class U 2 . One of them proceeds by forbidden subgraphs: an undirected graph belongs to U 2 if and only if it does not contain (i) a simple cycle of length strictly greater than 4, (ii) a length 3 simple cycle whose vertices have all degree 3, (iii) a length 4 simple cycle with two adjacent vertices of degree 3. A second characterization constructs the class U 2 from a class of atomic graphs, called the molecules, and an operation, the legal collapse, that glues together two graphs along a prescribed pair of vertices.

The two characterizations may be appreciated on their own, independently of the algorithm they give rise. Entanglement is an intrinsically dynamic concept, due to its game theoretic definition. As such it is not an easy object of study, while the two characterizations prepare it for future investigations with standard mathematical tools. They also suggest that entanglement is a quite robust notion, henceforth worth being studied independently of its fix-point theoretic background. As a matter of fact, some of the properties we shall encounter have already been under focus: the combinatorial characterization exhibits surprising analogies with the class of House-Hole-Domino free graphs, see [START_REF] Jamison | On the semi-perfect elimination[END_REF][START_REF] Chepoi | Finding a central vertex in an HHD-free graph[END_REF], a sort of generalization of graphs admitting a perfect elimination ordering. These graphs arise as the result of looking for wider notions of ordering for graphs that still ensure nice computational properties. On the other hand, the algebraic characterization recalls the well known fact that graphs of fixed arbitrary tree-width may be constructed by means of an algebra of pushouts and relabelings [START_REF] Courcelle | Graph rewriting: an algebraic and logic approach[END_REF]. The algebra of legal collapses suggests that, for entanglement, it might be possible to develop an analogous generic algebraic framework. It also points to standard graph theoretic ideas, such as n-connectiveness, as the proper tools by which to analyze entanglement.

Clearly, a work that still need to be carried out is to look for some useful characterization of directed graphs of entanglement at most k. At present, characterizations are known only for k ≤ 1 [1, Proposition 3]. We believe that the results presented here suggest useful directions to achieve this goal. In particular, a suggestive path is to generalize the algebra of molecules and legal collapses to an undirected setting. This path might be a feasible one considering that many scientists have recently developed ideas and methods to lift some algebraic framework from an undirected to a directed setting. W.r.t. the algebra of entanglement, a source of ideas might be the recent development of directed homotopy theory from concurrency [START_REF] Goubault | Dihomotopy as a tool in state space analysis[END_REF].

Acknowledgement. We would like to thank the anonymous referees for their useful comments, and for suggesting how to obtain the algorithm presented in Section 6 out of the algebraic framework introduced in Section 3.

Entanglement Games

The entanglement of a finite digraph G, denoted E(G), was defined in [START_REF] Berwanger | Entanglement-a measure for the complexity of directed graphs with applications to logic and games[END_REF] by means of some games E(G, k), k = 0, . . . , |V G |. The game E(G, k) is played on the graph G by Thief against Cops, a team of k cops. The rules are as follows. Initially all the cops are placed outside the graph, Thief selects and occupies an initial vertex of G. After Thief's move, Cops may do nothing, may place a cop from outside the graph onto the vertex currently occupied by Thief, may move a cop already on the graph to the current vertex. In turn Thief must choose an edge outgoing from the current vertex whose target is not already occupied by some cop and move there. If no such edge exists, then Thief is caught and Cops win. Thief wins if he is never caught. The entanglement of G is the least k ∈ N such that k cops have a strategy to catch the thief on G. It will be useful to formalize these notions.

Definition 1. The entanglement game E(G, k) of a digraph G is defined by: -Its positions are of the form (v, C, P ), where v ∈ V G , C ⊆ V G and |C| ≤ k, P ∈ {Cops, T hief }. -Initially Thief chooses v 0 ∈ V and moves to (v 0 , ∅, Cops). -Cops can move from (v, C, Cops) to (v, C ′ , T hief ) where C ′ can be 1. C : Cops skip, 2. C ∪ { v } : Cops add a new Cop on the current position, 3. (C \ { x }) ∪ { v } : Cops move a placed Cop to the current position. -Thief can move from (v, C, T hief ) to (v ′ , C, Cops) if (v, v ′ ) ∈ E G and v ′ / ∈ C.
Every finite play is a win for Cops, and every infinite play is a win for Thief.

We let

E(G) = min{ k | Cops have a winning strategy in E(G, k) } .
It is not difficult to argue that there exist polynomial time algorithms that, for fixed k ≥ 0 decide on input G whether E(G) ≤ k. Such an algorithm constructs the game E(G, k) whose size is polynomial in

|V G | and |E G |, since k is fixed. Since the game E(G, k) is clopen, i.e.
it is a parity game of depth 1, it is well known [START_REF] Jurdzinski | Small progress measures for solving parity games[END_REF] that such game can be solved in linear time w.r.t. the size of the graph underlying E(G, k).

In [START_REF] Berwanger | Entanglement-a measure for the complexity of directed graphs with applications to logic and games[END_REF] the authors proved that E(G) = 0 if and only if it is G is acyclic, and that E(G) ≤ 1 if and only if each strongly connected component of G has a vertex whose removal makes the component acyclic. Using these results it was argued that deciding whether a graph has entanglement at most 1 is a problem in NLOGSPACE.

While wondering for a characterization of graphs of entanglement at most 2, we observed that such a question has a clear answer for undirected graphs.To deal with this kind of graphs, we recall that an undirected edge {u, v} is just a pair (u, v), (v, u) of directed edges. We can use the results of [START_REF] Berwanger | Entanglement-a measure for the complexity of directed graphs with applications to logic and games[END_REF] to give characterizations of undirected graphs of entanglement at most 1. To this goal, for n ≥ 0 define the n-star of center x 0 , noted ς n x0 , to be the undirected graph (V, E) where V = { x 0 , a 1 , ..., a n } and E = { {x 0 , a 1 }, ..., {x 0 , a n } }. More generally, say that a graph is a star if it is isomorphic to some ς n x0 . Then we can easily deduce:

Proposition 2. If G is an undirected graph, then E(G) = 0 if and only if E G = ∅, and E(G) ≤ 1 if and only if G is a disjoint union of stars.
To end this section we state a Lemma that later will be used often. We remark that its scope does not restrict to undirected graphs.

Lemma 3. If H is a subgraph of G then E(H) ≤ E(G).
As a matter of fact, Thief can choose an initial vertex from H and then he can restrict his moves to edges of H. In this way he can simulate a winning strategy from E(H, k) to a winning strategy in E(G, k).

Molecules, Collapses, and the Class ζ 2

In this section we introduce a class of graphs and prove that the graphs in this class have entanglement at most 2. It will be the goal of the next sections to prove that these are all the graphs of entanglement at most 2.

Definition 4. A molecule θ ε,n a,b , where ε ∈ { 0, 1 } and n ≥ 0, is the undirected graph (V, E) with V = { a, b, c 1 , ..., c n } and E = { {a, c 1 }, ..., {a, c n }, {b, c 1 }, ..., {b, c n } } , ε = 0, { {a, b}, {a, c 1 }, ..., {a, c n }, {b, c 1 }, ..., {b, c n } } , ε = 1.
The glue points of a molecule θ ε,n a,b are a, b. Its dead points are c 1 , . . . , c n . It is not difficult to prove that molecules have entanglement at most 2.

Definition 5. Let G 1 and G 2 be two undirected graphs with V G1 ∩ V G2 = ∅, let a 1 ∈ V G1 and a 2 ∈ V G2 . The collapse of G 1 and G 2 on vertices a 1 and a 2 , denoted G 1 z a1,a2 G 2 , is the graph G defined as follows:

V G = (V G1 \ { a 1 }) ∪ (V G2 \ { a 2 }) ∪ { z }, where z ∈ V G1 ∪ V G2 , E G = { {x 1 , y 1 } ∈ E G1 | a 1 ∈ { x 1 , y 1 } } ∪ { {x 2 , y 2 } ∈ E G2 | a 2 ∈ { x 2 , y 2 } } ∪ { {x, z} | {x, a 1 } ∈ E G1 or {x, a 2 } ∈ E G2 } .
We remark that is a coproduct in the category of pointed undirected graphs and, for this reason, this operation is commutative and associative up to isomorphism. The graph η, whose set of vertices is a singleton, is a neutral element. As we have observed, a molecule is an undirected graph coming with a distinguished set of vertices, its glue points. Let us call a pair (G, Gl) with Gl ⊆ V G a glue graph. For glue graphs we can define what it means that a collapse is legal.

Definition 6. If G 1 , G 2 are glue graphs, then we say that G 1 z a,b G 2 is a legal collapse if a ∈ Gl G1 and b ∈ Gl G2 . We shall then use the notation G 1 z a,b G 2 and define Gl G1 z a,b G2 = (Gl G1 \ { a }) ∪ (Gl G2 \ { b }) ∪ { z } , so that G 1 z a,b G 2 is a glue graph.
Observe that the graph η can be made into a unit for the legal collapse by letting Gl η = V η . Even if the operation is well defined only after the choice of the two glue points that are going to be collapsed, it should be clear what it means that a family of glue graphs is closed under legal collapses. Definition 7. We let ζ 2 be the least class of glue graphs containing the molecules, the unit η, and closed under legal collapses and graph isomorphisms.

We need to make precise some notation and terminology. Firstly we shall abuse of notation and write

G = H v K to mean that there exist subgraphs H, K of G such that v ∈ Gl G ∩ V H ∩ V K and G is isomorphic to the legal collapse H z v,v K.
Notice that if H and K are distinct from η, then v is an articulation point of G. Second, we shall say that a graph G belongs to ζ 2 to mean that there exists a subset Gl ⊆ V G such that the glue graph (G, Gl) belongs to ζ 2 . We can now state the main result of this section.

Proposition 8. If G belongs to the class ζ 2 , then E(G) ≤ 2.
Proof. Observe that, given a molecule θ ε,n a,b occurring in an algebraic expression for G, we can rearrange the summands of the algebraic expression to write

G = L a θ ε,n a,b b R (1)
where L, R ∈ ζ 2 . A Cops winning strategy in the game E(G, 2) is summarized as follows. If Thief occupies some vertex of the molecule θ ε,n a,b , Cops will place its two cops on a and b, in some order. By doing that, Cops will force Thief to move (i) on the left component L, in which case Cops can reuse the cop on b on L, (ii) on the molecule θ ε,n a,b , in which case Thief will be caught in a dead point of the molecule, (iii) on the right component R, in which case Cops can reuse the cop on a on R.

Cops can recursively use the same strategy in E(L, 2) and E(R, 2). The recursion terminates as soon as in the expression (1) for G we have

L = R = η. ⊓ ⊔
The reader will have noticed similarities between the strategy proposed here and the strategy needed in [START_REF] Berwanger | Entanglement-a measure for the complexity of directed graphs with applications to logic and games[END_REF] to argue that undirected trees have entanglement at most 2. As a matter of fact, graphs in ζ 2 have an underlying tree structure. For a glue graph G, define the derived graph ∂G as follows: its vertices are the glue points of G, and {a, b}

∈ E ∂G if either {a, b} ∈ E G or there exists x ∈ V G \ Gl G such that {a, x}, {x, b} ∈ E G .

Combinatorial Properties

The goal of this section is to setup the tools for the characterization Theorem 16. We deduce some combinatorial properties of undirected graphs of entanglement at most 2. To this goal, let us say that a simple cycle is long it its length is strictly greater than 4, and say otherwise that it is short. Also, let us call a simple cycle of length 3 (resp. 4) a triangle (resp. square).

Proposition 10. An undirected graph G such that E(G) ≤ 2 satisfies the following conditions:

a simple Cycle of G is Short, (CS) a triangle of G has at least one vertex of degree 2, (No-3C) a square of G cannot have two adjacent vertices of degree strictly greater than 2. (No-AC) Condition (No-3C) forbids as subgraphs of G the graphs arising from the scheme on the left of figure 1. These are made up of a triangle and 3 distinct Collapses, with vertices x, y, z that might not be distinct. Condition (No-AC) forbids the scheme on the right of figure 1, made up of a square and two Adjacent Collapses, with vertices x, y that might not be distinct. Let us remark that graphs satisfying (CS), (No-3C), and (No-AC) are House-Hole-Domino free, in the sense of [START_REF] Chepoi | Finding a central vertex in an HHD-free graph[END_REF]. With respect to HDD-free graphs, the requirement is here stronger since for example long cycles are forbidden as subgraphs, not just as induced subgraphs. We shall see with Theorem 16 that these properties completely characterize Let P 0 be the empty graph and, for n ≥ 1, let P n be the path with n vertices and n-1 edges: V Pn = { 0, ..., n-1 } and {i, j} ∈ E Pn iff |i-j| = 1. For n ≥ 3, let C n be the cycle with n vertices and edges:

V Cn = { 0, ..., n -1 } and {i, j} ∈ E Cn iff |i -j| ≡ 1 mod n. Lemma 11. If n ≥ 5 then E(C n ) ≥ 3.
Proof. To describe a winning strategy for Thief in the game E(C n , 2) consider that the removal of one or two vertices from C n transforms such graph into a disjoint union P i + P j with i + j ≥ n -2 ≥ 3: notice in particular that i ≥ 2 or j ≥ 2. In a position of the form (v, C, T hief ) with v ∈ C, Thief moves to a component P i with i ≥ 2. From a position of the form (v, C, T hief ) with v ∈ C, v in some component P i , and i ≥ 2, Thief moves to some other vertex in the same component. This strategy can be iterated infinitely often, showing that Thief will never be caught. Up to a renaming of vertices, such a strategy can be iterated infinitely often, showing that Thief will never be caught. Again, we observe that the strategy does not depend on x, y being distinct.

⊓ ⊔

We end this section by pointing out that

E(C n ) = E(3C) = E(AC) = 3 (n ≥ 5).

Characterization of Entanglement at Most 2

In this section we accomplish the characterization of the class of undirected graphs of entanglement at most 2: we prove that this class coincides with ζ 2 .

The following Lemma is the key observation by which the induction works in the proof of Proposition 15. It is worth, before stating it, to recall the difference between , the collapse of two ordinary undirected graphs, and , the legal collapse of two glue graphs. Lemma 14. Let G be an undirected graph satisfying (No-3C) and

(No-AC). If G = θ ε,n v,b b H and H ∈ ζ 2 , then there is a subset Gl ′ ⊆ V G such that (H, Gl ′ ) is a glue graph in ζ 2 , b ∈ Gl ′ , and moreover G is the result of the legal collapse G = θ ε,n v,b b (H, Gl ′ ). Consequently, G ∈ ζ 2 , with v a glue point of G.
The proof of the Lemma doesn't present difficulties and therefore it omitted. If all the vertices in G have degree less than or equal to 2, then G is a disjoint union of paths and cycles of length at most 4. Clearly such a graph belongs to ζ 2 . Otherwise, let v 0 be a vertex such that deg G (v 0 ) ≥ 3 and consider the connected components G ℓ , ℓ = 1, . . . , h, of the graph G \ { v 0 }. Let G v0 ℓ be the subgraph of G induced by V G ℓ ∪ { v 0 }. We shall show that this graph is of the form

G v0 ℓ = θ ε,m v0,v1 v1 H , (2)
for some ε ∈ { 0, 1 }, m ≥ 0, and a graph

H ∈ ζ 2 . Clearly, if G ℓ is already a connected component of G, then G ℓ ∈ ζ 2 by the inductive hypothesis. We can pick any v 1 ∈ V G ℓ and argue that formula (2) holds with m = ε = 0, H = G ℓ .
Otherwise, let N ℓ = { a 1 , ..., a n }, n ≥ 1, be the set of vertices of G v0 ℓ at distance 1 from v 0 . We claim that either the subgraph of G ℓ induced by N ℓ , noted N G ℓ , is a star or there exists a unique v 1 ∈ G ℓ at distance 1 from N ℓ , and moreover the subgraph of G ℓ induced by N ℓ ∪ { v 1 } is a star. In both cases, a vertex of such a star which is not the center has degree 2 in G.

(i) If E NG ℓ = ∅, then N G ℓ is a star. Let us suppose that {a 1 , a 2 } ∈ E G ℓ . Since G ℓ is connected, if a k ∈ N ℓ \ { a 1 , a 2 }
then there exists a path from a k to both a 1 and a 2 . Condition (CS) implies that either

{a 1 , a k } ∈ E G ℓ , or {a k , a 2 } ∈ E G ℓ . If x 0 ∈ V G ℓ \ { a 2 }
then there cannot be a simple path a k . . . x 0 . . . a 1 otherwise v 0 a k . . . x 0 . . . a 1 a 2 v 0 is a long cycle. Therefore, a simple path from a k to a 1 is of the form a k a 1 or a k a 2 a 1 . By condition (No-3C) it is not the case that

{a k , a 1 }, {a k , a 2 } ∈ E G ℓ , otherwise { v 0 , a 1 , a 2 , a k } is a clique of cardinality 4. Finally, if {a k , a 1 } ∈ E G ℓ and a l ∈ N ℓ \ { a 1 , a 2 , a k }, then {a l , a 1 } ∈ E G ℓ as well, by condition (CS), otherwise v 0 a k a 1 a 2 a l v 0 is a long cycle. Therefore, if |N ℓ | > 2,
then N G ℓ is a star with a prescribed center, which we can assume to be a 1 . Since deg G (v 0 ) ≥ 3, by condition (No-3C) only a 1 among vertices in N ℓ may have degree greater than 2. Otherwise |N ℓ | = 2 and again at most one among a i , i = 1, 2, has deg G (a i ) > 2. Again, we can assume that deg G (a 2 ) = 2. We deduce that the subgraph of G v0 ℓ induced by

{ v 0 } ∪ N ℓ is of the form θ 1,n-1 v0,a1 . (ii) If E NG ℓ = ∅, then we distinguish two cases. If |N ℓ | = 1, then the subgraph of G v0 ℓ induced by { v 0 } ∪ N ℓ is θ 1,0 v0,a1 . Otherwise, if |N ℓ | ≥ 2
, between any two distinct vertices in N ℓ there must exist a path in G ℓ , since G ℓ is connected. By condition (CS), if a i . . . x i,j . . . a j is a simple path from a i to a j with x i,j ∈ V G ℓ \ N ℓ , then {a i , x i,j }, {a j , x i,j } ∈ E G ℓ . Also (CS) implies that, for fixed i, x i,k = x i,j if k = j, otherwise v 0 a k x i,k a i x i,j a j v 0 is a long cycle. We can also assume that x i,j = x j,i , and therefore x i,j = x i,k = x l,k whenever i = j and l = k. Thus we can write x i,j = v 1 for a unique v 1 at distance 2 from v 0 . Since |N ℓ | ≥ 2 and deg G (v 0 ) ≥ 3, condition (No-AC) implies that deg G (a i ) = 2 for i = 1, . . . , n. We have shown that in this case the subgraph of G v0 ℓ induced by

N ℓ ∪ { v 0 , v 1 } is a molecule θ 0,
G = G v0 1 v0 G v0 2 v0 ... v0 G v0 h , to deduce that G ∈ ζ 2 . ⊓ ⊔
We can now state our main achievement.

Theorem 16. For a finite undirected graph G, the following are equivalent:

1. G has entanglement at most 2, 2. G satisfies conditions (CS), (No-3C), (No-AC), 3. G belongs to the class ζ 2 .

As a matter of fact, we have shown in the previous section that 1 implies 2, in this section that 2 implies 3, and in section 3 that 3 implies 1.

A Linear Time Algorithm

In this section we present a linear time algorithm that decides whether an undirected graph G has entanglement at most 2. We would like to thank the anonymous referee for pointing to us the ideas and tools needed to transform the algebraic characterization of Section 3 into a linear time algorithm. Let us recall that, for G

= (V, E) and v ∈ V , v is an articulation point of G iff there exist distinct v 0 , v 1 ∈ V \ { v } such that every path from v 0 to v 1 visits v. Equivalently, v is an articulation point iff the subgraph of G induced by V \ { v } is disconnected. The graph G is biconnected if it does not contain articulation points. A subset of vertices V ′ ⊆ V is biconnected iff the subgraph induced by V ′ is biconnected. A biconnected component of G is biconnected subset C ⊆ V such that if C ⊆ V ′ and V ′ is biconnected then C = V . The superstructure of G is the graph F G defined as follows. Its set of vertices is the disjoint union V FG = A(G) ⊎ C(G), where A(G) = { a ∈ V | a is an articulation point of G } , C(G) = { C ⊆ V | C is a biconnected component of G } ,
and its set of edges is of the form

E FG = { {a, C} | a ∈ A(G), C ∈ C(G),
|C| = |V \ A(G)| + a∈A(G) |{ C ∈ C(G) | a ∈ C }| = |V \ A(G)| + |E FG | = O(|V | + |E|) .
The algorithm ENTANGLEMENT-TWO relies on the following considerations. If a graph G belongs to the class ζ 2 , then it has an algebraic expression explaining how to construct it using molecules as building blocks and legal collapses as operations. We can assume that in this expression the molecule θ 0,1 a,b does not appear, since each such occurrence may be replaced by the collapse θ 1,0 a,x x θ 1,0

x,b . W.r.t. this normalized expression, if G is connected then its articulation points are exactly those glue points v of G that appears in the algebraic expression as subscripts of some legal collapse v ; the molecules are the biconnected components of G.

The algorithm computes the articulation points and the biconnected components of G -that is, its superstructure -and afterwards it checks that each biconnected component together with its articulation points is a molecule. For a biconnected component together with a set of candidate glue points to be a molecule we need of course these candidates to be at most 2. Also, every vertex whose degree in G is not 2 is a candidate glue point. Improving on these observations we arrive at the following characterization. The following Lemma, whose proof depends on considering a tree with back edges arising from a Depth-First-Search on the graph, elucidates the role of the 3rd line of the algorithm.

Fig. 1 .

 1 Fig. 1. The graphs 3C and AC

⊓ ⊔ Lemma 12 .Lemma 13 .

 1213 Let 3C be a graph on the left of figure1. We have E(3C) ≥ 3.Proof. A winning strategy for Thief in the game E(3C, 2) is as follows. By moving on a, b, c, Thief can force Cops to put two cops there, say for example on a and b. Thief can then escape to c and iterate moves on the edge {c, z} to force Cops to move one cop on one end of this edge. From a position of the form (c, C, T hief ) with c ∈ C, Thief moves to a free vertex among a, b. From a position of the form (z, C, T hief ) with c ∈ C Thief moves to c and forces again Cops to occupy two vertices among a, b, c. Up to a renaming of vertices, such a strategy can be iterated infinitely often, showing that Thief will never be caught.Observe that the proof does not depend on x, y, z being distinct. ⊓ ⊔ Let AC be a graph on the right of figure1. We have E(AC) ≥ 3. Proof. By moving on a, b, c, d, Thief can force Cops to put two cops either on a, c or on b, d: let us say a, c. Thief can then escape to b and iterate moves on the edge {b, y} to force Cops to move one cop on one end of this edge. From a position of the form (b, C, T hief ) with b ∈ C, Thief moves to a free vertex among a, c. From a position of the form (y, C, T hief ) with b ∈ C Thief moves to b and forces again Cops to occupy either a, c or b, d.

Proposition 15 .

 15 If G is an undirected graph satisfying (CS), (No-3C), and (No-AC), then G ∈ ζ 2 . Proof. The proof is by induction on |V G |. Clearly the Proposition holds if |V G | = 1, in which case G = η ∈ ζ 2 . Let us suppose the Proposition holds for all graphs H such that |V H | < |V G |.

  and a ∈ C } . It is well known that F G is a forest and that Depth-First-Search techniques may be used to compute the superstructure F G in time O(|V | + |E|), see [18, §23-2]. Observe also that this implies that C∈C(G) |C| = O(|V | + |E|). This relation that may also be derived considering that biconnecetd components do not share common edges, so that |V FG | = O(|V | + |E|) and |E FG | = O(|V | + |E|) since F G is a forest. We have therefore C∈C(G)

1

  ENTANGLEMENT-TWO( G ) 2 // Input an u n d i r e c t e d graph G , a c c e p t i f G ∈ ζ2 3 i f |E| ≥ 3|V | then r e j e c t 4 foreach v ∈ V do deg(v) := |vE| 5 l e t FG = (A(G) ⊎ G(G), EF G ) be t h e s u p e r s t r u c t u r e o f G 6 foreach C ∈ A(G) do 7 i f not IS-MOLECULE( C, { a ∈ A(G) | a ∈ C } ) then r e j e c t 8 accept

Lemma 17 .

 17 Let G = (V, E) be a biconnected graph and D ⊆ V be such that{ v ∈ V | deg(v) = 2 } ⊆ D. Then G is isomorphic to a molecule θ ǫ,n a,b , with D isomorphically sent to a subset of { a, b }, if and only if either (i) |D| = 2 and {x, d} ∈ E for each x ∈ V \ D and d ∈ D or (ii) |D| < 2 and |V | ∈ { 3, 4 }.Therefore the recognition algorithm for a molecule is as follows.

1

  IS-MOLECULE( C, A ) 2 i f |A| > 2 then return f a l s e 3 l e t D = { x ∈ C | deg(x) = 2 } ∪ A 4 i f |D| > 2 then return f a l s e 5 i f |D| < 2 then 6 i f |C| ∈ { 3,4 } then return true 7 e l s e return f a l s e 8 foreach x ∈ C \ D 9 i f D ⊆ xE then return f a l s e 10 return true Let us now argue about time resources of this algorithm.

Fact.

  Algorithm ENTANGLEMENT-TWO(G) runs in time O(|V G |). It is clear that the function IS-MOLECULE runs in time O(|C|), so that the loop (lines 7-8) of ENTANGLEMENT-TWO runs in time O( C∈C(G) |C|) = O(|V | + |E|). Therefore the algorithm requires time O(|V | + |E|).

Lemma 18 .

 18 If a graph (V, E) does not contain a simple cycle C n with n ≥ k, then it has at most (k -2)|V | -1 undirected edges. Line 3 ensures |E G | = O(|V G |) and that the algorithm runs in time O(|V G |).

  The following Proposition is not difficult to prove. Proposition 9. A glue graph G is in ζ 2 if and only if ∂G is a forest, and each x ∈ V G \ Gl G has exactly two neighbors, which moreover are glue points.

  n v0,v1 , with n ≥ 2. Until now we have shown that (2) holds with H a graph of entanglement at most 2. Since for such a graph |V H | < |V G |, the induction hypothesis implies H ∈ ζ 2 . Lemma 14 in turn implies that G v0 ℓ ∈ ζ 2 , with v 0 a glue point of G v0 ℓ . Finally we can use


N Ranc

- D Wagner

Introduction

Sous certaines conditions de température T et de vitesse déformation  • , le phénomène de vieillissement dynamique qui résulte de l'interaction dislocations mobiles -atomes interstitiels ou substitutionnels peut se manifester dans de nombreux alliages [1,2]. Dans une partie de ce domaine (T, • ), il peut apparaître sur la courbe de traction des discontinuités qui portent le nom de phénomène Portevin-Le Chatelier (PLC) et qui résultent de la propagation de bandes de déformation plastique localisée [3,4,5]. L'observation expérimentale de ces bandes est délicate compte tenu de la rapidité du phénomène. Les principales techniques utilisées jusqu'à maintenant sont l'extensométrie résistive, l'extensométrie laser, l'émission acoustique… Lors de la déformation plastique d'un matériau, une partie de l'énergie apportée est convertie en chaleur ce qui se traduit par une élévation de la température du matériau déformé. Ces bandes PLC résultant de la localisation de la déformation plastique sont donc le siège d'une élévation de la température et l'enregistrement de la température à la surface de l'éprouvette au cours de l'essai doit être un moyen de visualiser la propagation de ces bandes. C'est ce qui a été fait au cours de cette étude sur un alliage Al-Cu par pyrométrie infrarouge.

Techniques expérimentales

Le matériau de l'étude est un alliage Al-Cu (4 %) à l'état brut de trempe (après mise en solution à 500°C pendant 30 min). Les essais ont été effectués à la température de 20°C avec une vitesse de déformation constante de 8,3.10 -3 s -1 sur des éprouvettes prismatiques de longueur utile 60 mm peintes en noire. Compte tenu de la gamme de température à mesurer (20 à 40°C), les mesures ont été effectuées par pyrométrie dans le domaine de l'infrarouge (gamme du détecteur MCT : 3,7 à 4,9 m), avec une fréquence d'acquisition de 60Hz et un temps d'ouverture de 1500 s. La résolution spatiale était de 0,4 mm par pixel. 2. Toutes les autres images (excepté l'image 7) montrent la création d'une nouvelle bande qui correspond à une hachure entre deux discontinuités. Le temps entre deux créations est de l'ordre de 50 ms. Ce temps varie au cours de la déformation. On a donc une propagation discontinue régulière de proche en proche des bandes de déformation plastique localisée. Les enregistrements de la température aux points A, B et C montrent une élévation brutale de la température lors de la création d'une bande traduisant une augmentation de la déformation plastique. A chaque point, lorsque la bande a disparu la température décroît légèrement, traduisant une diffusion de la chaleur dans l'éprouvette qui est également visible entre les images 6 et 7 de la figure 2. A part ce phénomène de diffusion, on n'observe aucune évolution de la température entre les bandes et donc pas de déformation plastique supplémentaire en dehors des bandes. Sur ce type d'alliage, la création des bandes au niveau du congé inférieur de l'éprouvette débute dès la fin du domaine d'élasticité (fig. 1). Il n'est pas nécessaire d'atteindre une déformation critique minimum pour obtenir l'effet PLC. Parfois, en fin d'essai, on assiste à un changement d'orientation de la bande par rapport à l'axe de traction. Cela se traduit par la discontinuité (c) sur la courbe . On peut également reporter la vitesse de la bande en fonction de la contrainte, dans ce cas la décroissance de la vitesse est linéaire avec l'augmentation de la contrainte.

Résultats

A partir de l'équation de la chaleur en faisant l'hypothèse d'adiabaticité du phénomène, on trouve une relation entre la variation de température et la variation de déformation plastique :  p  C p  (avec  la masse volumique, C p la capacité calorifique et  le coefficient de Taylor Quiney). L'augmentation de déformation plastique dans une bande déduite de l'augmentation de la température (mesurée à partir de la figure 1) est reportée en fonction de la déformation totale sur la figure 4. L'incrément de déformation plastique dans une bande est d'environ 10% de la déformation totale.

Conclusion

Cette étude, menée sur un alliage Al-Cu brut de trempe sensible au vieillissement dynamique à 20°C, a montré que la technique de pyrométrie infrarouge (jamais utilisée jusqu'à maintenant pour ce phénomène) permet de visualiser la naissance et la propagation des bandes type PLC en relation avec la courbe contrainte-déformation, de quantifier très précisément la vitesse apparente de ces bandes ainsi que l'augmentation de déformation plastique dans ces bandes en relation avec les contraintes et les déformations au cours de l'essai.

Remerciement

Nous remercions Monsieur Bremond de la CEDIP pour le prêt de la caméra infrarouge JADE.

Références

[1] J.E. Baird, Inhomogeneity of Plastic Deformation, ASM, Metals Park, OH, 1973,191. [2] L.P. Kubin, Y.Estrin, J.Phys. III 1, 1991, 929.

[3] P. Lacombe, Matériaux et Techniques, 1985, E5.

[4] L.J. Cuddy, W.C. Leslie, Acta Met.,20,1972, 1157. [5] P.G. Mc Cormick, S. Venkadesan, C.P. Ling, Scripta Met., 29, 1993, 1159.

  de l'éprouvette (A, B, C distants de 15 mm). La courbe - obtenue présente des hachures caractéristiques de l'effet PLC qui s'apparentent à des hachures de type B [4]. Le motif caractéristique est constitué d'une première discontinuité (par exemple en (a)) suivi de hachures régulières (entre (a) et (b)) et se termine à nouveau par une discontinuité plus importante (b). Les thermographies de l'éprouvette ont été enregistrées tout au long de l'essai. La figure 2 représente ces thermographies entre les points repérés (a) et (b) de la figure 1. La mise en relation de ces enregistrements permet de préciser le mécanisme macroscopique. Les discontinuités (type (a) et (b)) correspondent à la création d'une bande au niveau du congé inférieur de l'éprouvette repérées par des flèches sur les images 1 et 25 de la figure

Figure 1 :

 1 Figure 1 : Evolution de la contrainte et de la température

Figure 3 :

 3 Figure 3 : vitesse de propagation des bandes Figure 4 : Incrément de déformation dans les bandes


N Ranc

M.S.P D Wagner

STUDY OF TYPE A TO TYPE B PORTEVIN LE CHATELIER BAND TRANSITION BY INFRARED THERMOGRAPHY

INTRODUCTION

In the dynamic strain aging phenomenon, under certain temperature and strain rate conditions, the plastic strain becomes heterogeneous, and bands of plastic strain of few millimetres of width are created and are propagated along the tested sample. It is the dynamic interaction of mobile dislocations with the solute atoms in insertion or substitution which is at the origin of the phenomenon [1,[START_REF] Estrin | Continuum models for Materials and Microstructure[END_REF]. These bands are known under the name of bands of Portevin Le Chatelier (PLC). For a test at imposed strain rate, they are associated on the tensile curve with repeated serrations resulting from a succession of stress drops. These serrations on the tensile curve can be classified in 3 types depending on the spatiotemporal appearance of these bands. The type C corresponds to a chaotic creation of the bands (discontinuous and not correlated). Each drop of stress on the tensile curve corresponds to the formation of one band. The type B corresponds to the discontinuous but regular creation of the bands (each new band is created just above of the preceding band and so on). Type A, on a macroscopic scale is the continuous propagation of a band occurring on one edge of the specimen and being propagated until the other edge. A type of serration on the tensile curve which is more or less easily identifiable is associated with each type of band (A, B or C). When the strain rate increases (the waiting time of dislocations decreases) or the temperature decreases (mobility of the diffusing species decreases) the localization of the bands evolves from the type C to the type B and then to the type A. In order to study the spatiotemporal evolution of PLC bands, we used in this paper the infrared thermography technique [START_REF] Ranc | [END_REF]4]. Indeed the plastic deformation is accompanied by a dissipation of mechanical work into heat what causes an increase in the temperature. In a first part we will describe the material and the experimental device. In a second part, we will present the results obtained for the bands of the type A and type B. Then we will detail the evolution of the bands parameters according to strain and we will more particularly discuss on the type A -type B transition.

EXPERIMENTAL DEVICE

The material used this study is an aluminium-copper alloy (4% copper) heat treated at 500°C during 30 minutes and then water quenched. Immediately after quench, the copper concentration content in substitutional solid solution is high and this alloy is sensitive to DSA in a temperature range around 20°C. Immediately after quench, tensile tests were carried out on a screw driven machine at the ambient temperature with a strain rate of 1.19 x 10 -2 s -1 . Prismatic specimens of 12mm width, 3mm thickness and 60mm length were machined. The measurement of the temperature field on the specimen surface is carried out with a pyrometry technique. We thus use an infra-red camera. The characteristics of the camera and the experimental methodology are given in [4]. In the performed test, the refresh frequency of the camera is 320Hz what corresponds to a period of 3.125 ms.

RESULTS AND DISCUSSION

During the test, a transition from type A bands towards type B bands appears when the nominal strain increases. The value of the nominal strain when the transition occurs is difficult to evaluate, because in a strain range around this transition we show at the same time bands of type A and bands of type B. Also it is easier to define the strain range of the transition. We can estimate this transition strain range between 5% and 6%. In order to explain this transition from type A to type B, we are more particularly interested in the comparison between time of band formation and time between two band formations. The methodology of the determination of this two characteristics is shown in Fig. 1 (for the type B band). Fig. 2 shows the evolution of the time between two band formations (t mb ) according to the nominal strain when this quantity is measurable (type B band). It is noted that time between two band formations increases with the nominal strain. On Fig. 2, we can show that the evolution of the time between two band formations follows a linear law with the nominal strain in a log-log diagram. Thus, we can write a relation between t mb and the nominal strain ε:

t mb = Dε Ε
with D = 0.15 and E = 0.6068

The standard deviation between the experimental results and the regression is of 0.07s. The increase of the time between two band formations with the nominal strain was already noted by Jiang et al. [5] in an Al4%Cu alloy. More recently Ait-Amokhtar et al. [6] also showed in experiments that this time between two bands (called reloading time) increases when the nominal strain increases. This effect can be explained by the fact that the waiting time of mobile dislocations and thus the time between two band formations increase with the strain. Indeed, we can express the waiting time t w according to elementary plastic deformation noted Ω and the strain rate t w = Ω / ε& . It can be consider that the elementary plastic deformation increase linearly with the strain. An increase in the nominal strain thus results in an increase in the waiting time and thus an increase in the time between two band formations. Fig. 3 shows the evolution of the time of band formation (t f ) according to the nominal strain in the case of the bands of type B. The curve on Fig. 3 highlights a reduction in the time of band formation with the strain. In a log-log diagram (fig.

3), this evolution can be considered as linear. A linear regression enables us to obtain a power law evolution of the time of band formation according to the strain:

t f = Fε G with F = 0.0008s and G = -1.0925 (2)
The values measured in this study are the same order as those measured by Louche et al [7] (the development time of the band is estimated at 10 ms in an alloy Al-4wt.%Mg) and by Tong et al [8] (the development time of the band is estimated between 3ms and 5ms in an alloy Al-2.5wt.%Mg). However no data is available in the literature concerning the evolution of this time of band formation according to the nominal strain. On the Fig. 4, the time between two bands formations t mb and the time of band formation t f are plotted versus ε from equations ( 1) and [START_REF] Estrin | Continuum models for Materials and Microstructure[END_REF]. For one strain value, the two straight lines intersect. On the left hand of the intersection, the time of band formation t f is greater than the time between two bands formations t mb . In this case, it is impossible to distinguish two consecutive band formations and we are in a continuous propagation of the plastic strain front (type A band). From Fig. 4, the intersection is for ε = 4.6%, that is to say of the same order that the experimental value (5 -6%) determined for the transition type A-type B for the test performed for this study.

CONCLUSIONS

In this paper, we studied the Portevin Chatelier bands of type A, B in a Aluminium Copper alloy using the temperature measurement technique by infra-red thermography. We are more particularly interested in the study of the time of band formation and the time between two band formations according to the nominal strain. In particular, we highlighted an increase in the time between two band formations and a reduction in the time of formation with an increase in the nominal strain. We noted that in the case of bands of type B which corresponds to a discontinuous propagation, the time of band formation is lower than the time between two band formations. We also showed that the type A -type B transition from a continuous propagation towards a discontinuous propagation corresponds to the equality between the time of band formation and the time between two band formations.

Fig. 1 -Fig. 2 -Fig. 3 - 4 -

 1234 Fig.1 -Temperature evolution in the center of two consecutive bands


Dip. Emanuela Abbate
email: emanuela.abbate@u-bordeaux.fr

Angelo Iollo
email: angelo.iollo@u-bordeaux.fr

Gabriella Puppo
email: gabriella.puppo@uninsubria.it

A relaxation scheme

Keywords: low Mach flows, relaxation method, compressible flows MSC (2010): 65M08, 65N08, 35Q31

Introduction

In the numerical simulation of fluid flows, the low Mach regime induces severe stiffness and, consequently, stability problems for standard computational techniques. This is due to the fact that the upwind schemes adopted when solving compress-ible flows are not "asymptotic preserving", namely they do not preserve the low Mach number limit behaviour, which tends to incompressible flow [START_REF] Klainerman | Compressible and incompressible fluids[END_REF][START_REF] Klein | Semi-implicit extension of a Godunov-type scheme based on low Mach number asymptotics i: One-dimensional flow[END_REF]. It has been proved in [START_REF] Guillard | On the behaviour of upwind schemes in the low Mach number limit[END_REF] that upwind schemes lead to pressure fluctuations of the order of the Mach number M, while in the continuous case the pressure fluctuations are of order M 2 : this is one of the main reasons why compressible flow solvers perform so poorly in the low Mach number regime.

In this work, the derivation of a scheme for solving low Mach inviscid flows is addressed with a novel implicit relaxation approach. The relaxation method introduced in [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF] is adopted, approximating the original system with a larger one. This new system is linear except for a lower order source term and thanks to linearity, implicit time discretizations can be easily implemented. Therefore, both upwind and centered spatial discretizations can be used without having stability problems. The centered scheme allows to recover the correct limit on the pressure gradients in the low Mach regime. Nevertheless, the upwind discretization is needed in presence of Mach numbers of order one, in order to introduce enough numerical viscosity. Since the adopted spatial discretization is a convex combination of these two, it is able to approximate flows in different regimes and thus the scheme can be seen as an "all-speed" scheme, as the ones proposed in [START_REF] Cordier | An asymptotic-preserving all-speed scheme for the Euler and Navier-Stokes equations[END_REF][START_REF] Degond | All speed scheme for the low Mach number limit of the isentropic Euler equation[END_REF]. Moreover, thanks to the absolute stability of implicit schemes, the CFL is not limited by the acoustic constraint, which becomes extremely demanding in low Mach regimes.

The relaxation method

We briefly revise the relaxation method developed in [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF]. A general hyperbolic system of balance laws has the following structure:

∂ t ψ + ∂ x F (ψ) = Q (ψ) , (1)
where ψ ∈ R n is the vector of the conservative variables, F (ψ) the vector of the fluxes and Q (ψ) a source term. By introducing the relaxation variables vector v ∈ R n , the relaxation system approximating the original system (1) reads:

   ∂ t ψ + ∂ x v = Q (ψ) ∂ t v + A∂ x ψ = 1 ε (F (ψ) -v) , ε > 0, (2)
where A = diag{a i }, i = 1, .., n is a positive diagonal matrix. The small positive parameter ε is called relaxation rate. The right hand side of the second equation is a stiff lower order term. Our motivation in choosing this specific relaxation method relies in the resulting linearity of the advective part. This allows for an easy implementation of implicit schemes: the introduction of modified Riemann solvers is not required, as it is when adopting the Suliciu relaxation approach [START_REF] Chalons | Well-balanced time implicit formulation of relaxation schemes for the Euler equations[END_REF].

In order to ensure the dissipative nature of the relaxation, it is necessary to respect the Liu subcharacteristic condition (for details see [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF])

A -F (ψ) 2 ≥ 0 ∀ψ (3)
when building the relaxation system. By enforcing this condition, the coefficients of the relaxation matrix A are derived in such a way that the characteristic speeds λ i , i = 1, ..n of the original system (1) interlace with those of the relaxation system µ j = ± √ a i , j = 1, ..2n, i = 1, ..n. In our computations, A is built by taking a i = max x λ 2 i . This is the maximum over the domain of the a-priori estimated speed.

Numerical relaxation scheme

System (2) is discretized with finite volumes on a uniform mesh. For 1D problems, the grid spacing is ∆ x = x i+1/2x i-1/2 and the time step ∆t = t n+1t n . Let w n i be the approximate cell average of a quantity w in the cell x i-1/2 , x i+1/2 at time t n and w n i+1/2 the approximate point value of w at an interface x = x i+1/2 and at t = t n . In general, the spatial discretization for system (2) can be written as

     ∂ t ψ i + v i+1/2 -v i-1/2 ∆ x = Q (ψ i ) ∂ t v i + A ψ i+1/2 -ψ i-1/2 ∆ x = 1 ε (F (ψ i ) -v i ) . (4)
This is valid with an accuracy of O ∆ x 2 and for sufficiently accurate reconstructions of the quantities at the interfaces, noting that

F (ψ i ) = F 1 ∆ x x i+1/2 x i-1/2 ψdx = 1 ∆ x x i+1/2 x i-1/2 F (ψ) dx + O ∆ x 2 = F i + O ∆ x 2 .

Spatial discretization

In (4), the interface values have to be computed with a specific scheme. Let u be a generic variable. We define an hybrid discretization in the following way:

u i+1/2 -u i-1/2 ∆ x hyb = f (M loc ) u i+1/2 -u i-1/2 ∆ x upw + (1 -f (M loc )) u i+1/2 -u i-1/2 ∆ x cent , (5)
where the first term defines the spatial discretization through an upwind method and the second through a centered one. M loc is the local Mach number and we choose f (M loc ) = min{1, M loc } in order to have a convex combination. This way the correct numerical viscosity for each regime is recovered. The upwind scheme is derived as in [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF], computing the interface values by using the characteristic variables v ± A 1/2 ψ of system [START_REF] Cordier | An asymptotic-preserving all-speed scheme for the Euler and Navier-Stokes equations[END_REF]. At first order we have:

         v i+1/2 -v i-1/2 ∆ x upw = 1 2∆ x (v i+1 -v i-1 ) - A 1/2 2∆ x ψ i+1 -2ψ i + ψ i-1 ψ i+1/2 -ψ i-1/2 ∆ x upw = 1 2∆ x ψ i+1 -ψ i-1 - A -1/2 2∆ x (v i+1 -2v j + v i-1
) .

(6) For second order approximations, a Van Leer MUSCL scheme is employed. Since in this work we test second order schemes only for the computation of smooth solutions, non-linear flux limiters are not introduced. The centered spatial discretization is second order accurate and reads:

       v i+1/2 -v i-1/2 ∆ x cent = 1 2∆ x (v i+1 -v i-1 )
ψ i+1/2 -ψ i-1/2 ∆ x cent = 1 2∆ x ψ i+1 -ψ i-1 . (7)

Implicit time discretization

To ensure that the centered discretization ( 7) is stable and to avoid the acoustic CFL, we propose a fully implicit relaxation scheme, instead of adopting classic explicit relaxation schemes [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF][START_REF] Pareschi | Implicit-explicit Runge-Kutta schemes and applications to hyperbolic systems with relaxation[END_REF]. The implicit scheme at first order reads:

       ψ n+1 i -ψ n i ∆t + v n+1 i+1/2 -v n+1 i-1/2 ∆ x = Q ψ n+1 i v n+1 i -v n i ∆t + A ψ n+1 i+1/2 -ψ n+1 i-1/2 ∆ x = 1 ε F ψ n+1 i -v n+1 i , (8)
which is a simple backward Euler. For a second order implicit approximation, a BDF (Backward Differentiation Formula) second order accurate is employed.

The implicit non linear part in the source is dealt with applying one iteration of the Newton method, namely the fluxes are approximated with the Taylor expansion

F ψ n+1 = F (ψ n ) + F (ψ n ) ψ n+1 -ψ n , (9)
where F (ψ n ) is the Jacobian of the flux and can be computed analytically. This constitutes a significant simplification with respect to the use of complex solvers that deal with non-linear fluxes inside implicit schemes. When a non-linear source term Q (ψ) is present, it can be treated in the same way. With linearization (9), the derived implicit scheme possesses the following zero relaxation limit ε → 0 +

ψ n+1 i -ψ n i ∆t + F ψ n+1 i+1/2 -F ψ n+1 i-1/2 ∆ x = Q ψ n+1 i ,
which is a consistent and stable discretization of (1). In this framework, the full linear system to be solved reads

MΨ n+1 + NV n+1 = r PΨ n+1 + RV n+1 = s,
where Ψ n+1 and V n+1 are the vectors containing the grid point values of the conservative and of the relaxation variables respectively. In 1D problems, M, N, P and R have tridiagonal sub-blocks for first order discretizations. Linearization (9) only adds terms on the diagonals of the sub-blocks of P, not increasing the computational effort in the inversion algorithms. The scheme is unconditionally stable. The acoustic Courant number is defined as ν ac = µ max ∆t/∆ x and with the proposed implicit scheme it can be taken significantly larger than one. This is very useful in terms of computational time when simulating low Mach flows, since the acoustic waves are extremely fast (for Euler equations µ max ≥ |u + c| from condition (3), u being the flow velocity and c the sound speed). Therefore, the time step ∆t is not excessively limited as it would be with an explicit scheme requiring ν ac < 1 for stability. Moreover, in approximating material waves, a "material CFL condition" can be employed: the material Courant number is defined as ν mat = µ mat ∆t/∆ x with µ mat ≥ |u|. To ensure accuracy on the material waves, the time step is chosen by imposing ν mat ≤ 1. Thus, ∆t is not constrained by the speed of the acoustic waves but only by the speed of the material wave.

Numerical results

The proposed scheme is applied to the simulation of gas and liquid flows, governed by the one dimensional Euler equations with a generalized equation of state. In all simulations we employ ε = 10 -8 . Initial and boundary conditions on the relaxation variables are set to be consistent with the equilibrium state v = F (ψ) [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF].

Steady state example: nozzle flow

We validate the scheme by computing the steady state of a Laval nozzle flow in the quasi-1D approximation. In the general formulation (1), the conservative variables, the fluxes and the source term are:

ψ =   Sρ Sρu SE   , F (ψ) =   Sρu S ρu 2 -p S (E -p) u   , Q (ψ) =   0 p∂ x S 0   ,
where ρ is the density, u is the flow velocity, E = ρu 2 /2+ρe is the total energy (sum of the kinetic part and the internal energy e) and p is the pressure. S = S (x) is the cross sectional area of the nozzle, which is a smooth function of the axial coordinate x. In this approximation, all flow variables depend on only the coordinate x.

The scheme is able to deal with different state laws. In particular, we simulate:

• perfect gas flows, with the state law e = p/ (ρ (γ -1)) (γ = c P /c V is the heat capacity ratio and it is equal to 1.4 for biatomic gases); • stiffened gas flows, with the state law e = p/ (ρ (γ -1)) + p ∞ /ρ, where the p ∞ term models the intermolecular forces. This law describes flows of liquids (the parameters for water are γ = 4.4 and p ∞ = 6.8 • 10 8 Pa).

Three different configurations of the nozzle are simulated: The pressure profiles obtained with the first and second order implicit scheme are shown in Figs. 1(a)-1(b)-1(c) for the three tests and they are compared to the results of the classic explicit-upwind relaxation scheme of [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF]. The comparison shows that for test 1 the two schemes are equivalent. Instead, for low Mach flows (tests 2 and 3) our implicit scheme is more accurate than the explicit one, which gives a solution shifted from the exact one and presents oscillations, due to the wrong numerical viscosity. The implicit scheme computes pressure profiles that are superimposed to the exact solution in all the three cases thanks to discretization [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF]. In Fig. 1(d), the convergence analysis for the implicit scheme is carried out and the correct convergence rates are recovered.

The time step for the implicit scheme is chosen by enforcing ν ac = 100 at first order and ν ac = 40 at second order. Thanks to this constraint, our implicit scheme is computationally less demanding. For example in test 2, a precision of order 2 • 10 -7 is obtained by the first order implicit scheme in 64 s of CPU time and by the explicit in 3464 s.

Material wave simulation: gas tube

We give a numerical illustration of the performances of the scheme for the simulation of material waves, by solving a low Mach perfect gas flow in a tube. The Euler system in the general formulation (1) reads

ψ =   ρ ρu E   , F (ψ) =   ρu ρu 2 -p (E -p) u   , Q (ψ) =   0 0 0   .
Let x d be the discontinuity position, which is in the middle of the tube when t = 0. The Riemann problem initial data are ρ L = ρ R = 1Kg/m 3 , u L = 0m/s, u R = 0.008m/s, p L = 0.4Pa and p R = 0.399Pa. The solution consists in two fast expansion waves and a very slow material wave. On this latter wave we have M 6 • 10 -3 . The results at time t = 0.25s are shown in Fig. 2(a): the wave has moved from x d = 0.5 to x d = 0.501167m, namely, for a grid spacing ∆ x = 10 -3 , it has crossed 1 cell. The length of this tube is 1m. In order to see the material wave move, we run a simulation for long times: at time t = 150s (Fig. 2(b)) the wave has moved from x d = 200 to x d = 200.7m, namely, for a grid spacing ∆ x = 10 -1 , it has crossed 7 cells. The length of this second tube is 400m.

The results obtained using the implicit scheme with ν mat = 0.2 (giving ∆t 2.2 • 10 -2 on the chosen grid) are compared to the ones of the explicit-upwind relaxation scheme of [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF], where instead an acoustic condition has to be enforced (ν ac = 0.4 giving ∆t 5 • 10 -4 ). Due to the material constraint on ∆t, the implicit scheme is of course very diffusive on the acoustic waves. If accuracy on the rarefactions is needed, an acoustic CFL has to be enforced, thus recovering the same precision of the explicit scheme on these waves. Nevertheless, the implicit scheme is able to accurately reproduce and keep the contact wave sharp as it moves to the right,

1. test 1 Fig. 1

 11 Fig.1Nozzle flow: pressure profiles obtained with first and second order implicit schemes and with first order explicit-upwind relaxation scheme of[START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF] (500 grid points). Panel (d): convergence analysis of the implicit scheme for the three tests.

thanks to spatial discretization [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF]. The explicit scheme, instead, is very diffusive on this wave, which is completely smeared after some time (see Fig. 2(b)). Fig. 2 Low Mach gas tube flow: density profiles obtained with the implicit scheme and with the explicit-upwind relaxation scheme of [START_REF] Jin | The relaxation schemes for systems of conservation laws in arbitrary space dimensions[END_REF], both at first order.

Conclusions

We presented a novel implicit relaxation scheme, able to simulate low Mach flows, with first and second order accuracy. The low Mach limit is well reproduced in steady state problems and in the approximation of material waves. The scheme is simple and can be easily adapted to different state laws. In the future, simulation of waves in compressible elastic materials will be exploited.