Preuve d'exactitude :Algorithme pour le diamètre d'un arbre en théorie des graphes

StackOverflow https://stackoverflow.com//questions/20010472

Question

Afin de trouver le diamètre d'un arbre, je peux prendre n'importe quel nœud de l'arbre, effectuer un BFS pour trouver le nœud le plus éloigné de celui-ci, puis effectuer un BFS sur ce nœud.La plus grande distance du deuxième BFS donnera le diamètre.

Mais je ne sais pas comment le prouver ?J'ai essayé d'utiliser l'induction sur le nombre de nœuds, mais il y a trop de cas.

Toutes les idées seraient très appréciées...

Était-ce utile?

La solution

Appelons le noeud final trouvé par le premier bfs x. L'étape cruciale prouve que la X trouvée dans cette première étape toujours "fonctionne" - c'est-à-dire qu'elle est toujours à une extrémité d'un chemin le plus long. (Notez que, en général, il peut y avoir plus d'un chemin tout aussi le plus long.) Si nous pouvons établir cela, il est simple de voir qu'un BFS enraciné à X trouvera du siège aussi loin que possible de X, qui doit donc être globalement chemin le plus long.

indice: Supposons (au contraire) qu'il existe un chemin plus long entre deux sommets U et V, ce qui n'est pas non plus x.

Observez que, sur le chemin unique entre U et V, il doit y avoir du plus haut (le plus proche de la racine) sommet h. Il existe deux possibilités: Soit H est sur le chemin de la racine de la BFS à X ou ce n'est pas le cas. Montrez une contradiction en montrant que dans les deux cas, le chemin U-V peut être effectué au moins aussi longtemps en remplaçant un segment de chemin de chemin avec un chemin de x.

[modifier] en réalité, il peut ne pas être nécessaire de traiter les 2 cas séparément après tout. Mais je trouve souvent plus facile de casser une configuration dans plusieurs cas (ou même de nombreux) cas et de traiter chacun séparément. Ici, le cas où H est sur le chemin de la racine BFS à X est plus facile à manipuler et donne un indice pour l'autre cas.

[modifier 2] revenir à cela plus tard, il me semble maintenant que les deux cas qui doivent être considérés sont (i) le chemin UV intersecte le chemin de la racine à x ( Aux certains Vertex Y, pas nécessairement au point h le plus élevé du chemin UV); et (ii) ça ne le fait pas. Nous avons encore besoin de prouver chaque cas.

Autres conseils

je vais m'entraîner L'indice de j_random_hacker.Laisser s, t être une paire maximalement éloignée.Laisser u être le sommet arbitraire.Nous avons un schéma comme

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,

où x est la jonction de s, t, u (c'est à dire.le sommet unique qui se trouve sur chacun des trois chemins entre ces sommets).

Supposer que v est un sommet éloigné au maximum de u.Si le schéma ressemble maintenant à

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

alors

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),

où l'inégalité existe parce que d(u, t) = d(u, x) + d(x, t) et d(u, v) = d(u, x) + d(x, v).Il existe un cas symétrique où v se fixe entre s et x au lieu d'entre x et t.

L'autre cas ressemble à

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

Maintenant,

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),

donc max(d(v, s), d(v, t)) >= d(s, t) par un argument de moyenne, et v appartient à une paire maximalement éloignée.

Voici une solution alternative de regarder:

Supposons g = ( v , e ) est un arbre fini et non vigoureux avec sommet Vertex v et un ensemble de bord e

"

Considérez l'algorithme suivant:

  1. Laissez compter = 0. Laissez tous les bords dans e être initialement non coloré. Laissez c être initialement égal à v .
    2. .
  2. considérez le sous-ensemble v 'de v contenant tous les sommets avec exactement un bord non coloré:
    • si v 'est vide, puis laisse d = compter * 2 et arrêtez-vous.
      • >
    • si v 'contient exactement deux éléments, puis colorez leur vert mutuel (non coloré), laissez d = compter * 2 + 1, et arrêtez-vous.
    • sinon, v 'contient au moins trois sommets; procéder comme suit:
  3. incrément comptez par un.
  4. retirer tous les sommets de c qui n'ont pas de bords non colorés.
  5. pour chaque sommet dans v avec deux bords non colorés ou plus, recroiser chacun de ses bords verts rouges (certains sommets peuvent avoir zéro ces bords).
  6. pour chaque sommet dans v ', couleur son bord de bord non coloré.
  7. retourner à l'étape (2).

    8. qui coulent essentiellement du graphique des feuilles vers l'intérieur, des chemins de marquage avec une distance maximale à une feuille en vert et marquant ceux qui ne sont que des distances plus courtes en rouge. Pendant ce temps, les nœuds de c , le centre, avec une distance maximale plus courte à une feuille sont éteignées jusqu'à c contient uniquement les un ou deux nœuds avec la plus grande distance maximale à une feuille.

    Par construction, tous les chemins simples des sommets de feuilles à leur sommet central le plus proche que Traverser uniquement les bords verts sont la même longueur ( compte ) et tous les autres chemins simples d'un sommet de feuilles à son centre le plus proche. sommet (traverser au moins un bord rouge) est plus court. Il peut en outre être prouvé que

    • Cet algorithme se termine toujours dans les conditions données, laissant à chaque bord de g de couleur rouge ou vert, et laissant c avec un ou deux éléments.
    • à l'algorithme Terminaison, d est le diamètre de g , mesuré dans les bords.
    • Étant donné un sommet v dans v , les chemins simples maximaux de longueur dans g < / Strong> Démarrage de v sont exactement ceux qui contiennent contiennent tous les sommets du centre, se terminent à une feuille et traversent uniquement les bords verts entre le centre et le point d'extrémité lointain. Celles-ci vont de v , à travers le centre, à l'une des feuilles le plus éloignées du centre.

    Considérez maintenant votre algorithme, qui pourrait être plus pratique, à la lumière de ce qui précède. À partir de n'importe quel sommet v , il existe exactement un chemin simple p de ce sommet, se terminant dans un sommet central et contenant tous les sommets de la Centre (car g est un arbre, et s'il y a deux sommets dans c alors ils partagent un bord) . Il peut être montré que les chemins simples maximaux dans g ont v comme un point final ont la forme de l'union de P avec un chemin simple du centre à la feuille traversant uniquement des bords verts.

    Le point clé de nos fins est que le bord entrant de l'autre point final est nécessairement vert. Par conséquent, lorsque nous effectuons une recherche sur les chemins les plus longs qui commençaient là, nous avons accès à ceux qui ne traversent que des bords verts de la feuille à travers (tous les sommets de) le centre à une autre feuille. Ce sont exactement les chemins simples maximaux de longueur dans g , nous pouvons donc être convaincus que la deuxième recherche révélera effectivement le diamètre du graphique.

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top