tucoopy.games.mst¶
Minimum spanning tree (cost) games.¶
Given a complete undirected graph over players with edge weights \(w(i,j)\), the coalition cost is the MST cost over the induced subgraph on \(S\):
This module returns a TU worth game by taking \(v(S) = -c(S)\).
See Also
tucoopy.games.flow.flow_game tucoopy.games.airport.airport_game
Examples:
>>> from tucoopy.games.mst import mst_game
>>> g = mst_game([[0, 1], [1, 0]])
>>> g.value(0b11)
-1.0
mst_game ¶
mst_game(weights, *, player_labels=None)
Construct a minimum spanning tree (cost) game as a TU worth game.
Given a complete undirected graph over players with edge weights \(w(i,j)\), define the coalition cost as the MST cost over the induced subgraph on \(S\):
This constructor returns a worth game by taking \(v(S) = -c(S)\).
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
weights | Sequence[Sequence[float]] | Edge weights for the complete graph (n x n matrix). | required |
player_labels | list of str | Optional labels for players. | None |
Returns:
| Type | Description |
|---|---|
Game | Cooperative game instance representing the MST cost game. |
Raises:
| Type | Description |
|---|---|
InvalidParameterError | If weights is not a square n x n matrix or the graph is disconnected. |
Examples:
>>> from tucoopy.games.mst import mst_game
>>> g = mst_game([[0, 1], [1, 0]])
>>> g.n_players
2
>>> g.value(3)
-1.0