Graph theory

25 Jun 2022

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.

A simple graph

This graph has three nodes: A, B, and C.

Connected graph

A 4-node 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.

3-node cycle graph 4-node cycle graph

Complete graph

In a complete graph every node connects to the others. As you can see, a complete graph is a connected graph.

4-node complete graph