Algorithme pour trouver le diamètre d'un arbre en utilisant BFS / DFS. Pourquoi ça marche?

28

Ce lien fournit un algorithme pour trouver le diamètre d'un arbre non orienté à l' aide de BFS / DFS . Résumant:

Exécutez BFS sur tous les nœuds du graphique, en vous souvenant du nœud que vous avez découvert en dernier. Exécutez BFS à partir de u en vous souvenant du nœud v découvert en dernier. d (u, v) est le diamètre de l'arbre.

Pourquoi ça marche?

La page 2 de ceci fournit un raisonnement, mais c'est déroutant. Je cite la partie initiale de la preuve:

Exécutez BFS sur tous les nœuds du graphique, en vous souvenant du nœud que vous avez découvert en dernier. Exécutez BFS à partir de u en vous souvenant du nœud v découvert en dernier. d (u, v) est le diamètre de l'arbre.

Exactitude: Soit a et b deux nœuds quelconques tels que d (a, b) soit le diamètre de l'arbre. Il existe un chemin unique de a à b. Soit t le premier nœud sur ce chemin découvert par BFS. Si les chemins de s à u et de a à b ne partagent pas de bords, alors le chemin de t à u inclut s. Alorsp1p2

d(t,u)d(s,u)

d(t,u)d(s,a)

.... (plus d'inégalités suivent ..)

Les inégalités n'ont pas de sens pour moi.

curryage
la source
Je ne trouve pas la citation dans la question liée.
Raphael
1
Essayez de remplacer «ne pas partager les bords» par «ne pas partager les sommets» dans la solution.
Yuval Filmus
Vous utilisez uniquement BFS, pas DFS.
Vignette

Réponses:

11

Toutes les parties de la preuve de la revendication reposent sur 2 propriétés cruciales des arbres aux bords non orientés:

  • 1-connectivité (c'est-à-dire qu'entre 2 nœuds dans un arbre, il y a exactement un chemin)
  • n'importe quel nœud peut servir de racine de l'arbre.

Choisissez un nœud d'arbre arbitraire . Supposons que u , v V ( G ) sont des nœuds avec d ( u , v ) = d i a m ( G ) . Supposons en outre que l'algorithme trouve un nœud x commençant par s en premier, un nœud y commençant par x ensuite. wlog d ( s , u ) d ( s , v ) . Notez quesu,vV(G)d(u,v)=diam(G)xsyxd(s,u)d(s,v) doit tenir, à moins que la première étape de l'algorithme ne se termine pas à x . Nous verrons que d ( x , y ) = d ( u , v ) .d(s,x)d(s,y)xd(x,y)=d(u,v)

La configuration la plus générale de tous les nœuds impliqués peut être vue dans les pseudo-graphiques suivants (éventuellement ou s = z x y ou les deux):s=zuvs=zxy

(u)                                            (x)
  \                                            /
   \                                          /
    \                                        /
     ( z_uv )---------( s )----------( z_xy )
    /                                        \
   /                                          \
  /                                            \
(v)                                            (y)

nous savons que:

  1. . sinon d ( u , v ) < d i a m ( G ) contredisant l'hypothèse.(zuv,y)(zuv,v)(u,v)<jeunem(g)
  2. . sinon d ( u , v ) < d i a m ( G ) contredisant l'hypothèse.d(zuv,X)(zuv,u)(u,v)<jeunem(g)
  3. , sinon l'étape 1 de l'algorithme ne se serait pas arrêtée à x .(s,zXy)+(zXy,X)(s,zuv)+(zuv,u)X
  4. , sinon l'étape 2 de l'algorithme ne se serait pas arrêtée à y .d(zxy,y)d(v,zuv)+d(zuv,zxy)y

1) et 2) impliquent .d(u,v)=d(zuv,v)+d(zuv,u)d(zuv,x)+d(zuv,y)=d(x,y)+2d(zuv,zxy)d(x,y)

3) et 4) impliquent d(zxy,y)+d(s,zxy)+d(zxy,x)d(s,zuv)+d(zuv,u)+d(v,zuv)+d(zuv,zxy) équivalent à .d(x,y)=d(zxy,y)+d(zxy,x)2d(s,zuv)+d(v,zuv)+d(u,zuv)d(u,v)

donc .d(u,v)=d(x,y)

les épreuves analogiques tiennent pour les configurations alternatives

                 (u)                          (x)
                   \                          /
                    \                        /
                     \                      /
     ( s )---------( z_uv )----------( z_xy )
                     /                      \
                    /                        \
                   /                          \
                 (v)                          (y)

et

                          (x)        (u)  
                          /            \  
                         /              \ 
                        /                \
     ( s )---------( z_xy )----------( z_uv )
                        \                /          
                         \              /           
                          \            /            
                          (y)        (v)            

ce sont toutes des configurations possibles. en particulier, raison du résultat de l'étape 1 de l'algorithme et y p a t h ( x , u ) , y p a t h ( x , v ) en raison de l'étape 2.xpath(s,u),xpath(s,v)ypath(x,u),ypath(x,v)

