algorithme pour regrouper tous les cycles Ensemble

I ont un grand nombre de cycles (indiquées par des valeurs numériques, par exemple, 1-2-3-4 correspond à un cycle, avec 4 bords, le bord 1 est {1:2}, bord 2 est {2:3}, bord 3 est {3,4}, bord 4 est {4,1}, et ainsi de suite).algorithme pour regrouper tous les cycles Ensemble

Un cycle est dit être relié à un autre cycle si elles partagent un et un seul bord. Par exemple, disons que j'ai deux cycles 1-2-3-4 et 5-6-7-8, puis il y a deux groupes de cycles car ces deux cycles ne se connectent pas l'un à l'autre. Si j'ai deux cycles 1-2-3-4 et 3-4-5-6, alors je un seul groupe de cycle parce que ces deux cycles partagent le même bord.

La figure ci-dessous devrait être en mesure d'illustrer mon point:

alt text http://lh5.ggpht.com/_SDci0Pf3tzU/SuBhd07xbWI/AAAAAAAAFMs/9OlMhN8uzzQ/s640/mst.jpg

Le R1, R2-R7 ce que j'appelle "cycle". Dans la figure ci-dessus, il n'y a qu'un seul groupe de cycles englobant tous les R1 à R7.

Quelle est la façon la plus efficace de trouver tous les groupes de cycle?

Source

2010-04-03 Graviton

Comment votre entrée donné? Comme dans vos exemples ou est-ce qu'on vous donne un graphique ou quelque chose comme ça? – IVlad

Cette question peut être mieux adaptée à Math Overflow. –

Peut-être devriez-vous expliquer ce que vous essayez d'accomplir, ce qui pourrait donner une idée de la raison pour laquelle vous l'appelez «cycles» et pourquoi il a «bords», et ce que tout cela signifie. – Guffa

Trouvez tous les cycles dans le graphique et étiquetez-les par exemple A, B, C, etc. Maintenant, créez un nouveau graphique où chaque cycle trouvé dans le graphique est converti en un seul nœud dans le nouveau graphique. Joignez les nœuds avec un bord dans le nouveau graphique si les cycles correspondants sont "connectés" dans l'ancien graphique, en utilisant votre (plutôt inhabituel) définition de connecté.

Le nombre de « groupes de cycle » est alors le nombre de connected components dans le nouveau graphique.

Source

2010-04-03 12:57:18

@Merci Marc, mais y a-t-il moyen de récupérer tous les cycles à l'intérieur de chaque groupe de cycle? – Graviton

@Mark, aussi je pose la question sur la façon de dire si les cycles sont connectés, mais dans votre réponse, vous dites que je dois rejoindre les nœuds, peut être plus explicitement à ce sujet? – Graviton

@Ngu: Je laisserai les cycles de détection à quelqu'un d'autre. Pour déterminer si deux cycles sont connectés, comptez le nombre d'arêtes qu'ils partagent. Une fois que vous avez détecté les cycles, vous pouvez créer un nouveau graphique, G '. Dans votre exemple, G 'contiendrait 7 nœuds, un pour chaque cycle que vous avez détecté. Appelez ces nouveaux noeuds R1, R2, ..., R7. Si deux cycles sont connectés, créez un bord entre eux dans G '. R1 devrait avoir un bord à R6 et R7. R2 devrait avoir un avantage sur R3 et R7, etc ... Compter les composants connectés de ce graphique en utilisant n'importe quel algorithme standard de Wikipedia - la réponse est 1. –

Je suis assez sûr que ce n'est pas la façon la plus efficace, mais ce serait ma première tentative:

bords Premier échange avec des sommets: Donc, pour vos cycles par exemple 1-2-3-4, 3-4-5-6 et 5-6-7-8, vous « ll besoin:

"12" => "A" 
"23" => "B" 
"34" => "C" 
"45" => "D" 
"56" => "E" 
"67" => "F" 
"78" => "G" 
"41" => "H" 
"63" => "I" 
"85" => "J"

Cela vous donne jusqu'à (v * (v-1))/2 sommets, mais bien - il peut encore être assez bon pour un algorithme O (v^2).

ensuite représenter les cycles comme bitfields: "1-2-3-4" devient ABCH

ABCDEFGHIJ 
1110000100

et "3-4-5-6" devient CDEI

ABCDEFGHIJ 
0011100010

Alors ils ont exactement un point commun, ce qui signifie que dans le graphe original, ils avaient exactement un point commun. Cela peut être vérifié soit bit par bit avec O (v^2), soit avec recherche binaire (premier contrôle par ANDing, s'ils ont un bit en commun, puis contrôle AND sur la première moitié des bits etc.)

Source

2010-04-03 12:40:44

Ne pensez pas que votre solution fonctionne, et si deux cycles qui ne se connectent pas directement ne font pas encore partie du même groupe de cycle? – Graviton

@Ngu: Mon intention était de tester deux cycles en premier, et de les combiner en un, s'ils sont connectés (la combinaison peut être faite facilement par une opération OU). Puis continuez avec le prochain cycle. J'espère comprendre le regroupement correctement, car il est utilisé ici! –

Si vous souhaitez améliorer les performances, vous pouvez également essayer de tester trois ou quatre cycles à la fois en les associant (en fonction de la probabilité que les cycles soient dans un groupe, vous pouvez modifier les performances de cette manière). Ensuite, "descendez" vers des paires de cycles seulement, si une correspondance s'est produite. Il peut même être possible de commencer par ET en effectuant la moitié des cycles et en «rognant» récursivement ... –

algorithme pour regrouper tous les cycles Ensemble

Répondre

Questions connexes