๊ธฐ๋ณธ ์ฉ์ด
๊ทธ๋ํ
์ ๊ณผ ์ ์ผ๋ก ์ด๋ฃจ์ด์ง ๋ํ ($G(V,E)$)
๊ผญ์ง์
๊ทธ๋ํ์์์ ์ (๊ทธ๋ํ์์ ๊ผญ์ง์ ์งํฉ: V)
๋ณ
๊ผญ์ง์ ์ ์ฐ๊ฒฐํ ์ (๊ทธ๋ํ์์ ๋ณ ์งํฉ: E)
๊ฐ์ ๊ทธ๋ํ์ด๋ค.
๊ผญ์ง์ ์ ์์น๋ฅผ ๋ฐ๊พธ๊ฑฐ๋ ๋ณ์ ๊ตฌ๋ถ๋ฆฌ๊ฑฐ๋ ๋์ด๊ฑฐ๋ ์ค์ฌ๋ ๋ ๊ทธ๋ํ๋ฅผ ๊ฐ์ ๊ทธ๋ฆผ์ผ๋ก ๊ทธ๋ฆด ์ ์๋ค.
๊ผญ์ง์ ์ ์ฐจ์
๊ทธ๋ํ์์ ํ ๊ผญ์ง์ ์ ์ฐ๊ฒฐ๋ ๋ณ์ ๊ฐ์
๊ทธ๋ํ์์ ๋ชจ๋ ๊ผญ์ง์ ์ ์ฐจ์์ ํฉ = 2*๋ณ์ ๊ฐ์
์์ ๊ทธ๋ํ
์๋ก ๋ค๋ฅธ ๋ ๊ผญ์ง์ ์ฌ์ด์ ํญ์ ๋ณ์ด ์ค์ง ํ ๊ฐ ์๋ ๊ทธ๋ํ ($K_{n}$)
์ฐ๊ฒฐ๊ทธ๋ํ
์์์ ์๋ก ๋ค๋ฅธ ๋ ๊ผญ์ง์ ์ด ์ฐ๊ฒฐ๋ ๊ทธ๋ํ
๊ฒฝ๋ก
๊ทธ๋ํ์ ํ ๊ผญ์ง์ ์์ ๋ค๋ฅธ ๊ผญ์ง์ ์ผ๋ก ์ด๋ํ ๋, ํ ๋ฒ ์ง๋ ๋ณ์ ๋ฐ๋ณตํ์ง ์์ผ๋ฉด์ ์ฐ๊ฒฐ๋ ๋ณ์ ๋ฐ๋ผ ์์๋๋ก ๊ผญ์ง์ ์ ๋์ดํ ๊ฒ
๊ฒฝ๋ก์ ๊ธธ์ด
ํ ๊ผญ์ง์ ์์ ๋ค๋ฅธ ๊ผญ์ง์ ์ผ๋ก ๊ฐ๋ ๊ฒฝ๋ก์์ ์ง๋๋ ๋ณ์ ๊ฐ์
ํ๋ก
ํ ๊ผญ์ง์ ์์ ์ถ๋ฐํ์ฌ ์ถ๋ฐํ ๊ผญ์ง์ ์ผ๋ก ๋์์ค๋ ๊ฒฝ๋ก
์ธ์ ํ๋ ฌ
์ด๋ค ๊ทธ๋ํ์ ๋ ๊ผญ์ง์ ์ด ํ ๋ณ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด 1, ๋ณ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ง ์์ผ๋ฉด 0์ผ๋ก ํ์ฌ ๊ทธ๋ํ์ ๋ ๊ผญ์ง์ ์ฌ์ด์ ๊ด๊ณ๋ฅผ ๋ํ๋ธ ํ๋ ฌ
https://scian.tistory.com/175
์ฌ๋ฌ ๊ทธ๋ํ
ํ๋ฉด๊ทธ๋ํ
ํ๋ฉด์์ ๋ณ๋ค์ด ๊ผญ์ง์ ์์๋ง ๊ต์ฐจํ๋ ๊ทธ๋ํ
์ค์ผ๋ฌ๊ณต์: ์ฐ๊ฒฐ๋ ํ๋ฉด๊ทธ๋ํ์์ $v-e+f=2$
- $e \leq 3v-6$ (๋จ, $v \geq 3$)
- ์ฐจ์๊ฐ 5 ์ดํ์ธ ๊ผญ์ง์ ์ด ์ ์ด๋ ํ๋ ์์
์ค์ผ๋ฌ ๊ฒฝ๋ก
์ฐ๊ฒฐ๋ ๊ทธ๋ํ์ ๋ชจ๋ ๋ณ์ ์ง๋๋ฉฐ ํ ๋ฒ ์ง๋ ๋ณ์ ๋ค์ ์ง๋์ง ์๋ ๊ฒฝ๋ก
โ ํ์์ ์ ๊ฐ์ 0๊ฐ ํน์ 2๊ฐ, ์์์ ๊ณผ ๋์ ์ด ํ์์
์ค์ผ๋ฌ ํ๋ก
ํ๋ก์ธ ์ค์ผ๋ฌ ๊ฒฝ๋ก
โ ํ์์ ์ ๊ฐ์ง์ง ์์
์ค์ผ๋ฌ ๊ทธ๋ํ
์ค์ผ๋ฌ ํ๋ก๋ฅผ ๊ฐ๋ ๊ทธ๋ํ
ํด๋ฐํด ๊ฒฝ๋ก
์ฐ๊ฒฐ๋ ๊ทธ๋ํ์ ๋ชจ๋ ๊ผญ์ง์ ์ ํ ๋ฒ์ฉ๋ง ์ง๋๋ ๊ฒฝ๋ก
ํด๋ฐํด ํ๋ก
ํ๋ก์ธ ํด๋ฐํด ๊ฒฝ๋ก
n๊ฐ์ ๊ผญ์ง์ ์ ๊ฐ๊ณ ์๋ ์ฐ๊ฒฐ๊ทธ๋ํ์์ ์ธ์ ํ์ง ์์ ์์์ ๋ ๊ผญ์ง์ ์ ์ฐจ์์ ํฉ์ด n ์ด์์ผ ๊ฒฝ์ฐ, ํด๋ฐํดํ๋ก๊ฐ ์กด์ฌ (๋จ, nโฅ3)
ํด๋ฐํด ๊ทธ๋ํ
ํด๋ฐํด ํ๋ก๋ฅผ ๊ฐ๋ ๊ทธ๋ํ
์ํ๋
์ํ๋
ํ๋ก๋ฅผ ๊ฐ์ง๊ณ ์์ง ์๋ ์ฐ๊ฒฐ๊ทธ๋ํ
์ํ๋์ด๋ฉด, $e=v-1$ ๋ง์กฑ (ํญ์ $f=1$)
G๊ฐ n๊ฐ์ ๊ผญ์ง์ ์ ๊ฐ๋ ์ฐ๊ฒฐ๊ทธ๋ํ์ผ ๋, ์๋๋ ๋ชจ๋ ๋์น.
G๋ ์ํ๋์ด๋ค.
โ ์์์ ๊ผญ์ง์ u, v์ ๋ํ์ฌ u์์ v๋ก ๊ฐ๋ ์ ์ผํ ๊ฒฝ๋ก๊ฐ ์๋ค.
โ G์์ ์์์ ํ ๋ณ์ ์ ๊ฑฐํ๋ฉด ๋จ์ ๊ทธ๋ํ๋ ์ฐ๊ฒฐ๊ทธ๋ํ๊ฐ ์๋๋ค.
โ G๋ n-1๊ฐ์ ๋ณ์ ๊ฐ์ง๊ณ ์๋ค.
์์ฑ์ํ๋
์ฐ๊ฒฐ๋ ๊ทธ๋ํ์ ํ๋ก๊ฐ ํฌํจ๋ ๊ฒฝ์ฐ ๋ณ์ ์ผ๋ถ ์ ๊ฑฐํ์ฌ ์ํ๋๊ฐ ๋ ๋, ๊ทธ ์ํ๋
- $G(V,E)$์ ๋ถ๋ถ๊ทธ๋ํ $G^{\prime}(V^{\prime},E^{\prime})$์ ๋ํด $V=V^{\prime}$์ด๊ณ , $G^{\prime}$์ด ์ํ๋์ด๋ฉด $G^{\prime}$์ $G$์ ์์ฑ์ํ๋์ด๋ค.
- ์ฐ๊ฒฐ๊ทธ๋ํ์๋ ํญ์ ์์ฑ์ํ๋๊ฐ ์๋ค.
- n๊ฐ์ ๊ผญ์ง์ ์ ๊ฐ๋ ์๋ก ๋ค๋ฅธ ์ํ๋์ ๊ฐ์๋ $n^{n-2}$๊ฐ