Problem 2646. Determine the number of maximal cliques in an undirected graph
In an undirected graph, a clique is a subset of vertices that are fully connected, i.e. there is an edge between all pairs of vertices in the subset. A maximal clique is one in which the subset of vertices is not part of a larger clique. So, for instance, a fully connected graph has many cliques, but only one maximal clique.
Given an NxN adjacency matrix (A) for an undirected graph with N vertices, return the number (num) of maximal cliques.
Example
Consider the graph shown below,
which has the following adjacency matrix:
A = [ 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 ]
The number of maximal cliques is 3. The maximal cliques are {1,2}, {2,3,4}, and {4,5}.
NOTE: You may assume the data type of the adjacency matrix is double.
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers6
Suggested Problems
-
Sum all integers from 1 to 2^n
14454 Solvers
-
Calculate the Hamming distance between two strings
316 Solvers
-
Celsius to Fahrenheit converter
598 Solvers
-
Try 1.5.4: Celsius to Fahrenheit
791 Solvers
-
170 Solvers
More from this Author44
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!