Quels sont les graphiques en termes simples

18

Que sont les graphiques en informatique et à quoi servent-ils? En termes simples, de préférence.

J'ai lu la définition sur Wikipédia :

En informatique, un graphe est un type de données abstrait destiné à implémenter les concepts de graphe et d'hypergraphe à partir des mathématiques.

Une structure de données de graphe est constituée d'un ensemble fini (et éventuellement mutable) de paires ordonnées, appelées arêtes ou arcs, de certaines entités appelées nœuds ou sommets. Comme en mathématiques, une arête (x, y) est dite pointer ou aller de x à y. Les nœuds peuvent faire partie de la structure du graphe ou peuvent être des entités externes représentées par des indices entiers ou des références.

mais je recherche une définition moins formelle et plus facile à comprendre.

ConditionRacer
la source
Voulez-vous dire des graphiques de la structure des données?
System Down
1
Oui désolé. Graphes comme décrit ici en.wikipedia.org/wiki/Graph_(abstract_data_type) , seulement je cherche une définition moins formelle et plus facile à comprendre.
ConditionRacer
@ Justin984 Les liens Wikipedia avec des parenthèses (et il y en a tellement) ne fonctionnent pas, les parenthèses ne fonctionnent pas bien avec le format Markdown pour les liens. Maintenant, pour référence future, veuillez ajouter des clarifications à votre question dans la question elle-même, pas dans les commentaires, elles ne sont pas si visibles et il est facile de les manquer. Je vais modifier votre commentaire ci-dessus dans la question ...
yannis
@ Justin984 Notez également que Computer Science Stack Exchange pourrait être un peu plus approprié pour des questions comme celle-ci que les programmeurs. Ne vous méprenez pas, la question est parfaitement sur le sujet ici, et elle a obtenu d'excellentes réponses, mais cela ne ferait pas de mal si vous jetez un œil à une communauté qui est un peu plus concentrée sur les concepts informatiques fondamentaux que nous ne le sommes (ne le faites pas mais posez la même question sur plusieurs sites, si vous la publiez sur le mauvais site, nous pouvons la déplacer automatiquement sur la bonne).
yannis

Réponses:

26

Un parfait exemple de profane pourrait être Facebook . Le réseau de vous, vos amis et leurs amis, etc., est collectivement appelé le graphique social .

Dans ce "graphique", les personnes sont considérées comme des nœuds du graphique et les bords sont des liens d'amitié .

Dans Facebook, l' ami est une relation bidirectionnelle (A est l'ami de B => B est l'ami de A), de sorte que le graphique est un graphique non orienté . Un réseau comme Google+ ou Twitter serait considéré comme un graphique dirigé, car la direction de la relation a un sens ici.

Tous ces graphiques sont appelés graphiques cycliques , car les relations entre les nœuds peuvent former des cycles. Un arbre généalogique , d'autre part, est un type spécial de graphique qui, entre autres, est acyclique car il ne peut pas y avoir de cycles dans la relation d'arbre généalogique. (Il est techniquement appelé un graphique acyclique dirigé (DAG) car il est à la fois dirigé et acyclique)

Cela devrait couvrir tout le jargon de base concernant les graphiques, alors maintenant vous devriez pouvoir suivre le reste du matériel sur le terrain.

