A previous article studied the Naming Game which models how robots (agents) can create their own artificial language without human help. The agents have to connect to one another in some manner which takes us on a deep dive into graph theory.
A graph is a data structure of nodes or vertices and the edges which connect them. A node can represent anything: an image, the physical address of a house, someone’s Facebook profile. In the Naming Game a node is an individual agent and its edges represent connections to other agents.
This graph has three nodes: A, B, and C.
A path is a set of edges joining a set of nodes. If the path connects all nodes it’s a connected graph, otherwise it’s a disconnected graph.
The degree of a node is the number of edges connecting the node. Cycle graphs have a degree of two.
In a complete graph every node connects to the others. As you can see, a complete graph is a connected graph.