Qu'est-ce qu'une "sculpture de graphes"?

Question

J'ai préféré a question here, et la réponse la plus prometteuse à ce jour implique des "sculptures de graphes". Le problème est, je n'ai aucune idée de ce que c'est (ni l'OP, apparemment), et il semble très prometteur et intéressant pour plusieurs utilisations. Mon Googlefu m'a échoué sur ce sujet, car je n'ai trouvé aucune ressource utile/gratuite en parler. Est-ce que quelqu'un peut me dire ce qu'est un «graphe», comment en faire un pour un graphe, et comment je peux déterminer ce qui rend une certaine sculpture mieux adaptée à une tâche qu'à une autre? Merci de ne pas aller trop mathématique sur moi (ou d'être prêt à répondre à d'autres questions): Je comprends ce qu'est un graphe, ce qu'est un noeud et ce qu'est un sommet, je gère avec une grosse notation O, mais je n'ai pas de vrais maths Contexte.

Answer 1

Je pense que la réponse donnée dans la question liée est un peu lâche avec la terminologie. Je pense qu'il décrit un arbre sculpture d'un graphique G. Ce n'est toujours pas particulièrement google-friendly, je l'admets, mais peut-être qu'il vous permettra de continuer votre chemin. L'application principale de cette structure semble être dans un algorithme DFS particulier, décrit dans ces twopapers.

Une description peut-être plus claire du même algorithme peut apparaître dans this book.

Je ne suis pas sûr que passer par cet algorithme serait particulièrement utile. C'est un algorithme raisonnablement complexe et l'explication ne serait probablement que le reflet de ceux donnés dans les articles que j'ai liés. Je ne peux pas prétendre le comprendre très bien moi-même. L'approche la plus fructueuse consisterait peut-être à examiner les éléments communs de ces trois liens et à poser des questions précises sur les parties que vous ne comprenez pas.

Answer 2

Q1:

ce qui est une 'sculpture graphique'

Il existe deux types de sculpture graphique: Arbre-Carving et Sculpture.

• Un arbre de sculpture d'un graphique est une partition de l'ensemble de sommets V en sous-ensembles V1, V2, ..., Vk avec les propriétés suivantes. Chaque sous-ensemble constitue un nœud d'arbre T. Pour tout sommet v dans Vj, tous les voisins de v dans G appartiennent soit à Vj lui-même, soit à Vi où Vi est adjacent à Vj dans l'arbre T.

• A sculpture d'un graphe est un partitionnement de l'ensemble de sommets V en une collection de sous-ensembles V1, V2, ... Vk avec les propriétés suivantes. Chaque sous-ensemble constitue un nœud d'un arbre enraciné T. Chaque nœud non-feuille Vj de T possède un sommet spécial noté g (Vj) appartenant à p (Vj). Pour chaque sommet v Vi, tous les voisins de v qui sont des ensembles d'ancêtre de Vi appartiennent soit

  1. Vi ou
  2. Vj, où Vj est le parent de Vi dans l'arbre T, ou
  3. Vl, où Vl est le grand-parent dans l'arbre T.Dans ce cas, toutefois, le voisin de v ne peut être g (p (Vi))

Les defination visées du chapitre 6 du livre "Approximation Algorithms for NP-Hard problems" et paper1. (paper1 est choisi parmi la réponse de Gain, merci Gain.)

Selon ma compréhension. Tree-Carving ou Carving sont une sorte de représentation (ou une simplification) d'un graphique original G. Alors que le nouveau graphique résultant conserve encore 'propriétés de connexion' de G, mais avec une taille beaucoup plus petite (moins de sommet , moins de nœuds). Ces deux méthodes à la fois essayer d'une manière ou d'une autre pour supprimer 'local' ' informations similaires' mais de garder 'structure' 'informations vitales' . En fusionnant certains sommets en un seul sommet et en supprimant certains bords.

Et il semble que Tree Carving est un peu plus simple et plus facile à comprendre Since in **Carving**, edges are allowed to go to a single vertex in the grapdhparenet node as well. Il permettrait de préserver plus d'informations.

Q2:

comment je peux faire un pour un graphique

Je ne sais comment obtenir une sculpture d'arbre.
Vous pouvez vous référer à l'algorithme de paper1.
C'est un algorithme basé sur la profondeur d'abord. Est-ce que DFS, avant le retour d'une itération, vérifie si cette arête est 'bridge' edge ou non. Si oui, vous devez supprimer ce «pont» et ajouter un peu de «back edge». Vous obtiendrez un DFS-partition qui donne une sculpture-arbre de G.

Q3:

comment je peux déterminer ce qui fait mieux une certaine taille adaptée à une tâche qu'un autre?

Désolé je ne sais pas. Je suis aussi un nouveau type en théorie des graphes.

 
 
 
Si vous avez plus de question:

• Quelle est la fonction g de g (Vj)?
  un nœud spécial appelé nœud gris. aller à paper1
• Qu'est ce que la fonction p de p (Vj)?
  Je ne suis pas sûr. peut-être p représente 'parent'. aller à paper1
• Quel est le bord arrière du nœud t?
  un bord (u, v) s.t. u est un décent de t et v est un précédent de t. aller à paper1
• Qu'est-ce qu'un pont?
  bridge wiki