trou noir
la source
(1) Concernant le premier graphique, le chemin de s à x ne devrait-il pas toujours contenir les sommets u et v dans un certain ordre car ils sont présents sur l'arbre généré par BFS? (2) Pourriez-vous préciser comment les inégalités sont obtenues? (3) Étant donné que le BFS à partir de s et celui à partir de x contiennent u, v quelque part sur le chemin, je pense que le graphique devrait être comme indiqué dans le lien imgur.com/jQ94erY . Comment le raisonnement que vous avez fourni s'applique-t-il ici?
curryage
@curryage notez que l'arbre est donné et n'est pas construit par les bfs! réponses spécifiques: annonce 1) non. imaginez un raffinement de l'arbre dans le graphique (1) en ajoutant arbitrairement plusieurs nœuds sur le bord et exactement 1 nœud sur le bord ( z x y , x ) . la première étape bfs se terminera alors à x. ad 2) quelles inégalités ne sont pas claires? nous supposons toujours que ( u , v ) est un chemin de la longueur du diamètre du graphique d i a g ( G )(s,zxy)(zxy,x)(u,v)diag(G). ceci est bien défini car G est 1-connecté. ad 3) non: 3.1 il y a plus d'un chemin entre 2 nœuds différents de , donc le graphique n'est pas un arbre. ...(s,y)
collapsar
@curryage ... 3,2 ; cela est impossible car d ( u , v ) = d i a m ( G ) par hypothèse et le diamètre d'un graphique est la distance minimale maximale entre deux nœuds quelconques. dans le cas d'un arbre, il y a exactement 1 chemin entre 2 nœuds, de sorte que la définition se réduit à «distance maximale entre deux nœuds». d(x,y)>d(u,v)d(u,v)=diam(G)
collapsar
9

L'intuition derrière est très facile à comprendre. Supposons que je dois trouver le chemin le plus long qui existe entre deux nœuds dans l'arbre donné.

Après avoir dessiné quelques diagrammes, nous pouvons observer que le chemin le plus long se produira toujours entre deux nœuds feuilles (nœuds ayant un seul bord lié). Cela peut également être prouvé par la contradiction que si le chemin le plus long se situe entre deux nœuds et que l'un des deux nœuds ou les deux ne sont pas un nœud feuille, nous pouvons étendre le chemin pour obtenir un chemin plus long.

Donc, une façon consiste à vérifier d'abord quels nœuds sont des nœuds feuilles, puis de démarrer BFS à partir d'un des nœuds feuilles pour obtenir le nœud le plus éloigné.

Au lieu de trouver d'abord quels nœuds sont des nœuds feuilles, nous démarrons BFS à partir d'un nœud aléatoire et voyons ensuite quel nœud en est le plus éloigné. Soit le nœud le plus éloigné x. Il est clair que x est un nœud feuille. Maintenant, si nous démarrons BFS à partir de x et vérifions le nœud le plus éloigné, nous obtiendrons notre réponse.

Mais quelle est la garantie que x sera le point final d'un chemin maximum?

Voyons par un exemple: -

       1   
    / /\ \
   6 2  4 8
         \ \
          5 9
           \
            7

Supposons que j'ai commencé mon BFS à partir de 6. Le nœud à la distance maximale de 6 est le nœud 7. En utilisant BFS, nous pouvons obtenir ce nœud. Maintenant, nous observons BFS à partir du nœud 7 pour obtenir le nœud 9 à la distance maximale. Le chemin du nœud 7 au nœud 9 est clairement le chemin le plus long.

Et si BFS qui partait du nœud 6 donnait 2 comme nœud à la distance maximale. Ensuite, lorsque nous passerons de 2 à BFS, nous obtiendrons 7 comme nœud à la distance maximale et le chemin le plus long sera alors 2-> 1-> 4-> 5-> 7 avec la longueur 4. Mais la longueur de chemin la plus longue réelle est 5. Cela ne peut pas se produire parce que BFS du nœud 6 ne donnera jamais le nœud 2 comme nœud à la distance maximale.

J'espère que ça t'as aidé.

MayankPratap
la source
1
c'est une explication simple et claire! merci :)
anekix
4

Voici une preuve qui suit de plus près l'ensemble de solutions MIT lié dans la question d'origine. Pour plus de clarté, j'utiliserai la même notation qu'ils utilisent afin que la comparaison puisse être faite plus facilement.

Supposons que nous ayons deux sommets et b tels que la distance entre a et b sur le chemin p ( a , b ) soit un diamètre, par exemple la distance d ( a , b ) est la distance maximale possible entre deux points quelconques de l'arbre. Supposons que nous ayons également un nœud s a , b (si s = a , alors il serait évident que le schéma fonctionne, puisque le premier BFS obtiendrait b , et le second reviendrait à a). Supposons également que nous ayons un nœudababp(a,b)d(a,b)sa,bs=ab tel que d ( s , u ) = max x d ( s , x ) .ud(s,u)=maxxd(s,x)

