Subversion Repositories wimsdev

Rev

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