Problem 2647. Find the maximal cliques in an undirected graph

Created by Matthew Eicholtz

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/image","targetMode":"","relationshipId":"rId1","target":"/media/image1.png"}],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is a variant of a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/2646-determine-the-number-of-maximal-cliques-in-an-undirected-graph\"><w:r><w:t>previous problem</w:t></w:r></w:hyperlink><w:r><w:t> on maximal cliques. Instead of simply computing the number of maximal cliques in an undirected graph, now you must return the cliques themselves.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given an NxN adjacency matrix (A) for an undirected graph with N vertices, return an array (C) in which each column encodes one of the maximal cliques in the graph. If C(i,j) = 1, then the ith vertex in the graph is included in the jth clique. The order of columns does not matter, but all maximal cliques must be given - that is, size(C,2) should equal the number of maximal cliques.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Consider the graph shown below,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:customXml w:element=\"image\"><w:customXmlPr><w:attr w:name=\"height\" w:val=\"-1\"/><w:attr w:name=\"width\" w:val=\"-1\"/><w:attr w:name=\"relationshipId\" w:val=\"rId1\"/></w:customXmlPr></w:customXml></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>which has the following adjacency matrix:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[A = [ 0 1 0 0 0\n 1 0 1 1 0\n 0 1 0 1 0\n 0 1 1 0 1\n 0 0 0 1 0 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The maximal cliques are {1,2}, {2,3,4}, and {4,5}. Therefore, one (of three) valid outputs is:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[C = [ 1 0 0\n 1 1 0\n 0 1 0\n 0 1 1\n 0 0 1 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>NOTE: You may assume the data type of the adjacency matrix (A) is double.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"},{"partUri":"/media/image1.png","contentType":"image/png","content":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAACAAAAAgCAMAAABEpIrGAAADAFBMVEV4eHiTk5P29vaBgYGcnJzAwMC3t7eKiorS0tLt7e3b29vk5OTJycn///9vb28AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD61b95AAAAyklEQVR42q2SSQ6FIAxAWzQxkcj976lEE5R+hojQOmw+Cxa8RwcoGnhf6oNDD0AvGL8j/E2wC+JiXwSaAKbbatGkLjBrX13szynmtPXnKc2eCRiMGQtXxrq2hmZRuuXx6SVdPlPpopeC387sFMMIwdsyAMFAEcHuptW5oIaKYgjHBBoZ512snMeJ8g7o0DmA5jwKXRdqy9W6gfMzhd7iMOySlxq0qn/z4leR43HNQ8WrLtYi1Dz+pnjsmt/8ZsulwLgQOOeC4EyQHH5z1GUZiLNTtwAAAABJRU5ErkJggg=="}]}

This is a variant of a <a href = "http://www.mathworks.com/matlabcentral/cody/problems/2646-determine-the-number-of-maximal-cliques-in-an-undirected-graph">previous problem</a> on maximal cliques. Instead of simply computing the number of maximal cliques in an undirected graph, now you must return the cliques themselves.Given an NxN adjacency matrix (A) for an undirected graph with N vertices, return an array (C) in which each column encodes one of the maximal cliques in the graph. If C(i,j) = 1, then the ith vertex in the graph is included in the jth clique. The order of columns does not matter, but all maximal cliques must be given - that is, size(C,2) should equal the number of maximal cliques.ExampleConsider the graph shown below,<img src = "https://dl.dropboxusercontent.com/u/13345152/examplegraph.png">which has the following adjacency matrix:<pre class="language-matlab">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 ]
</pre>The maximal cliques are {1,2}, {2,3,4}, and {4,5}. Therefore, one (of three) valid outputs is:<pre class="language-matlab">C = [ 1 0 0
 1 1 0
 0 1 0
 0 1 1
 0 0 1 ]
</pre>NOTE: You may assume the data type of the adjacency matrix (A) is double.

This is a variant of a <http://www.mathworks.com/matlabcentral/cody/problems/2646-determine-the-number-of-maximal-cliques-in-an-undirected-graph previous problem> on maximal cliques. Instead of simply computing the number of maximal cliques in an undirected graph, now you must return the cliques themselves.

Given an NxN adjacency matrix (A) for an undirected graph with N vertices, return an array (C) in which each column encodes one of the maximal cliques in the graph. If C(i,j) = 1, then the ith vertex in the graph is included in the jth clique. The order of columns does not matter, but all maximal cliques must be given - that is, size(C,2) should equal the number of maximal cliques.

*Example*

Consider the graph shown below,

<<https://dl.dropboxusercontent.com/u/13345152/examplegraph.png>>

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 maximal cliques are {1,2}, {2,3,4}, and {4,5}. Therefore, one (of three) valid outputs is:

C = [ 1 0 0
        1 1 0
        0 1 0
        0 1 1
        0 0 1 ]

NOTE: You may assume the data type of the adjacency matrix (A) is double.

Solve

Solution Stats

12 Solutions
5 Solvers

Last Solution submitted on Jan 09, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

rifat on 4 Nov 2014

test suite 3 prevented my brute-force :(

Solution Comments

Show comments

Problem Recent Solvers5

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!