4 ms·
No, each edge in the graph has 2 states. There are 15 edges between the 6 people.
by kevinwang 2y ago
No, each edge in the graph has 2 states. There are 15 edges between the 6 people.
- bongodongobob 2y agoBut 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.