3 ms·
But the edge states don't matter, the node states do. They're either connected friends or they aren't. What's the third state?
by bongodongobob 2y ago
But the edge states don't matter, the node states do. They're either connected friends or they aren't. What's the third state?
- 01HNNWZ0MV43FF 2y ago2 groups of 3 mutual friends is a different graph than 3 pairs of friends
- lmm 2y agoNo, the connections are what matters. A may be friends with both B and C, but that doesn't mean that B is necessarily friends with C.
- bongodongobob 2y agoI understand that. That's the encoding of being "connected".
- lmm 2y agoWhere did you get "connected" from? We're talking about whether they are "a trio of mutual friends" or not; that requires them all to be friends with each other, not merely "connected".
- sixfiveotwo 2y agoIn this encoding of the problem, the graph is fully connected, the edges indicate the state of a connection (ie. friendship) between 2 users, and the goal is to check that there is either a chain of 2 "connected" edges (A to B and B to C for any A,B,C in the nodes) or 2 "disconnected" edges, which indeed isn't easy to do the tedious way. The crucial property here is the symmetry between connected and disconnected edges: for any given configuration, if it's difficult to check it on one hand, then it should be easy to do it on the other.