Quest-ce quun graphe complet?

Meilleure réponse

Connaissez-vous la structure dune molécule de cyclopropane? Un cyclopropane est un hydrocarbure alicyclique constitué de trois atomes de carbone disposés dans une structure en anneau comme celle-ci

Observez attentivement la structure. Ignorez les atomes dhydrogène pour linstant et remarquez simplement les liaisons covalentes entre deux atomes de carbone. Observez que chaque atome de carbone est lié à chaque autre atome de carbone dans une molécule de cyclopropane. Cest lintuition de base derrière un graphique complet .

Maintenant une définition formelle:

Un graphe complet composé de n sommets est un graphe connexe tel quil existe un chemin de longueur un entre deux sommets quelconques du graphe . En dautres termes, dans un graphe complet, chaque sommet est adjacent aux sommets restants de sorte que le nombre darêtes dans le graphe est exactement \, \ binom {n} {2}

A un meilleur exemple de graphe complet est \, K\_5 \,

Observez que dans le graphe ci-dessus, chaque sommet est joint à tous les autres sommets. Il sagit donc dun graphique complet.

Réponse

Différence entre la structure des données du graphique et de larborescence:

Graphique

1. Dans graphe il peut y avoir plus dun chemin, cest-à-dire que le graphe peut avoir des chemins unidirectionnels ou bidirectionnels entre les nœuds.
2. Dans le graphe, il ny a pas de concept de root .
3. Le graphe peut avoir des boucles, des circuits ainsi que des boucles automatiques.
4. Dans Graph, il n’existe pas de relation parent-enfant.
5. Les graphiques sont plus complexes que les arbres car ils peuvent avoir des cycles, des boucles, etc.
6. Le graphique est parcouru par DFS : Profondeur Première recherche et dans BFS : Algorithme de première recherche en largeur.
7. Le graphique peut être cyclique ou acyclique.
8. Il existe principalement deux types de graphes: les graphes dirigés et non orientés.
9. Applications graphiques: coloration de cartes, a lgorithmes, coloration du graphique, planification des travaux, etc.
10. Dans le graphique, non. des arêtes dépendent du graphe.
11. Le graphe est un modèle de réseau.

Arbres

1. Larbre est une forme spéciale de graphe, cest-à-dire un graphe minimalement connecté et nayant quun seul chemin entre deux sommets.
2. Larbre est un cas particulier de graphe sans boucles, sans circuits et sans auto-boucles.
3. Dans larborescence, il y a exactement une racine nœud et chaque enfant nont quun seul parent.
4. Dans les arbres, il existe une relation parent-enfant, donc le flux peut être là avec la direction de haut en bas ou vice versa.
5. Les arbres sont moins complexes que les graphiques car ils nont pas de cycles, pas dauto-boucles et sont toujours connectés.
6. La traversée darbre est une sorte de cas particulier de traversée du graphique. Larbre est parcouru en Pré-commande , En ordre et Post-commande (les trois dans DFS ou dans BFS )
7. Les arbres entrent dans la catégorie des DAG: les graphes acycliques dirigés sont une sorte de graphe orienté qui nont pas de cycles.
8. Différents types darbres sont: Arbre binaire , Arbre de recherche binaire, arbre AVL, tas.
9. Applications darborescence : tri et recherche comme la traversée darbre et la recherche binaire.
10. Larbre a toujours n-1 bords.
11. Arbre est un modèle hiérarchique.