Graphe
prog_amateur
Messages postés
9
Date d'inscription
lundi 18 avril 2005
Statut
Membre
Dernière intervention
19 avril 2006
-
6 avril 2006 à 13:17
mouhouche2006 Messages postés 1 Date d'inscription vendredi 28 avril 2006 Statut Membre Dernière intervention 28 avril 2006 - 28 avril 2006 à 18:58
mouhouche2006 Messages postés 1 Date d'inscription vendredi 28 avril 2006 Statut Membre Dernière intervention 28 avril 2006 - 28 avril 2006 à 18:58
2 réponses
Pamaury
Messages postés
341
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
17 juin 2008
3
6 avril 2006 à 22:39
6 avril 2006 à 22:39
"On peut en fait montrer qu'un graphe dont les noeuds sont tous
connectés à un nombre pair (et non nul) d'arcs dispose toujours d'un
circuit Eulérien."
Donc tu parcourt la liste de tes noeuds et si le nombres d'arcs connecté à ce noeud est non nul et est pair, et s'il y en a un seul qui désobeit à cette loi le graphe n'est pas eulérien
code(C):
int eulerian=1;
int cur_node;
for(cur_node=0;cur_node<nb_nodes;cur_node++)
if(nb_adj[cur_node]==0 || (nb_adj[cur_node]&1))
{
eulerian=0;
break;
}
Et voilà
A m a u r y
connectés à un nombre pair (et non nul) d'arcs dispose toujours d'un
circuit Eulérien."
Donc tu parcourt la liste de tes noeuds et si le nombres d'arcs connecté à ce noeud est non nul et est pair, et s'il y en a un seul qui désobeit à cette loi le graphe n'est pas eulérien
code(C):
int eulerian=1;
int cur_node;
for(cur_node=0;cur_node<nb_nodes;cur_node++)
if(nb_adj[cur_node]==0 || (nb_adj[cur_node]&1))
{
eulerian=0;
break;
}
Et voilà
A m a u r y
mouhouche2006
Messages postés
1
Date d'inscription
vendredi 28 avril 2006
Statut
Membre
Dernière intervention
28 avril 2006
28 avril 2006 à 18:58
28 avril 2006 à 18:58
salam: g un tout petit probleme , si vous pouvez me donné un algo qui donne le nombre de chemins possibles qui passe par tous les sommets et qui passe une seule fois par ces sommets ,je vous serais vraiment reconnaissant