Lemme 0: et b sont des nœuds foliaires.ab

Preuve: S'ils n'étaient pas des nœuds foliaires, nous pourrions augmenter en étendant les extrémités aux nœuds foliaires, contredisant d ( a , b ) étant un diamètre.d(a,b)d(a,b)

max[d(s,a),d(s,b)]=d(s,u)

d(s,a)d(s,b)(s,u)

Cas 1: chemin p(une,b)ne contient pas de sommets. In this case, d(a,b) cannot be the diameter. To see why, let t be the unique vertex on p(a,b) avec la plus petite distance à s. Ensuite, nous voyons qued(a,u)=d(a,t)+d(t,s)+d(s,u)>d(a,b)=d(a,t)+d(t,b), since d(s,u)>d(s,b)=d(s,t)+d(t,b)>d(t,b). Similarly, we would also have d(b,u)>d(a,b). This contradicts d(a,b) being a diameter.

Case 2: path p(a,b) contains vertex s. In this case, d(a,b) again cannot be the diameter, since for some vertex u such that d(s,u)=maxxd(s,x), both d(a,u) and d(b,u) would be greater than d(a,b).

Lemma 1 gives the reason why we start the second Breadth-First search at the last-discovered vertex u of the first BFS. If u is the unique vertex with the greatest possible distance from s, then by Lemma 1, it must be one of the endpoints of some path with a distance equal to the diameter, and hence a second BFS with u as the root unambiguously finds the diameter. On the other hand, if there is at least one other vertex v such that d(s,v)=d(s,u), then we know that the diameter is d(a,b)=2d(s,u), and it doesn't matter whether we start the second BFS at u or v.

xdavidliu
la source
Impressionnant. Merci d'avoir posté cette réponse. Je suis surpris que cette réponse n'ait reçu aucun vote positif.
Zephyr
0

First run a DFS from a random node then the diameter of a tree is the path between the deepest leaves of a node in its DFS subtree: enter image description here

seddik11
la source
4
Pourquoi ça marche?
Yuval Filmus
0

By the definition of BFS, the distance (from the starting node) of each node explored is either equal to the distance of the previous node explored or greater by 1. Thus, the last node explored by BFS will be among those farthest from the starting node.

Thus, the algorithm of using BFS twice amounts to "Pick an arbitrary node x. Find the node a farthest from x (last node found by BFS starting from x). Find the node b farthest from a (last node found by BFS starting from a).", which thus finds two nodes of maximum distance from eachother.

Extrarius
la source
1
Merci pour la réponse avec l'intuition. Cependant, le «ainsi» dans votre dernière phrase n'est pas évident. Pourquoi cela suit-il? Pourquoi le nœud le plus éloignéXdoivent être l'un des deux nœuds à distance maximale l'un de l'autre? Il semble que cela nécessite des preuves.
DW
Je ne sais pas comment construire une telle preuve. J'ai l'impression que l'inverse est intuitivement vrai: si deux nœuds sont à une distance maximale l'un de l'autre, alors, pour un nœud donné, l'un des deux est à la plus grande distance possible de lui.
Extrarius
La revendication "intuitivement vraie" n'est pas vraie en général pour les graphiques généraux. Voir le graphique dans cs.stackexchange.com/a/213/755 , et imaginez démarrer le BFS à partir du nœudv (c.-à-d. laissez X=v); alors il choisiraune=u et trouver le nœud b à la plus grande distance de une, mais cela ne trouve pas les deux nœuds de distance maximale l'un de l'autre. Donc, la déclaration revendiquée, si elle est vraie, doit s'appuyer sur une propriété spéciale des arbres qui ne vaut pas pour les graphiques généraux.
DW
Oui, mais cette question spécifie des arbres non orientés, qui est le contexte dans lequel je me sens. Les cycles de blocage et les bords dirigés rendent beaucoup de problèmes de graphe beaucoup plus simples à raisonner.
Extrarius
0

Une chose clé à savoir est qu'un arbre est toujours plan, ce qui signifie qu'il peut être disposé sur un plan, donc la pensée bidimensionnelle ordinaire fonctionne souvent. Dans ce cas, l'algorithme dit de commencer n'importe où, d'aller aussi loin que possible. La distance entre ce point et le plus loin possible de ce point est la plus longue distance dans l'arbre, et donc le diamètre.

Cette méthode fonctionnerait également pour trouver le diamètre d'une véritable île physique si nous la définissions comme le diamètre du plus petit cercle qui entourerait complètement l'île.

Old Pro
la source
0

@op, the way the cases are defined in the PDF may be a bit off.

I think that the two cases should be:

  1. p1 does not intersect with p2, i.e. there are no common vertices between paths p1 and p2. In this case, define t as the first node on p2 discovered by the first BFS starting at s.

  2. p1 and p2 have at least one common vertex. In this case, define t to be the first node on p2 discovered by the first BFS that is also on p1.

The rest of the proof in the PDF should follow.

With this definition, the figure shown by OP falls into Case 2.

user650654
la source