algorithme de construction pour déterminer si un graphique est créé avec un algorithme donné

Question

Soit: G - le graphique V (G) - les sommets E (G) - les bords v, w sommets particuliers.

l'algorithme pour la construction du graphique:

//adding v (a new vertex to the graph) 
if v has a friend in V (G) then E ← E ∪ {vw|w ∈ V (G)} 
G ← (V ∪ v,E) 

Pouvez-vous s'il vous plaît me donner au moins une idée de comment pourrais-je savoir si un graphique donné a été construit avec cet algorithme?

Merci à l'avance.

Answer 1

Si G a des sommets de degré 0, ils doivent avoir été ajoutés après l'ajout du dernier sommet "ami". Retirez-les. Une fois que nous avons fini de trier les sans amis, il doit y avoir un "dernier sommet amical ajouté", identifiable parce qu'il est attaché à tout. Trouvez-le, retirez-le, et revenez chercher et détruire-sans-ami. Si le graphe est finalement complètement détruit par ce processus, il peut être créé par votre algorithme.

Answer 2

Il est à peu près dire, lorsque vous ajoutez v au graphique, si elle a des amis dans le graphique Thew, il obtient un avantage à tous les sommets existants. Donc, chaque addition n'ajoute aucun bord ou arête à tous les sommets. La chose délicate est qu'un sommet ajouté sans aucun ami peut encore obtenir un avantage d'un sommet ajouté suivant.

Si vous pouvez dire dans quel ordre ils ont été ajoutés, vous pouvez déterminer si le graphe est possible en rejouant cet ordre et en vérifiant que chaque ajout ajoute 0 ou tous les arêtes possibles.

Si vous ne connaissez pas l'ordre, vous pouvez essayer de "déballer" le graphique en supprimant les sommets les plus récents, si vous pouvez les comprendre.

Éditez l'algorithme suggéré a été supprimé car il fait ses devoirs ;-).