Rev 13587 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
18392 | bpr | 1 | !!deprecated |
13103 | bpr | 2 | pari_header=est_connexe(a)=my(n=#a,b=(1.+a)^(n-1));for(x=1,n,if(b[1,x]==0,return(0)));1\ |
3 | /* graphe_connexe */\ |
||
4 | graphe_connexe(n)={\ |
||
5 | my(a=matrix(n,n),i,j);\ |
||
6 | while(!est_connexe(a),i=1+random(n);j=1+random(n);if(i!=j,a[i,j]=a[j,i]=1));\ |
||
7 | a\ |
||
8 | };\ |
||
9 | \ |
||
10 | /* M est la matrice d'un graphe connexe */\ |
||
11 | graphe_eulerien(M)={\ |
||
12 | my(x,y,z,a=M,n=#a);\ |
||
13 | my(impdeg=vector(n,i,sum(j=1,n,a[i,j])%2));\ |
||
14 | while (sum(i=1,n,impdeg[i]),[x,y]=select(x->x,impdeg,1);\ |
||
15 | if (a[x,y],\ |
||
16 | z=1+(x==1)+(y==2);\ |
||
17 | if(a[x,z] && a[y,z], a[x,y]=a[y,x]=0,\ |
||
18 | a[x,z]=a[z,x]=1-a[x,z];a[y,z]=a[z,y]=1-a[y,z]),\ |
||
19 | a[x,y]=a[y,x]=1);\ |
||
20 | impdeg[x]=impdeg[y]=0\ |
||
21 | );\ |
||
22 | a\ |
||
23 | };\ |
||
24 | \ |
||
25 | est_eulerien(a)=est_connexe(a)&&!vector(#a,i,sum(j=1,#a,a[i,j])%2)\ |
||
26 | \ |
||
27 | /* a est la matrice d'un graphe eulerien trouve un cycle eulerien sur a */\ |
||
28 | \ |
||
29 | cycle_eulerien(a)={\ |
||
30 | my(n=#a,deg=vector(n,i,sum(j=1,n,a[i,j])),m=sum(i=1,n,deg[i])/2);\ |
||
31 | my(cdeg=vector(n),cyc=vector(m+1),c,x,x0,nb);\ |
||
32 | cyc[1]=nb=1;\ |
||
33 | while(nb <= m,\ |
||
34 | [c]=select(x->x&&cdeg[x]<deg[x],cyc,1);\ |
||
35 | x0 = x = cyc[c];\ |
||
36 | until (x==x0,\ |
||
37 | nb++; cdeg[x]++; y = 1; while (!a[x,y] || deg[y]==cdeg[y], y++);\ |
||
38 | cdeg[y]++; forstep (i=nb,c+1,-1,cyc[i]=cyc[i-1]);\ |
||
39 | a[x,y]--;a[y,x]--;\ |
||
40 | cyc[c]=y; x = y);\ |
||
41 | );\ |
||
42 | cyc\ |
||
43 | };\ |