Karthik T
la source
1
Je ne peux pas croire qu'il ne m'est pas venu à l'esprit qu'il s'appelle l'API Facebook Graph. Bon exemple!
ConditionRacer
4
L'arbre généalogique n'est pas cyclique? Ça ne devrait pas l'être, mais c'est malheureusement ...
Marjan Venema
1
@MarjanVenema, l'arbre généalogique est-il cyclique ? (C'est un graphique orienté, donc la direction est importante pour déterminer les cycles, et les relations de pas ne comptent probablement pas vraiment.)
huon
@dbaupp: Je n'ai aucune envie d'entrer dans les détails ici, donc je vais juste mentionner un mot: l'inceste.
Marjan Venema
5
@MarjanVenema, vous manquez mon point. Un cycle dans un graphique dirigé est un modèle comme A -> B -> C -> A(c'est-à-dire un cercle de flèches), l'inceste donne simplement A -> B -> Cet A -> D -> C(c'est-à-dire un diamant). Un cycle dans un arbre généalogique nécessite un voyage dans le temps.
Huon
16

Les graphiques sont l'un des concepts mathématiques les plus importants utilisés en informatique.

Vous avez vu des graphiques plusieurs fois. Imaginez que vous prenez l'avion d'une ville à l'autre. Vous trouverez inévitablement un joli magazine sur papier glacé de la compagnie aérienne dans la poche du siège devant vous. À l'arrière de ce magazine, vous pouvez presque toujours trouver une carte qui représente les villes desservies par cette compagnie aérienne représentées par des cercles, avec les vols qui relient ces villes représentées par des lignes courbes. Voilà un graphique! Les villes, représentées par des cercles, sont les nœuds de ce graphique et les vols, représentés par des lignes courbes, sont les bords. Les graphiques ne sont que des objets avec des nœuds et des arêtes qui relient les nœuds.

Vous pouvez embellir ces graphiques simples de différentes manières. Vous ne voulez pas voir juste un tas de cercles et de lignes lorsque vous regardez cette carte. Ces villes ont des noms. L'étiquetage de ces villes donne un graphique étiqueté. (Vous pouvez également étiqueter les bords, par exemple, le vol 1234.) L'informatique associe souvent des données aux nœuds, parfois aux bords, mais ce n'est qu'une extension de l'étiquette. C'est toujours un graphique étiqueté. Un autre embellissement résulte si vous pouvez voler directement de la ville A à la ville B, mais pas de la ville B à la ville A. Un moyen évident de le représenter est de mettre une flèche sur la ligne qui relie les villes pour représenter cette relation à sens unique. Vous avez maintenant un graphique orienté.

Les listes liées, les arbres, les diagrammes de transition d'état et de nombreuses autres structures de données informatiques sont tous des exemples de graphiques. C'est un concept très puissant.

David Hammen
la source
Je voudrais en fait étendre cet exemple pour noter que toutes les entités décrites dans votre exemple peuvent être représentées comme des sommets dans un graphique (ville, avion, magazine, carte, etc.), la carte elle-même n'étant qu'un sommet unique.
Demian Brecht
14

Une meilleure question serait "A quoi ne servent pas les graphiques?". L'informatique est, à bien des égards, l'étude des graphes.

Un graphe, en termes simples, est une collection d'objets abstraits arbitraires appelés «nœuds» ou «sommets» qui représentent des points de connexion. Ils sont ensuite connectés via des "chemins" ou "arêtes". Le type de données abstrait "Graph" est une implémentation du "Graph" mathématique. Donc, fondamentalement, vous avez des nœuds et des bords comme champs et diverses opérations que vous pouvez effectuer sur eux. Vous pouvez, par exemple, ajouter un nouveau nœud à la collection du graphe (cela peut être une liste ou un tableau ou une autre structure selon la langue). Vous pouvez ensuite lier ce nœud aux nœuds existants. Les opérations consisteraient également à parcourir le graphique, à vérifier si deux nœuds partagent un bord (sont connectés), à récupérer des valeurs à partir de nœuds ou d'arêtes et à supprimer des nœuds ou des bords du graphique.

En ce qui concerne l'utilisation, les graphiques sont utilisés partout. Le réseautage en fait un usage particulièrement intensif, mais ils se trouvent dans l'intelligence artificielle, l'exploration de données, le développement de jeux, la géoinformatique et une foule d'autres disciplines. En informatique formelle, ils voient encore plus d’utilité, notamment comme moyen de représenter l’État.

En fait, tout ce que vous pouvez représenter comme un ensemble de connexions peut être représenté sous forme de graphique et implémenté via cet ADT sous une forme ou une autre.

Voici un exemple de graphique que j'ai fait:

Exemple de graphique

Ingénieur du monde
la source
3

Un graphique est juste une collection d'objets reliés entre eux par des lignes appelées sommets.

Le terme «graphique» est une abstraction et une généralisation de nombreuses structures de données utilisées dans le développement de logiciels. Les listes liées, les arbres binaires et les AST sont tous des graphiques.

Fondamentalement, toute collection d'objets qui a des pointeurs qui associent les objets les uns aux autres est un graphique. Une fois que vous avez un graphique, vous pouvez lui appliquer les principes de la théorie des graphes pour résoudre certains problèmes .

Robert Harvey
la source