Discussion
Consider a simple undirected unweighted graph with at least three vertices. If \(A\) is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
Answer: D
The number of 3-cycles is the trace of \(A^{3}\) divided by 6.
The entry \((A^{3})_{ii}\) counts the closed walks of length 3 that start and end at vertex \(i\). In a simple graph a closed walk of length 3 must go round a triangle, since there are no loops or repeated edges to use.
Each triangle is counted several times in the trace: it can be started at any of its 3 vertices and traversed in either of 2 directions, giving \(3 \times 2 = 6\) closed walks. So the number of triangles is \(\frac{tr(A^{3})}{6}\).
The trace itself counts every triangle six times; dividing by 2 corrects only for direction and dividing by 3 only for the starting vertex.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development