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

๊ธฐ๋ณธ ์šฉ์–ด

๊ทธ๋ž˜ํ”„
์ ๊ณผ ์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋„ํ˜• ($G(V,E)$)

๊ทธ๋ž˜ํ”„์˜ ์˜ˆ์‹œ

 
๊ผญ์ง“์ 
๊ทธ๋ž˜ํ”„์—์„œ์˜ ์  (๊ทธ๋ž˜ํ”„์—์„œ ๊ผญ์ง“์  ์ง‘ํ•ฉ: V)
 
๋ณ€
๊ผญ์ง“์ ์„ ์—ฐ๊ฒฐํ•œ ์„  (๊ทธ๋ž˜ํ”„์—์„œ ๋ณ€ ์ง‘ํ•ฉ: E)
 
๊ฐ™์€ ๊ทธ๋ž˜ํ”„์ด๋‹ค.
๊ผญ์ง“์ ์˜ ์œ„์น˜๋ฅผ ๋ฐ”๊พธ๊ฑฐ๋‚˜ ๋ณ€์„ ๊ตฌ๋ถ€๋ฆฌ๊ฑฐ๋‚˜ ๋Š˜์ด๊ฑฐ๋‚˜ ์ค„์—ฌ๋„ ๋‘ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ฐ™์€ ๊ทธ๋ฆผ์œผ๋กœ ๊ทธ๋ฆด ์ˆ˜ ์žˆ๋‹ค.
 
๊ผญ์ง“์ ์˜ ์ฐจ์ˆ˜
๊ทธ๋ž˜ํ”„์—์„œ ํ•œ ๊ผญ์ง“์ ์— ์—ฐ๊ฒฐ๋œ ๋ณ€์˜ ๊ฐœ์ˆ˜
๊ทธ๋ž˜ํ”„์—์„œ ๋ชจ๋“  ๊ผญ์ง“์ ์˜ ์ฐจ์ˆ˜์˜ ํ•ฉ = 2*๋ณ€์˜ ๊ฐœ์ˆ˜
 
์™„์ „๊ทธ๋ž˜ํ”„
์„œ๋กœ ๋‹ค๋ฅธ ๋‘ ๊ผญ์ง“์  ์‚ฌ์ด์— ํ•ญ์ƒ ๋ณ€์ด ์˜ค์ง ํ•œ ๊ฐœ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„ ($K_{n}$)
 
์—ฐ๊ฒฐ๊ทธ๋ž˜ํ”„
์ž„์˜์˜ ์„œ๋กœ ๋‹ค๋ฅธ ๋‘ ๊ผญ์ง“์ ์ด ์—ฐ๊ฒฐ๋œ ๊ทธ๋ž˜ํ”„

๊ฒฝ๋กœ
๊ทธ๋ž˜ํ”„์˜ ํ•œ ๊ผญ์ง“์ ์—์„œ ๋‹ค๋ฅธ ๊ผญ์ง“์ ์œผ๋กœ ์ด๋™ํ•  ๋•Œ, ํ•œ ๋ฒˆ ์ง€๋‚œ ๋ณ€์„ ๋ฐ˜๋ณตํ•˜์ง€ ์•Š์œผ๋ฉด์„œ ์—ฐ๊ฒฐ๋œ ๋ณ€์„ ๋”ฐ๋ผ ์ˆœ์„œ๋Œ€๋กœ ๊ผญ์ง“์ ์„ ๋‚˜์—ดํ•œ ๊ฒƒ
 
๊ฒฝ๋กœ์˜ ๊ธธ์ด
ํ•œ ๊ผญ์ง“์ ์—์„œ ๋‹ค๋ฅธ ๊ผญ์ง“์ ์œผ๋กœ ๊ฐ€๋Š” ๊ฒฝ๋กœ์—์„œ ์ง€๋‚˜๋Š” ๋ณ€์˜ ๊ฐœ์ˆ˜
 
ํšŒ๋กœ
ํ•œ ๊ผญ์ง“์ ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ ์ถœ๋ฐœํ•œ ๊ผญ์ง“์ ์œผ๋กœ ๋Œ์•„์˜ค๋Š” ๊ฒฝ๋กœ
 
์ธ์ ‘ํ–‰๋ ฌ
์–ด๋–ค ๊ทธ๋ž˜ํ”„์˜ ๋‘ ๊ผญ์ง“์ ์ด ํ•œ ๋ณ€์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์œผ๋ฉด 1, ๋ณ€์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€ ์•Š์œผ๋ฉด 0์œผ๋กœ ํ•˜์—ฌ ๊ทธ๋ž˜ํ”„์˜ ๋‘ ๊ผญ์ง“์  ์‚ฌ์ด์˜ ๊ด€๊ณ„๋ฅผ ๋‚˜ํƒ€๋‚ธ ํ–‰๋ ฌ
https://scian.tistory.com/175 

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

์•„๋ž˜ ๊ธ€์„ ๋จผ์ € ๋ณด์‹œ๊ณ  ์˜ค์‹œ๊ธฐ๋ฅผ ์ถ”์ฒœ๋“œ๋ฆฝ๋‹ˆ๋‹ค. https://scian.tistory.com/174 [๊ทธ๋ž˜ํ”„ ์ด๋ก ] ์šฉ์–ด ๋ฐ ๊ธฐ๋ณธ ๊ฐœ๋… ์ •๋ฆฌ๊ธฐ๋ณธ ์šฉ์–ด๊ทธ๋ž˜ํ”„ ์ ๊ณผ ์„ ์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋„ํ˜• ($G(V,E)$) ๊ผญ์ง“์  ๊ทธ๋ž˜ํ”„์—์„œ์˜ ์  (๊ทธ๋ž˜

scian.xyz


์—ฌ๋Ÿฌ ๊ทธ๋ž˜ํ”„

ํ‰๋ฉด๊ทธ๋ž˜ํ”„
ํ‰๋ฉด์—์„œ ๋ณ€๋“ค์ด ๊ผญ์ง“์ ์—์„œ๋งŒ ๊ต์ฐจํ•˜๋Š” ๊ทธ๋ž˜ํ”„
์˜ค์ผ๋Ÿฌ๊ณต์‹: ์—ฐ๊ฒฐ๋œ ํ‰๋ฉด๊ทธ๋ž˜ํ”„์—์„œ $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}$๊ฐœ