Simplification de graphe/treillis

Question

Je travaille sur la structure de données pour l'algorithme de coupe de graphe. Le problème est de faire des coupes différentes sur les chemins les plus courts. J'ai fait une structure de données pour laquelle je ne suis pas sûr des propriétés.

entrée est dirigé graphique de chemins les plus courts, qui est treillis borné, partiellement ordonné réglé avec minimum et maximum de l'élément.

Définir noeud suivant N (n) de noeud n comme un ensemble de noeuds pour lesquels un b b < et il n'y a pas c avec un < c < b. Similaire définir noeud précédent P (n). Étendre les définitions sur les ensembles, union N (S) de N (n) pour n dans S, similaire pour P (S).

Il est facile de faire différentes coupes sur la liste de l'ensemble des nœuds L, N (L), N (N (L)), ... où pour chaque paire voisine d'ensembles A, N (A) = B estime qu'il n'y a pas de cloisons:

A = A_1 union A_2 
B = B_1 union B_2 
with B_i = N(A_i), A_i = P(B_i) for i=1,2. 

avec cette propriété de créer une nouvelle maille avec la cartographie:

• sous-réseau à un noeud
• si cloison supérieure se trouve que de créer des bords (partition nombre de cardinalité).

En simple, algorithme de réseau -> cartographie du réseau est:

A = {minimum node} 
new_node = [A] 
1: 
while A, N(A) don't have partitions 
    append N(A) to new_node 
    A = N(A) 
for each partition $B_i$ 
    last_new_node = new_node 
    create new_node = [B_i] 
    create edge last_new_node to new_node 
    go to 1 
At the end fix maximum node in new lattice if needed 

Cet algorithme peut être appelé à plusieurs reprises sur les nouveaux réseaux. Je suis préoccupé par:

• Existe-t-il une garantie pour atteindre le réseau à un seul nœud?
• Y at-il mesure du nombre d'itérations pour atteindre un réseau nœud? Il me semble que cette limite est le diamètre du graphe d'entrée.

J'apprécie lien vers une structure de données similaire.

Tnx

Contexte:

J'ai eu une idée d'utiliser problème d'interdiction du réseau de débit maximal dans des choses que je travaillais. Je pensais à la version vertex interdiction où un certain nombre de sommets peuvent être retirés du réseau pour minimiser le débit maximal. Le réseau sur lequel je travaillais était un graphe orienté planaire très régulier (plan divisé en hexagones, chaque sommet est relié à 6 sommets). Je voulais couper (interdire) seulement les chemins les plus courts de source à sink. Pour que je simplification du graphe orienté, bord (a,b) est graphique simplifiée si elle est sur le chemin le plus court de a à sink. Si le poids de la bordure est positif, le graphe orienté simplifié est un treillis. C'est ce que j'ai appelé "graphe orienté des chemins les plus courts".

Je voulais avoir des coupes de sommets qui sont agréables (parallèles, propagation, ...), ce qui est plus facile sur treillis (très structuré).

coupes indigènes sont « vagues », par exemple une belle coupe C produit également N(C) ce qui est agréable.Pour cette raison j'ai essayé de simplifier le treillis avec les opérations décrites ci-dessus. J'ai essayé de décrire 2 sous - ensembles de sommets qui sont intéressants pour les coupes et utilisés dans la cartographie: - ensemble de nœuds ondulatoire - parallèle. Si C est une onde, N(C) en est une autre. - rayure - série d'ondes sans intersection avec d'autres rayures. C, N(C), N(N(C)).

B1--C1--D1 ... 
/\/\/
A X X 
\/\/\ 
    B2--C2--D2 

Waves: {A}, {B1,B2}, {C1,C2}, {D1,D2} 
Stripe is made of these 4 waves. 

Mappage de la bande du réseau initial au noeud du nouveau réseau. Les nœuds dans un nouveau réseau sont connectés s'ils partagent une onde. La direction du bord est de la bande qui partagent la dernière vague à la bande qui partagent la première vague. Comme la cartographie produit un nouveau réseau avec les mêmes propriétés, la procédure peut être répétée jusqu'à ce qu'il y ait un réseau avec un seul nœud. Cela peut être démontré parce que le diamètre du réseau est plus petit, au moins pour 1, à chaque itération. En effet, les noeuds minimaux M et N(M) sont dans la même bande, ce qui réduit le diamètre du treillis. Maintenant, effectuer ou rechercher des coupes est une tâche récursive, commencer par un treillis avant le dernier avec un seul noeud, et faire une coupe sur une onde entière ou sur des ondes voisines en escalier. Pour les nœuds coupés, prenez le sous-réseau qui y est mappé et faites une coupe sur ce sous-réseau. La même chose est faite jusqu'à atteindre le treillis initial.

Cette structure est en quelque sorte sur la compression en treillis. Je pense qu'il peut être utilisé pour la recherche de coupes dynamiques en treillis.

Dans mon cas, je ne l'utilise pas depuis d'autres restrictions de projet. J'ai résolu le problème initial très simple avec seulement quelques lignes de code, mais je ne m'étais pas rendu compte que ça pouvait être fait comme ça auparavant :-)

Answer 1

Y at-il une garantie pour atteindre un réseau à un nœud?

Si je comprends bien votre pseudo, non: il porte un ordre -node linéaire n à un ordre -node linéaire n.

Je décrirais votre code comme acceptant une commande partielle et trouvant un series-parallel partial order dans lequel il a une intégration raisonnablement "fidèle".

Si vous êtes simplement intéressé par trouver des débits max/min dans les graphiques planaires, il y a un O(n log n) algorithm pour cela.