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.
Connected graph
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.
Cycle graph
The degree of a node is the number of edges connecting the node. Cycle graphs have a degree of two.
Complete graph
In a complete graph every node connects to the others. As you can see, a complete graph is a connected graph.
