Différence entre les sommets et les arêtes [graphes, algorithme et DS]

Question

Je viens maintenant commencé à lire un livre Les algorithmes qui définit les graphiques comme suit:

graphiques - qui représentent des relations entre paires d'objets arbitraires. La figure 1.8 (b) modélise un réseau de routes sous la forme d'un graphique, où les sommets sont des villes et les tronçons sont des routes reliant des paires de villes. Les graphiques sont probablement l'objet en question chaque fois que vous cherchez un « réseau », « circuit », « web » ou « relation »

Figure 1.8 (b) est la suivante:.

Ce qui me confond ici est la ligne suivante:

... où les sommets sont les villes et les bords des routes qui relient les paires de villes ...

Answer 1

Les sommets sont les points, les arêtes sont les lignes. D'où les villes et les routes. Je ne suis pas sûr de ce qui vous rend confus, mais en général les graphiques sont en effet utilisés pour modéliser les connexions entre les objets.

Si vous avez un groupe d'objets (sommets) qui peuvent être "connectés" les uns aux autres, un graphique serait la structure de données de haut niveau pour le maintenir. Je dis "haut niveau" car en pratique vous aurez probablement besoin de structures de données pour maintenir un graphique dans la mémoire/base de données/fichier: matrices, listes de liens, tables plusieurs-à-plusieurs, etc

Si le " direction "n'est pas important, comme dans le cas du graphique ci-dessus (c'est-à-dire que toutes les routes sont bidirectionnelles), vous avez un" graphique non orienté ". Si le sens de la connexion a une importance (par exemple s'il y a des routes unidirectionnelles entre les villes), vous aurez un "graphe orienté", où chaque arête est en fait une "flèche" pointant vers une certaine direction.

Si vous êtes très nouveau à ce sujet, je vous recommande de lire le Wikipedia entry correspondant. Pour quelques "vrais" études, je recommande Cormen et al's Introduction to Algorithms, le livre que j'ai étudié, qui est à mon avis l'un des meilleurs livres d'informatique jamais écrit.

Answer 2

Les sommets sont les nœuds du graphique. Les arêtes sont les arcs qui relient des paires de nœuds.

Answer 3

Si vous comptez chaque ligne, vous voyez que les vertices.edges sont les coins [par exemple, une sphère n'a pas de coins et pas de sommets mais a i face.if vous voulez connaître toutes les propriétés des formes 3D rechercher des formes 3D sur votre ordinateur. Vous obtiendrez plus d'explications.