Graph Theory37 sections · 1633 units
Open in Course

Bipartite Game Graphs

(Player positions alternate)

A bipartite game graph has two sets of vertices: player 11 positions and player 22 positions. Edges only go between the two sets. This structure arises naturally in turn-based games. Player 11 positions are where player 11 moves, and vice versa. Bipartite structure simplifies analysis.

You know whose turn it is based on which set the current position belongs to. The bipartite structure means positions alternate between two sets. This often simplifies analysis because you can characterize winning positions by which partition they belong to.