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 | };\ |