[일반] 인접행렬 A^k의 주대각선 성분의 합을 k!로 나눈 값이

[익명(118.235)]

인접행렬이 나타내는 그래프의 길이가 k인 회로의 개수 맞음?

그냥 정사각형을 나타내는 인접행렬의 네제곱의 주대각선 성분의 합은 4!으로 나누어떨어지지 않는데?

[흑화뉴비(coderhs)]

왜 나누는데? - dc App

[흑화뉴비(coderhs)]

원래 나누는 이유는 여러번 카운팅 되는거 제거용인데 이 논리가 k=2,3빼고는 안되는게 4부터는 엣지 두번 왔다갔다랑 사각형의 두가지 경우가 생기고 엣지 형태에 따라 변해서

[수갤러 1(122.199)]

무향이면 2k 아닌가 cycle 당 출발점 k개 반대순서 2개