Problem 1169. Count the Number of Directed Cycles in a Graph

Created by Joseph Kirk

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":[],"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>Given an asymmetric adjacency matrix, determine the number of unique</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>directed</w:t></w:r><w:r><w:t> cycles.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example, the graph represented by 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 = [\n  0 1 1 0;\n  1 1 0 1;\n  1 0 0 1;\n  1 1 0 0];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>has 7 cycles. They are:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[2 -> 2]\n[1 -> 2 -> 1]\n[1 -> 3 -> 1]\n[2 -> 4 -> 2]\n[1 -> 2 -> 4 -> 1]\n[1 -> 3 -> 4 -> 1]\n[1 -> 3 -> 4 -> 2 -> 1]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The input is an adjacency matrix of 0s and 1s, and the output should be the number of unique (simple) directed cycles in the graph.</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>"}]}

Solve

Solution Stats

25 Solutions
5 Solvers

Last Solution submitted on Jul 01, 2020

Last 200 Solutions

Problem Comments

Problem Recent Solvers5

Problem Tags

cycles directed graphs graph theory

Problem 1169. Count the Number of Directed Cycles in a Graph

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers5

Suggested Problems

More from this Author3

Problem Tags

Problem 1169. Count the Number of Directed Cycles in a Graph

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers5

Suggested Problems

More from this Author3

Problem Tags

Players