Graph theory is used to study the relations between objects. A graph is composed of vertices and edges in a diagram such as this:
A-----B
| / \
| / \
| / E
| / /
|/ /
C-----D
In the above diagram, A
is linked to B
and C
; B
is linked to A
, C
, and E
; C
is linked to A
, B
, and D
; D
is linked to C
and E
; and E
is linked to B
and D
. As that description was rather wordy, a graph can be represented as a symmetric boolean matrix where a 1 represents a connection and a 0 represents the lack thereof. The above matrix is translated to this:
01100
10101
11010
00101
01010
For the purpose of this problem, the matrix definition can be extended to include the distances or weights of the paths between nodes. If individual ASCII characters in the diagram have weight 1, he matrix would be:
05500
50502
55050
00502
02020
A "complete graph" consists of a set of points such that each point is linked to every other point. The above graph is incomplete because it lacks connections from A
to D
and E
, B
to D
, and C
to E
. However, the subgraph between A
, B
, and C
is complete (and equally weighted). A 4-complete graph would look like this:
A---B
|\ /|
| X |
|/ \|
C---D
and would be represented by the matrix:
01111
10111
11011
11101
11110
This problem is as follows: Given a symmetric matrix representing a graph and a positive integer n
, find the number of distinct equally-weighted complete subgraphs of size n
contained within.
You may assume that the input matrix is numeric and symmetric, and may choose input/output format. An entry in the matrix may be part of multiple equally-weighted subgraphs as long as they are distinct and of equal size. You may assume that n
is a positive integer greater than or equal to 3.
The winning criterion for this challenge is code golf. Standard rules apply.
n
too? \$\endgroup\$