[๊ทธ๋ž˜ํ”„ ์ด๋ก ] ์ธ์ ‘ํ–‰๋ ฌ๊ณผ ๊ฑฐ๋“ญ์ œ๊ณฑ์˜ ์„ฑ์งˆ

์•„๋ž˜ ๊ธ€์„ ๋จผ์ € ๋ณด์‹œ๊ณ  ์˜ค์‹œ๊ธฐ๋ฅผ ์ถ”์ฒœ๋“œ๋ฆฝ๋‹ˆ๋‹ค.
https://scian.tistory.com/174

 

[๊ทธ๋ž˜ํ”„ ์ด๋ก ] ์šฉ์–ด ๋ฐ ๊ธฐ๋ณธ ๊ฐœ๋… ์ •๋ฆฌ

๊ธฐ๋ณธ ์šฉ์–ด๊ทธ๋ž˜ํ”„ ์ ๊ณผ ์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋„ํ˜• ($G(V,E)$) ๊ผญ์ง“์  ๊ทธ๋ž˜ํ”„์—์„œ์˜ ์  (๊ทธ๋ž˜ํ”„์—์„œ ๊ผญ์ง“์  ์ง‘ํ•ฉ: V) ๋ณ€ ๊ผญ์ง“์ ์„ ์—ฐ๊ฒฐํ•œ ์„  (๊ทธ๋ž˜ํ”„์—์„œ ๋ณ€ ์ง‘ํ•ฉ: E) ๊ฐ™์€ ๊ทธ๋ž˜ํ”„์ด๋‹ค. ๊ผญ์ง“์ ์˜ ์œ„์น˜๋ฅผ ๋ฐ”

scian.xyz


์ธ์ ‘ํ–‰๋ ฌ
์–ด๋–ค ๊ทธ๋ž˜ํ”„์˜ ๋‘ ๊ผญ์ง“์ ์ด ํ•œ ๋ณ€์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์œผ๋ฉด 1, ๋ณ€์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€ ์•Š์œผ๋ฉด 0์œผ๋กœ ํ•˜์—ฌ ๊ทธ๋ž˜ํ”„์˜ ๋‘ ๊ผญ์ง“์  ์‚ฌ์ด์˜ ๊ด€๊ณ„๋ฅผ ๋‚˜ํƒ€๋‚ธ ํ–‰๋ ฌ

$v_{1}, …, v_{n}$์„ ๊ผญ์ง“์ ์œผ๋กœ ๊ฐ–๋Š” ๊ทธ๋ž˜ํ”„ $G$์˜ ์ธ์ ‘ํ–‰๋ ฌ์„ $A$๋ผ ํ•  ๋•Œ,

G์˜ ๊ฐ ๊ผญ์ง“์ ์˜ ์ฐจ์ˆ˜
$A^{2}$์˜ ๋Œ€๊ฐ์„ฑ๋ถ„ ($v_{i}$์˜ ์ฐจ์ˆ˜: $A^{2}$์˜ i,i ์„ฑ๋ถ„)

  • G์˜ ๋ณ€์˜ ์ˆ˜: $\frac{tr(A^{2})}{2}$ (๋ชจ๋“  ๊ผญ์ง“์  ์ฐจ์ˆ˜ ํ•ฉ/2)


$v_{i}$์—์„œ $v_{j}$๋กœ ๊ฐ€๋Š” ๊ธธ์ด๊ฐ€ k์ธ ๊ธธ์˜ ๊ฐœ์ˆ˜
$A^{k}$์˜ $(i,j)$ ์„ฑ๋ถ„

G์•ˆ์— ์žˆ๋Š” ์‚ผ๊ฐํ˜•์˜ ๊ฐœ์ˆ˜
$\frac{tr(A^{3})}{6}$ ($A^3$ ๋Œ€๊ฐ์„ฑ๋ถ„ ํ•ฉ/3!)