Recherche locale dans un graphe
Pour mon projet, je veux un code en Qtcreator pour le deplacement des sommets dans les deux parties de ma coupe. Bref savoir déplacer un noeud d’un côté vers l’autre dans la coupe G=(V1,V2) où V1 et V2 sont deux classes de ma coupe.
Et voici le mode que j'ai proposé:
Dans mon réseau G=(V,E), les m arcs qui nous intéressent sont ceux qui ont une extrémité dans la classe 1 et l’autre dans la classe 2 ,avec m le nombre d'arcs à minimiser .
La coupe G=(V1,V2) est telle que n1 soit le nombre de sommets de V1 et n2 le nombre de sommets de V2.
Je peux ajouter que tout sommet appartient à V1 ou V2. Par exemple, Je peux dire que v1 = 1 si le sommet 1 appartient à V1, et 0 s’il appartient à V2, de sorte que |V1| + |V2| = n, avec |V|= n, le nombre total de sommets du graphe
Ainsi, quand on déplaces un noeud de la classe 1 vers la classe 2, n1 diminue de 1 alors que n2 augmente de 1. Pour ce qui est de m , ça dépend de combien de voisins du noeud, sont dans la classe 1 et combien sont dans la classe 2.
J'attends votre bonne volonté!
