http://www.saphir-control.fr/

Graphes et réseaux avec Scilab, la boîte à outils Metanet
Première partie

Claude Gomez   Maurice Goursat

• les réseaux dits de service : eau, gaz, électricité et téléphone ;
• les réseaux de transport auxquels nous sommes de plus en plus sensibles et qui nous causent des soucis quotidiens. En effet, qui n'a pas été pris dans un embouteillage, particulièrement en Île de France ?

1   Euler se promène

---

Figure 1: La ville de Koenigsberg

---

metanet()

---

Figure 2: La fenêtre Metanet avec le graphe du pont

---

g=load_graph("pont");

function ar=genar(n)
global ar l;
fact=1; for i=1:n, fact=fact*i; end;
ar=zeros(fact,n); l=1;
ar(1,:)=1:n; ref=1:n;
genar1(n,1,ref);

function genar1(n,m,ref)
global ar l;
if size(ref,"*")<>0 then
  for i=1:size(ref,"*")
    ar(l:$,m)=ref(i);
    ref2=ref; ref2(i)=[];
    genar1(n,m+1,ref2);
  end
else
  l=l+1; 
end;

-->getf("genar.sci")
 
-->ar=genar(7);
 
-->nsol=0; sol=zeros(1,7);
 
-->for i=1:size(ar,"r")
-->  p=ar(i,:);
-->  ns=path_2_nodes(p,g); // transforme un chemin en sommets
-->  if ns <> [] then nsol=nsol+1; sol(nsol,:)=p; end;
-->end
 
-->nsol
 nsol  =
    0.  

---

Figure 3: Les enveloppes

---

-->getf("genar.sci")
 
-->g=load_graph("enveloppe");
 
-->ar=genar(8);
 
-->nsol=0; sol=zeros(1,8);
 
-->for i=1:size(ar,"r")
-->  p=ar(i,:);
-->  ns=path_2_nodes(p,g);
-->  if ns <> [] then nsol=nsol+1; sol(nsol,:)=p; end;
-->end
 
-->nsol
 nsol  =
    88.  

-->sol(33,:) // suite des aretes
 ans  =
!   2.    6.    5.    1.    7.    4.    3.    8. !

-->path_2_nodes(ans,g) // suite des sommets
 ans  =
!   2.    3.    5.    1.    2.    5.    4.    3.    1. !

2   Les entrailles de Metanet

2.1   Qu'est-ce qu'un graphe ?

2.2   La graph-list

name

nom du graphe (une chaîne de caractères) ;

directed

flag qui vaut 1 si le graphe est orienté ou 0 sinon ;

node_number

nombre de sommets ;

tail

vecteur ligne des numéros des sommets de queue pour chaque arc ;

head

vecteur ligne des numéros des sommets de tête pour chaque arc ;

---

Figure 4: Un petit graphe orienté

---

g=make_graph("foo",1,4,[1 1 2 3],[2 3 1 3]);

show_graph(g)

g("node_x")=[42 108 176 162];
g("node_y")=[36 134 36 93];

2.3   Comment représenter un graphe ?

• lp est le tableau des pointeurs, de taille n+1 ;
• ls est le tableau des sommets, de taille m ;
• la est le tableau des arcs, de taille m.

-->g=make_graph("foo",1,4,[1 1 2 3],[2 3 1 3]);
 
-->[lp,la,ls]=adj_lists(g)
 ls  = 
!   2.    3.    1.    3. !
 la  =
!   1.    2.    3.    4. !
 lp  =
!   1.    3.    4.    5.    5. !

3   Jouer avec les graphes

3.1   Distinguer les sommets de degré impair

-->g=load_graph("enveloppe");
 
-->show_graph(g);

-->n=0;
 
-->for i=1:node_number(g)
-->  d=size(find(g('tail')==i | g('head')==i),"c");
-->  if modulo(d,2) <> 0 then n=n+1; ns(1,n)=i; end;
-->end;

-->ns
 ns  = 
!   1.    2. !
 
-->show_nodes(ns)

3.2   Circuit hamiltonien

g=load_graph("hamilton");
cir=hamilton(g);

edgecolor=ones(1,arc_number(g)); edgecolor(cir)=11*ones(cir);
g("edge_color")=edgecolor;
show_graph(g)

---

Figure 5: Circuit hamiltonien

---

3.3   Autres jeux de base

• déterminer les composantes connexes ou fortement connexes ;
• chercher des cycles, des circuits, calculer des bases de cycles ;
• chercher des plus courts chemins ;
• calculer la fermeture transitive ;
• déterminer le couplage maximum ;
• déterminer une clique maximale ;
• déterminer les points d'articulation ;
• déterminer le centre, le diamètre ;
• trouver un arbre de poids minimum ;
• etc.

4   Conclusion

Contacts

This document was translated from L^AT_EX by H^EV^EA.