Découverte d'un cycle/circuit eulérien

% Rappel :
% Un graphe admet un cycle eulérien
% si et seulement si il est connexe et si
% chacun de ses sommets est de degré pair
function c = cycle_eulerien(G)
c = [];
if(connexe(G) && eulerien(G))
    s = alea(size(G,1)); % Part d'un sommet au hasard
    [G s c] = cycle(G, s, c);
end
end
 
function [G s c] = cycle(G, s, c)
c = [c s];
if(~isole(G,s))
    v = voisin(G,s);
    t = v(alea(length(v)));
    % L'arrête a été utilisée, donc on la supprime
    G(s,t) = 0;
    G(t,s) = 0;
    % On avance dans le graphe
    [G t c] = cycle(G, t, c);
end
 
end
 
function c = connexe(G)
c = (size(tarjan(G),1) == 1);
end
 
function e = eulerien(G)
e = pair(sum(sum(G,1)+sum(G,2)'));
end
 
function zs = alea(n)
aux=randperm(n);
zs=aux(1);
end
 
function test_isole = isole(G,s)
test_isole = degre(G,s) == 0
end
 
function d=degre(G,s)
d = sum(G(s,:));
end
 
function V = voisin(G,s)
V = find(G(s,:)==1);
end
 
function p = pair(n)
p = mod(n,2) == 0;
end