Graphs & paths: Bron-Kerbosch, maximal cliques.

Graphs & paths: Bron-Kerbosch, maximal cliques.

6 years ago
Anonymous $cyhBy-qkd5

https://towardsdatascience.com/graphs-paths-bron-kerbosch-maximal-cliques-e6cab843bc2c

Sally is having a party. ? She invites Max, Sue, Tom and Jake. Then Tom invites Ryan, who brings Jess, and Jess brings Lu who knows Tom’s friends. Jake is popular, so Jake also knows Jess and Ryan. Then there is Joe. Joe knows Lu, but doesn’t know Sally, or anyone else really, although still ‘technically’ a guest at the party. Three randoms Liz, Ty, and Jay show up, because the party is ? and finally, Erin, who almost always is fashionably late, shows up with Amy and Jack.

Our task is to find all the maximal cliques, the groupings of people that all know each other.