I suspect a lot of graph theory can be reduced to abstract algebra. You consider matrices over lots of different scalar types. The scalar types should be:
- Rigs (rings without negation),
- idempotent (that is, where x + x = x for all x),
- equipped with involution (so that undirected graphs can be made the default by restricting the matrices which represent graphs to only self-adjoint matrices),
- and the entries of the matrix can be restricted to a *-ideal. Note that a *-ideal can be considered a scalar type in its own right.
Different choices of the above scalar types can be used to capture different graph types: Weighted, directed, undirected, bipartite.
There's no clue to physical implementation, other than that sparse graphs can be treated like sparse matrices. Anybody tried this? How did it work out?
- Rigs (rings without negation),
- idempotent (that is, where x + x = x for all x),
- equipped with involution (so that undirected graphs can be made the default by restricting the matrices which represent graphs to only self-adjoint matrices),
- and the entries of the matrix can be restricted to a *-ideal. Note that a *-ideal can be considered a scalar type in its own right.
Different choices of the above scalar types can be used to capture different graph types: Weighted, directed, undirected, bipartite.
There's no clue to physical implementation, other than that sparse graphs can be treated like sparse matrices. Anybody tried this? How did it work out?