Tangential: I don't know anything about graph theory but I'm intrigued by the student-instrument duet example.
Is there a way to include probability/fuzz into the tensor products? In other words, how do you account for non-binary strength of connections between nodes? Like I'm 80% good at piano but 50% good at oboe.
Generalize the adjacency matrices to include values between 0 and 1. Typically, you'd impose some normalization condition like rows and/or columns sum to 1.
Then compute the Kronecker product of matrices to obtain the graph tensor product.
Probably you would model it as a mixed integer optimization task, and optimize for max % competence across picked duets.
Not terribly dissimilar from a traveling salesman problem where you pick the order of nodes traveled between to minimize distance.
Note that the graph coloring described here is a way of defining what the possible nodes and edges are in the duet example. You still need to do some sort of solving on to find a feasible solution within the graph, which would likely also involve the same logic I mentioned above.
yes: you're thinking of a "edge-weighted graph". And extending the tensor product to preserve probabilities is straightforward - you can just multiply the weights of each original pair of edges to get the weight of the edge in the tensor product graph.
Is there a way to include probability/fuzz into the tensor products? In other words, how do you account for non-binary strength of connections between nodes? Like I'm 80% good at piano but 50% good at oboe.