ﮔﺮﺍﻑﻫﺎﻯﻣﻨﺘﻈﻢﻭﻛﺎﻣﻞ
ﺣﻤﻴﺪﺭﺿﺎ ﺍﻣﻴﺮﻯ
ﻛﻠﻴﺪ ﻭﺍژﻩﻫﺎ:
ﮔﺮﺍﻑ ﻣﻨﺘﻈﻢ ،ﮔﺮﺍﻑ ﻛﺎﻣﻞ ،ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ ﮔﺮﺍﻑ ﻛﺎﻣﻞ ،ﻣﺴﺎﺋﻞ ﮔﺮﺍﻑ ﻫﺎﻯ ﻛﺎﻣﻞ ﻭ ﻣﻨﺘﻈﻢ
ﮔﺮﺍﻑ ﻛﺎﻣﻞ ﮔﺮﺍﻑ ﻣﻨﺘﻈﻢ
ﮔﺮﺍﻑ ﻫﺎﻯ ﻛﺎﻣﻞ ،ﺩﺳﺘﻪ ﻯ ﺧﺎﺻﻰ ﺍﺯ ﮔﺮﺍﻑ ﻫﺎﻯ ﻣﻨﺘﻈﻢ ﻣﺤﺴﻮﺏ ﺍﮔﺮ ﺩﺭ ﻳﻚ ﮔﺮﺍﻑ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ ،pﺩﺭﺟﻪ ﻯ ﻫﻤﻪ ﻯ ﺭﺃﺱ ﻫﺎ ﺑﺎ ﻫﻢ
2 1
ﻣﻰ ﺷﻮﻧﺪ ﻭ ﻫﻤﺎﻥ ﻃﻮﺭ ﻛﻪ ﺍﺯ ﺍﺳﻢ ﺁﻥ ﻫﺎ ﻣﻰ ﺗﻮﺍﻥ ﺩﺭﻳﺎﻓﺖ ،ﮔﺮﺍﻑ ﻫﺎﻳﻰ ﺑﺮﺍﺑﺮ ﺑﺎﺷﻨﺪ ،ﭼﻨﻴﻦ ﮔﺮﺍﻓﻰ ﻣﻨﺘﻈﻢ ﺍﺳﺖ ﻭ ﺍﮔﺮ ﺩﺭﺟﻪﻱ ﺭﺃﺱﻫﺎ ﺑﺮﺍﺑﺮ ﺑﺎ
ﻫﺴﺘﻨﺪ ﻛﻪ ﺍﻧﺪﺍﺯﻩ ﻯ ﺁﻥ ﻫﺎ ﻛﺎﻣﻞ ﺍﺳﺖ .ﮔﺮﺍﻑ ﻛﺎﻣﻞ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ pﻛﻪ ﺑﺎ ﻋﺪﺩ ﺣﺴﺎﺑﻰِ rﺑﺎﺷﻨﺪ ،ﺁﻥ ﺭﺍ ﮔﺮﺍﻑ -rﻣﻨﺘﻈﻢ ﻣﻰ ﻧﺎﻣﻴﻢ .ﺑﻪ ﺑﻴﺎﻥ ﺩﻳﮕﺮ،
ﺭﺃﺱ ﺁﻥ )(p-1 Kpﻧﻤﺎﻳﺶ ﺩﺍﺩﻩ ﻣﻰ ﺷﻮﺩ ،ﮔﺮﺍﻓﻰ ﺍﺳﺖ ﻛﻪ ﺩﺭﺟﻪ ﻯ ﻫﺮ ِ ﺍﮔﺮ ﺑﺰﺭگ ﺗﺮﻳﻦ ﺩﺭﺟﻪ ﻯ ﺭﺋﻮﺱ ﻳﻚ ﮔﺮﺍﻑ ﺭﺍ ﻣﺎﻛﺰﻳﻤﻢ ﺩﺭﺟﻪ ﻯ ﮔﺮﺍﻑ
ﺑﺎﺷﺪ .ﺑﻪ ﻋﺒﺎﺭﺕ ﺩﻳﮕﺮ» ،ﻫﺮ ﮔﺮﺍﻑ ) - (p-1ﻣﻨﺘﻈﻢ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ pﺭﺍ ﻭ ﻛﻮﭼﻚ ﺗﺮﻳﻦ ﺩﺭﺟﻪ ﻯ ﺭﺋﻮﺱ ﻳﻚ ﮔﺮﺍﻑ ﺭﺍ ﻣﻴﻨﻰ ﻣﻢ ﺩﺭﺟﻪ ﻯ ﮔﺮﺍﻑ
ﻛﺎﻣﻞ ﻣﻰ ﮔﻮﻳﻴﻢ« .ﺑﻨﺎﺑﺮﺍﻳﻦ ﺩﺭ ﻫﺮ ﮔﺮﺍﻑ ﻛﺎﻣﻞ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ Pﺩﺍﺭﻳﻢ: ﺑﻨﺎﻣﻴﻢ ،ﻭ ﺁﻥ ﻫﺎ ﺭﺍ ﺑﻪ ﺗﺮﺗﻴﺐ ﺑﺎ Δﻭ δﻧﻤﺎﻳﺶ ﺩﻫﻴﻢ ،ﺩﺍﺭﻳﻢ:
r = p −1 G ⇔ Δ = δ = rﮔﺮﺍﻓﻰ -rﻣﻨﺘﻈﻢ ﺍﺳﺖ.
rp = 2q ⇒ p(p − 1) = 2q ﺍﺯ ﻃﺮﻑ ﺩﻳﮕﺮ ،ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﻗﻀﻴﻪ ﻯ ﻛﺘﺎﺏ ﺩﺭﺳﻰ ﻛﻪ ﺑﻴﺎﻥ ﻣﻰ ﻛﻨﺪ:
)p(p − 1 »ﻣﺠﻤﻮﻉ ﺩﺭﺟﺎﺕ ﺭﺋﻮﺱ ﻳﻚ ﮔﺮﺍﻑ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ pﻭ ﺍﻧﺪﺍﺯﻩ ﻯq 3
=⇒q
2 ﻫﻤﻮﺍﺭﻩ ﺩﻭ ﺑﺮﺍﺑﺮ ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ ﺁﻥ ﮔﺮﺍﻑ ﺍﺳﺖ« ،ﻣﻰ ﺗﻮﺍﻥ ﻧﺘﻴﺠﻪ ﮔﺮﻓﺖ
ﻫﻤﺎﻥ ﻃﻮﺭ ﻛﻪ ﻣﻼﺣﻈﻪ ﻣﻰ ﻛﻨﻴﺪ q ،ﺣﺪﺍﻛﺜﺮ ﻣﻘﺪﺍﺭ ﺧﻮﺩ ﺭﺍ ﺩﺍﺭﺩ .ﺯﻳﺮﺍ
ﻛﻪ »ﺩﺭ ﻫﺮ ﮔﺮﺍﻑ -rﻣﻨﺘﻈﻢ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ pﻭ ﺍﻧﺪﺍﺯﻩ ﻯ ، qﻫﻤﻮﺍﺭﻩ ﺩﺍﺭﻳﻢ:
qﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ ﻳﻚ ﮔﺮﺍﻑ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ pﺍﺳﺖ ﻛﻪ ﭼﻮﻥ ﻣﺠﻤﻮﻋﻪ ﻯ
.«pr = 2qﺑﻨﺎﺑﺮﺍﻳﻦ ﺩﺭ ﻫﺮ ﮔﺮﺍﻑ -rﻣﻨﺘﻈﻢ ﺑﺎ ﻣﻔﺮﻭﺽ ِ
ﺑﻮﺩﻥ ،rﻫﻤﻮﺍﺭﻩ
ﻋﻀﻮﻯ ﻣﺠﻤﻮﻋﻪ ﻯِ ﻳﺎﻝ ﻫﺎﻯ ﻳﻚ ﮔﺮﺍﻑ ﺷﺎﻣﻞ ﺯﻳﺮﻣﺠﻤﻮﻋﻪ ﻫﺎﻯ ﺩﻭ
ِ ﺭﺍﺑﻄﻪ ﺍﻯ ﺑﻴﻦ qﻭ pﺑﺮﻗﺮﺍﺭ ﺍﺳﺖ ﻭ ﺍﮔﺮ ﻳﻚ ﻣﻌﺎﺩﻟﻪ ﻯ ﺩﻳﮕﺮ ﺑﺮﺣﺴﺐ
ﻋﻀﻮﻯ ﻳﻚ ﺭﺃﺱ ﻫﺎﻯ ﺁﻥ ﺍﺳﺖ ﻭ ﺗﻌﺪﺍﺩ ﻛﻞ ﺯﻳﺮﻣﺠﻤﻮﻋﻪ ﻫﺎﻯ ﺩﻭ
pﻭ qﻣﻔﺮﻭﺽ ﺑﺎﺷﺪ ،ﺑﺎ ﺣﻞ ﺩﺳﺘﮕﺎﻩ ﺩﻭ ﻣﻌﺎﺩﻟﻪ ،ﺩﻭ ﻣﺠﻬﻮﻝ pﻭ q
⎞⎛p
ﻣﺠﻤﻮﻋﻪ ﻯ pﻋﻀﻮﻯ ﺑﺮﺍﺑﺮ ﺍﺳﺖ ﺑﺎ ، ⎜ ⎟ = p(p −1) :ﭘﺲ qﺩﺭ ﻣﺤﺎﺳﺒﻪ ﻣﻰ ﺷﻮﻧﺪ.
⎟⎜2 2
⎠ ⎝ ﻣﺜﺎﻝ :ﺩﺭ ﻳﻚ ﮔﺮﺍﻑ -4ﻣﻨﺘﻈﻢ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ pﻭ ﺍﻧﺪﺍﺯﻩ ﻯ ،qﺩﺍﺭﻳﻢ:
ﮔﺮﺍﻑ ﻛﺎﻣﻞ ،ﺣﺪﺍﻛﺜﺮ ﺍﺳﺖ. ِ
ﺭﺋﻮﺱ ﺍﻳﻦ ﮔﺮﺍﻑ ﺭﺍ ﺑﻴﺎﺑﻴﺪ. . 5 p − 3 q = −9ﻣﺠﻤﻮﻉ ﺩﺭﺟﺎﺕ
ﻳﻚ ﻧﻜﺘﻪﻯ ﻣﻬﻢ :ﮔﺮﺍﻑﻫﺎﻯ -rﻣﻨﺘﻈﻢ ﺍﺯ ﻣﺮﺗﺒﻪﻯ pﻛﻪ ، r < p-1ﺩﺭ ﺣﻞ:
ﺑﺴﻴﺎﺭﻯ ﺍﺯ ﻣﻮﺍﺭﺩ ﻣﻨﺤﺼﺮ ﺑﻪ ﻓﺮﺩ ﻧﻴﺴﺘﻨﺪ ،ﻭﻟﻰ ﮔﺮﺍﻑ ﻫﺎﻯ ﻛﺎﻣﻞ ﺍﺯ ﻫﺮ ⎧4 p = 2q q =2p
⎨ ⇒ 5 p − 6p = −9 ⇒ p = 9
ﻣﺮﺗﺒﻪ ،ﻣﻨﺤﺼﺮ ﺑﻪ ﻓﺮﺩﻧﺪ .ﺑﺮﺍﻯ ﻣﺜﺎﻝ ،ﮔﺮﺍﻑ ﻫﺎﻯ -2ﻣﻨﺘﻈﻢ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ ⎩5 p − 3 q = −9
9ﺭﺍ ﺭﺳﻢ ﻛﺮﺩﻩ ﺍﻳﻢ ﻛﻪ ﺗﻌﺪﺍﺩ ﺁﻥ ﻫﺎ 4ﻋﺪﺩ ﺍﺳﺖ ،ﺍﻣﺎ ﺗﻌﺪﺍﺩ ﮔﺮﺍﻑﻫﺎﻱ
q = 2p = 2 × 9 = 18
ﻛﺎﻣﻞ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 9ﻓﻘﻂ ﻳﻜﻰ ﺍﺳﺖ. ﻣﺠﻤﻮﻉ ﺩﺭﺟﺎﺕ ﺭﺋﻮﺱ ⇒ 2q = 36
ﻣﺘﻮﺳﻄﻪ
ﺩﻭﺭﻩﻱ ﺑﻴﺴﺘﻢ /ﺷﻤﺎﺭﻩﻱ 1
5
ﭘﺎﻳﻴﺰ 1389
. . .. ...
.. .......
.. .. . ..
. .
. .
. .. . .
.
ﺭﺳﻢ ﻛﻨﻴﺪ.
.
⎧ )p(p − 1
= ⎪q )p(p − 1
⎨ =2 ⇒p ⇒
2
. .
⎪⎩q = p 3 : G2ﻭ 6ﺿﻠﻌﻰ ﻓﺎﻗﺪ ﻗﻄﺮ 9 : G1ﺿﻠﻌﻰ ﺑﺪﻭﻥ ﻗﻄﺮ 4 : G3ﻭ 5ﺿﻠﻌﻰ ﻓﺎﻗﺪ ﻗﻄﺮ
.
.
p≠0
2p = p(p − 1) ⇒ (p − 1) = 2 ⇒ p = 3
.
: G4ﺳﻪ ﺗﺎ 3ﺿﻠﻌﻰ
ﻣﺜﺎﻝ :ﺍﮔﺮ ﮔﺮﺍﻑ Gﺩﺍﺭﺍﻯ 38ﻳﺎﻝ ﺑﺎﺷﺪ ،ﺍﻳﻦ ﮔﺮﺍﻑ ﺣﺪﺍﻗﻞ ﭼﻨﺪ ) G2ﻭ G3ﮔﺮﺍﻑ ﻫﺎﻯ ﺩﻭ ﺑﺨﺸﻰ ﻭ G4ﮔﺮﺍﻑ ﺳﻪ ﺑﺨﺸﻰ ﻫﺴﺘﻨﺪ(.
ﺭﺃﺱ ﺩﺍﺭﺩ؟ ﺗﻤﺮﻳﻦ :ﺗﻌﺪﺍﺩ ﮔﺮﺍﻑ ﻫﺎﻯ -3ﻣﻨﺘﻈﻢ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 12ﺭﺍ ﺑﻴﺎﺑﻴﺪ ﻭ
ﺣﻞ :ﺑﺮﺍﻯ ﭘﺎﺳﺦ ﮔﻮﻳﻰ ﺑﻪ ﺍﻳﻦ ﻧﻮﻉ ﺳﺆﺍﻝ ﻫﺎ ﻛﺎﻓﻰ ﺍﺳﺖ ﻣﺸﺨﺺ ﻛﻨﻴﻢ ﺁﻥ ﻫﺎ ﺭﺍ ﺭﺳﻢ ﻛﻨﻴﺪ) .ﺟﻮﺍﺏ 4 :ﮔﺮﺍﻑ(
ِ
ﮔﺮﺍﻑ ﻛﺎﻣﻞ ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ ﮔﺮﺍﻑ ﻣﻮﺭﺩﻧﻈﺮ ﺑﻴﻦ ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ ﻛﺪﺍﻡ ﺩﻭ ﺩﺭ ﺟﺪﻭﻝ ﺯﻳﺮ ،ﺑﻪ ﺩﻟﻴﻞ ﺍﻫﻤﻴﺖ ﻭ ﻣﻮﺍﺭﺩ ﺍﺳﺘﻔﺎﺩﻩ ﻯ ﺑﺴﻴﺎﺭ ،ﺗﻌﺪﺍﺩ
⎞ ⎛9 ⎞⎛10
ﻗﺮﺍﺭ ﺩﺍﺭﺩ! ﺩﺭ ﺍﻳﻦ ﻣﺜﺎﻝ ﺩﺍﺭﻳﻢ . ⎜ ⎟ < 38 < ⎜ ⎟ :ﺑﻪ ﻋﺒﺎﺭﺕ ﺩﻳﮕﺮ، ﻳﺎﻝ ﻫﺎﻯ ﮔﺮﺍﻑ ﻫﺎﻯ ﻛﺎﻣﻞ ﺍﺯ K1ﺗﺎ K11ﺁﻣﺪﻩ ﺍﺳﺖ:
⎟⎜2 ⎟⎜2
⎠ ⎝ ⎠ ⎝
ﺑﺎ 9ﺭﺃﺱ ﺣﺪﺍﻛﺜﺮ 36ﻳﺎﻝ ﻣﻰ ﺗﻮﺍﻥ ﺗﻌﺮﻳﻒ ﻛﺮﺩ .ﻟﺬﺍ ﺑﺮﺍﻯ ﺗﻌﺮﻳﻒ ﺩﻭ ⎞ p(p − 1) ⎛ p
KP ﮔﺮﺍﻑ =q ⎟ ⎜=
ﺭﺃﺱ ﺩﻳﮕﺮ ﻧﻴﺎﺯ ﺩﺍﺭﻳﻢ .ﭘﺲ ﺟﻮﺍﺏ ﺍﻳﻦ ﺳﺆﺍﻝ ﻳﺎﻝ ﺩﻳﮕﺮ ،ﺑﻪ ﺣﺪﺍﻗﻞ ﻳﻚ ِ 2 ⎟⎜2 )ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎ(
⎠ ⎝
ﻋﺪﺩ 10ﺍﺳﺖ .ﺩﺭ ﻭﺍﻗﻊ ﮔﺮﺍﻑ Gﺑﺎ ﻧﺰﺩﻳﻚ ﺗﺮﻳﻦ ﮔﺮﺍﻑ ﻛﺎﻣﻞ ﺍﺯ ﻧﻈﺮ K1 0
ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻣﻘﺎﻳﺴﻪ ﺷﺪ.
⎞⎛2
ﻛﺮﺩﻥ ﻳﻚ ﮔﺮﺍﻑ ﺑﺎ ﮔﺮﺍﻑ ﻛﺎﻣﻞِ ﻧﺰﺩﻳﻚ ﺑﻪ ﺁﻥ،ِ ﺗﺬﻛﺮ ﻣﻬﻢ :ﻣﻘﺎﻳﺴﻪ K2 ⎜ ⎟ =1
⎟⎜2
⎠ ⎝
ﺭﻭﺷﻰ ﺍﺳﺖ ﻛﻪ ﻣﺴﺎﺋﻞ ﺩﻳﮕﺮﻯ ﺭﺍ ﻧﻴﺰ ﻣﻰ ﺗﻮﺍﻥ ﺗﻮﺳﻂ ﺁﻥ ﺣﻞ ﻛﺮﺩ.
⎞ ⎛3
ﭼﻮﻥ ﮔﺮﺍﻑ ﻫﺎﻯ ﻛﺎﻣﻞ ﮔﺮﺍﻑ ﻫﺎﻯ ﺧﺎﺹ ﻭ ﻣﻨﺤﺼﺮ ﺑﻪ ﻓﺮﺩﻯ ﻫﺴﺘﻨﺪ، K3 ⎜ ⎟=3
⎟⎜2
⎠ ⎝
ﺣﺬﻑ ﻳﻚ ﻳﺎ ﭼﻨﺪ ﻳﺎﻝ ﺍﺯ ﻳﻚ ﮔﺮﺍﻑ ﻛﺎﻣﻞ ﻣﻰ ﺗﻮﺍﻧﺪ ﺭﺍﻩ ﮔﺸﺎ ِ ﮔﺎﻫﻰ
ﺑﺎﺷﺪ .ﺑﻪ ﻣﺜﺎﻝ ﻫﺎﻯ ﺯﻳﺮ ﺗﻮﺟﻪ ﻛﻨﻴﺪ: ⎞ ⎛4
⎜ ⎟ =6
K4 ⎟⎜2
ﻣﺜﺎﻝ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 9ﺩﺍﺭﺍﻯ 35ﻳﺎﻝ ﺍﺳﺖ ،ﺍﻳﻦ ﮔﺮﺍﻑ ﭼﻨﺪ ⎠ ⎝
ﺭﺃﺱ ﺍﺯ ﺩﺭﺟﻪ ﻯ ) 8ﺍﺯ ﺩﺭﺟﻪ ﻯ ﻣﺎﻛﺰﻳﻤﻢ( ﻭ ﭼﻨﺪ ﺭﺃﺱ ﺍﺯ ﺩﺭﺟﻪﻱ ⎞ ⎛5
⎜ ⎟ = 10
⎟⎜2
ﻣﻴﻨﻰ ﻣﻢ ﺩﺍﺭﺩ؟ K5
⎠ ⎝
ﺣﻞ :ﻣﻰ ﺩﺍﻧﻴﻢ K9ﺩﺍﺭﺍﻯ 36ﻳﺎﻝ ﺍﺳﺖ ،ﻟﺬﺍ ﺍﮔﺮ ﻳﻚ ﻳﺎﻝ ﺍﺯ K9 ⎞ ⎛6
⎜ ⎟ = 15
ﺣﺬﻑ ﻛﻨﻴﻢ ،ﮔﺮﺍﻑ Gﺣﺎﺻﻞ ﻣﻰ ﺷﻮﺩ .ﻭﺍﺿﺢ ﺍﺳﺖ ﻛﻪ ﺍﮔﺮ ﺍﺯ K9 K6 ⎟⎜2
⎠ ⎝
ﺭﺃﺱ ﺁﻥ ﺁﺳﻴﺐ ﻣﻰ ﺑﻴﻨﻨﺪ ﻭ ﺍﺯ ﺩﺭﺟﻪ ﻯ 8ﺑﻪﻳﻚ ﻳﺎﻝ ﺣﺬﻑ ﺷﻮﺩ ،ﺩﻭ ِ
⎞⎛7
ﺩﺭﺟﻪ ﻯ 7ﺗﻨ ّﺰﻝ ﭘﻴﺪﺍ ﻣﻰ ﻛﻨﻨﺪ ! ﺑﻨﺎﺑﺮﺍﻳﻦ ،ﮔﺮﺍﻑ Gﺩﺍﺭﺍﻯ 9 - 2 = 7 K7 ⎜ ⎟ = 21
⎟⎜2
⎠ ⎝
ﺭﺃﺱ ﺍﺯ ﺩﺭﺟﻪ ﻯ ﻣﺎﻛﺰﻳﻤﻢ ﻭ ﺩﻭ ﺭﺃﺱ ﺍﺯ ﺩﺭﺟﻪ ﻯ ﻣﻴﻨﻰ ﻣﻢ ﺩﺍﺭﺩ.
⎞ ⎛8
ﻣﺜﺎﻝ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 8ﺩﺍﺭﺍﻯ 26ﻳﺎﻝ ﺍﺳﺖ .ﺍﻳﻦ ﮔﺮﺍﻑ ⎜ ⎟ = 28
K8 ⎟⎜2
⎠ ⎝
ﺣﺪﺍﻗﻞ ﻭ ﺣﺪﺍﻛﺜﺮ ﭼﻨﺪ ﺭﺃﺱ ﺍﺯ ﺩﺭﺟﻪ ﻯ ﻣﺎﻛﺰﻳﻤﻢ ﺍﺳﺖ؟
ﺣﻞ :ﺩﺭ ﺍﻳﻦ ﻣﺜﺎﻝ ﺑﺎﻳﺪ 2ﻳﺎﻝ ﺍﺯ ﮔﺮﺍﻑ K8ﺣﺬﻑ ﻛﻨﻴﻢ ﺗﺎ ﮔﺮﺍﻑ ⎞ ⎛9
⎜ ⎟ = 36
K9 ⎟⎜2
Gﺣﺎﺻﻞ ﺷﻮﺩ .ﺣﺬﻑ ﺍﻳﻦ ﺩﻭ ﻳﺎﻝ ﺑﻪ ﺩﻭ ﺻﻮﺭﺕ ﺍﻣﻜﺎﻥ ﭘﺬﻳﺮ ﺍﺳﺖ :ﻳﺎ ⎠ ⎝
ﻫﺮ ﺩﻭ ﻳﺎﻝ ﺭﺍ ﺍﺯ ﻳﻚ ﺭﺃﺱ ﺣﺬﻑ ﻛﻨﻴﻢ ) 3ﺭﺃﺱ ﺁﺳﻴﺐ ﻣﻰ ﺑﻴﻨﺪ( ،ﻭ ﻳﺎ ⎞⎛10
⎜ ⎟ = 45
ﺩﻭ ﻳﺎﻝ ﺭﺍ ﻃﻮﺭﻯ ﺣﺬﻑ ﻛﻨﻴﻢ ﻛﻪ ﺭﺃﺱ ﻣﺸﺘﺮﻙ ﻧﺪﺍﺷﺘﻪ ﺑﺎﺷﻨﺪ ) 4ﺭﺃﺱ K10 ⎟⎜2
⎠ ⎝
ﺁﺳﻴﺐ ﻣﻰ ﺑﻴﻨﺪ(. ⎞⎛11
⎜ ⎟ = 55
ﺩﺭ ﺣﺎﻟﺖ ﺍﻭﻝ ﺍﺯ ﻳﻚ ﺭﺃﺱ ﺩﻭ ﺩﺭﺟﻪ ﻭ ﺍﺯ ﺩﻭ ﺭﺃﺱ ﺩﻳﮕﺮ ﻫﺮﻛﺪﺍﻡ K11 ⎟⎜2
⎠ ⎝
ﺭﺃﺱ ﻣﺎﻛﺰﻳﻤﻢ )ﺍﺯ ﺩﺭﺟﻪ ﻯ (7 1ﺩﺭﺟﻪ ﻛﻢ ﻣﻰ ﺷﻮﺩ ﻭ ﮔﺮﺍﻓﻰ ﺩﺍﺭﺍﻯ ِ 5
ﻭ 1ﺭﺃﺱ ﻣﻴﻨﻰ ﻣﻢ )ﺍﺯ ﺩﺭﺟﻪ ﻯ (5ﺧﻮﺍﻫﻴﻢ ﺩﺍﺷﺖ. ﻣﺜﺎﻝ :ﺩﺭ ﮔﺮﺍﻑ ﻛﺎﻣﻞ ،Kpﺍﮔﺮ ﺩﺍﺷﺘﻪ ﺑﺎﺷﻴﻢ ، p = q :ﺍﻳﻦ ﮔﺮﺍﻑ ﺭﺍ
6 ﻣﺘﻮﺳﻄﻪ
ﺩﻭﺭﻩﻱ ﺑﻴﺴﺘﻢ /ﺷﻤﺎﺭﻩﻱ 1
ﭘﺎﻳﻴﺰ 1389
ﮔﺮﺍﻑ ← G ﺩﺭ ﺣﺎﻟﺖ ﺩﻭﻡ ﻧﻴﺰ ﺗﻌﺪﺍﺩ ﺭﺃﺱ ﻫﺎﻯ ﻣﺎﻛﺰﻳﻤﻢ )ﺍﺯ ﺩﺭﺟﻪ ﻯ (7ﺑﺮﺍﺑﺮ
....K8
ﻣﺜﺎﻝ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 14ﺩﺍﺭﺍﻯ ﭼﻬﺎﺭ ﺑﺨﺶ ﺍﺳﺖ ﻭ ﺩﺍﺭﻳﻢ:
ﺍﺳﺖ ﺑﺎ 4 . 8-4 = 4 :ﺭﺃﺱ ﻧﻴﺰ ﺍﺯ ﺩﺭﺟﻪ ﻯ ﻣﻴﻨﻰ ﻣﻢ )ﺍﺯ ﺩﺭﺟﻪ ﻯ (6
ﺩﺭ ﮔﺮﺍﻑ ﻣﻮﺟﻮﺩ ﺍﺳﺖ.
.δ = 1ﺍﻳﻦ ﮔﺮﺍﻑ ﺣﺪﺍﻛﺜﺮ ﭼﻨﺪ ﻳﺎﻝ ﺩﺍﺭﺩ؟ ﻣﺜﺎﻝ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 10ﺩﺍﺭﺍﻯ 42ﻳﺎﻝ ﺍﺳﺖ .ﺍﮔﺮ ﺩﺭ ﺍﻳﻦ
ﮔﺮﺍﻑ ﺩﺍﺷﺘﻪ ﺑﺎﺷﻴﻢ ،(Δ - δ) = 1 :ﺩﺭ ﺍﻳﻦ ﺻﻮﺭﺕ ﮔﺮﺍﻑ Gﭼﻨﺪ ﺭﺃﺱ
ﺣﻞ :ﮔﺮﺍﻑ Gﻃﺒﻖ ﻓﺮﺽ ﺭﺃﺱ ﺍﻳﺰﻭﻟﻪ ﻧﺪﺍﺭﺩ ﻭ ﺑﻪ ﺻﻮﺭﺕ ﺯﻳﺮ ﻣﺎﻛﺰﻯ ﻣﻢ ﻭ ﭼﻨﺪ ﺭﺃﺱ ﻣﻴﻨﻰ ﻣﻢ ﺩﺍﺭﺩ؟
ﺍﺳﺖ. ﺣﻞ :ﺑﺪﻳﻬﻰ ﺍﺳﺖ ﻛﻪ ﺍﮔﺮ ﺍﺯ K10ﻛﻪ 45ﻳﺎﻝ ﺩﺍﺭﺩ 3 ،ﻳﺎﻝ ﺣﺬﻑ
.. .
→ K8ﮔﺮﺍﻑ G
. .. ﻛﻨﻴﻢ ،ﮔﺮﺍﻓﻲ ﺑﺎ ﺗﻌﺪﺍﺩ ﻳﺎﻝﻫﺎﻱ ﺑﺮﺍﺑﺮ ﺑﺎ Gﺑﻪﺩﺳﺖ ﻣﻰﺁﻳﺪ .ﺍﻣﺎ ﭼﻮﻥ
ﻃﺒﻖ ﻓﺮﺽ ، Δ - δ = 1ﺣﺬﻑ ﺍﻳﻦ ﺳﻪ ﻳﺎﻝ ﺑﺎﻳﺪ ﺑﻪﮔﻮﻧﻪﺍﻯ ﺑﺎﺷﺪ ﻛﻪ ﺍﺯ
ﻫﻴﭻ ﺭﺃﺳﻰ ﺩﻭ ﻳﺎﻝ ﺣﺬﻑ ﻧﺸﻮﺩ .ﺯﻳﺮﺍ ﺩﺭ ﺍﻳﻦﺻﻮﺭﺕ ﺧﻮﺍﻫﻴﻢ ﺩﺍﺷﺖ2 :
⎞ ⎛8
: ⎜ ⎟ + 3 = 31ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ G = Δ - δﻛﻪ ﺧﻼﻑ ﻓﺮﺽ ﺍﺳﺖ .ﭘﺲ ﺳﻪ ﻳﺎﻝ ﺣﺬﻑ ﺷﺪﻩ ﻧﺒﺎﻳﺪ ﺭﺃﺱ
⎟⎜2
⎠ ⎝ ﻣﺸﺘﺮﻙ ﺩﺍﺷﺘﻪ ﺑﺎﺷﻨﺪ ﻛﻪ ﺩﺭ ﺍﻳﻦﺻﻮﺭﺕ ،ﺩﺭﺟﻪﻯ 6ﻳﺎﻝ ﻫﺮﻛﺪﺍﻡ 1ﺩﺭﺟﻪ
ﻣﺜﺎﻝ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 18ﺩﺍﺭﺍﻯ ﺳﻪ ﺑﺨﺶ ﺍﺳﺖ .ﺍﮔﺮ ﺩﺭ ﻛﺎﻫﺶ ﻣﻰﻳﺎﺑﺪ ﻭ 10-6 = 4ﺭﺃﺱ ﺍﺯ ﺩﺭﺟﻪﻯ ﻣﺎﻛﺰﻳﻤﻢ )ﺍﺯ ﺩﺭﺟﻪﻯ (9ﻭ
ﺍﻳﻦ ﮔﺮﺍﻑ ﺩﺍﺷﺘﻪ ﺑﺎﺷﻴﻢ ،δ = 2 :ﺩﺭ ﺍﻳﻦ ﺻﻮﺭﺕ Gﺣﺪﺍﻛﺜﺮ ﭼﻨﺪ ﻳﺎﻝ 6ﺭﺃﺱ ﺍﺯ ﺩﺭﺟﻪﻯ ﻣﻴﻨﻰﻣﻢ )ﺍﺯ ﺩﺭﺟﻪﻯ (8ﺩﺭ ﮔﺮﺍﻑ Gﻣﻮﺟﻮﺩ ﺍﺳﺖ.
ﻣﻰ ﺗﻮﺍﻧﺪ ﺑﺎﺷﺪ؟ ﺗﻤﺮﻳﻦ :ﻣﺜﺎﻝ ﻗﺒﻞ ﺭﺍ ﺑﺎ ﻓﺮﺽ Δ - δ = 2ﺣﻞ ﻛﻨﻴﺪ.
ﺣﻞ :ﻃﺒﻖ ﻓﺮﺽ ،ﮔﺮﺍﻑ Gﺭﺃﺱ ﺍﻳﺰﻭﻟﻪ ﻭ ﺭﺃﺱ ﺍﺯ ﺩﺭﺟﻪ ﻯ ﻳﻚ ﺗﺬﻛﺮ ﻣﻬﻢ :ﻳﻜﻰ ﺩﻳﮕﺮ ﺍﺯ ﻛﺎﺭﺑﺮﺩﻫﺎﻯ ﮔﺮﺍﻑ ﻫﺎﻯ ﻛﺎﻣﻞ ﺩﺭ ﺗﻌﻴﻴﻦ
ﻧﺪﺍﺭﺩ ﻭ ﺑﺎﻳﺪ ﺑﻪ ﺷﻜﻞ ﺯﻳﺮ ﺑﺎﺷﺪ: ﻣﺎﻛﺰﻳﻤﻢ ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ ﻳﻚ ﮔﺮﺍﻑ ﭼﻨﺪﺑﺨﺸﻰ ﺍﺳﺖ ﻛﻪ ﺩﺭ ﻣﺜﺎﻝ ﻫﺎﻯ
.. .
..
ﮔﺮﺍﻑ K12 ← G ﺯﻳﺮ ﺑﻪ ﺁﻥ ﻣﻰ ﭘﺮﺩﺍﺯﻳﻢ.
ﻣﺜﺎﻝ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 7ﮔﺮﺍﻓﻰ ﺩﻭ ﺑﺨﺸﻰ ﺍﺳﺖ .ﺍﻳﻦ ﮔﺮﺍﻑ
⎞ ⎛12
: ⎜ ⎟ + 6 = 66 + 6 = 72ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ G ﺣﺪﺍﻛﺜﺮ ﭼﻨﺪ ﻳﺎﻝ ﻣﻰ ﺗﻮﺍﻧﺪ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ؟
⎟⎜2
⎠ ⎝ ﺣﻞ :ﺗﻮﺟﻪ ﺩﺍﺭﻳﻢ ﻛﻪ ﺭﺃﺱ ﺍﻳﺰﻭﻟﻪ ﻳﺎ ﺗﻨﻬﺎ ،ﻳﻚ ﺑﺨﺶ ﻣﺤﺴﻮﺏ
ﻫﺮ ﻳﻚ ﺩﻭ ﺑﺨﺸﻰ ﻫﺴﺘﻨﺪ. ﻣﻰ ﺷﻮﺩ .ﺑﺮﺍﻯ ﻣﺜﺎﻝ ،ﮔﺮﺍﻑ ﻫﺎﻯ ﻭ
...
ﻣﺜﺎﻝ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ P1ﺩﺍﺭﺍﻯ Kﺑﺨﺶ ﺍﺳﺖ .ﺍﮔﺮ ﺩﺭ
.
ﺍﻳﻦ ﮔﺮﺍﻑ ﺩﺍﺷﺘﻪ ﺑﺎﺷﻴﻢ ،δ = P2 :ﺩﺭ ﺍﻳﻦ ﺻﻮﺭﺕ Gﺣﺪﺍﻛﺜﺮ ﭼﻨﺪ ﻳﺎﻝ ﺩﺭ ﺍﻳﻦ ﻣﺜﺎﻝ ﺍﮔﺮ ﺑﺨﻮﺍﻫﻴﻢ ﮔﺮﺍﻓﻰ ﺩﻭﺑﺨﺸﻰ ﺑﺎ 7ﺭﺃﺱ ﻭ ﺣﺪﺍﻛﺜﺮ ﻳﺎﻝ
ﻣﻰ ﺗﻮﺍﻧﺪ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ؟ ﺩﺍﺷﺘﻪ ﺑﺎﺷﻴﻢ ،ﻛﺎﻓﻰ ﺍﺳﺖ ﻳﻚ ﺭﺃﺱ ﺍﺯ 7ﺭﺃﺱ ﺭﺍ ﺍﻳﺰﻭﻟﻪ ﻛﻨﻴﻢ ﻭ ﺑﺎ 6
ﺣﻞ :ﮔﺮﺍﻑ Gﺑﺎﻳﺪ ﺩﺍﺭﺍﻯ ) (K-1ﺑﺨﺶ ﺑﺎ ﺣﺪﺍﻛﺜﺮ ﻳﺎﻝ ﻭ δ = P2 ⎞ ⎛6
⎜ ⎟ = 15 ﺭﺃﺱ ﺩﻳﮕﺮ ﻳﻚ ﮔﺮﺍﻑ ﻛﺎﻣﻞ ) (K6ﺑﺴﺎﺯﻳﻢ .ﺩﺭ ﺍﻳﻦ ﺣﺎﻟﺖ
ِ
ﺑﺨﺶ ﺑﺎﺷﺪ ﻛﻪ ) (K-1ﮔﺮﺍﻑ ﻛﺎﻣﻞ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ) (P2 + 1ﺍﺳﺖ ﻭ ﻳﻚ ⎟⎜2
⎠ ⎝
ﻛﺎﻣﻞ ﺍﺯ ﻣﺮﺗﺒﻪ ﻯ ﺭﺃﺱ ﻫﺎﻱ ﺑﺎﻗﻰ ﻣﺎﻧﺪﻩ ﻛﻪ ﺗﻌﺪﺍﺩ ﺭﺃﺱ ﻫﺎﻯ ﺑﺎﻗﻰ ﻣﺎﻧﺪﻩ ﻳﺎﻝ ﺑﺮﺍﻯ ﮔﺮﺍﻑ ﺣﺎﺻﻞ ﻣﻰ ﺷﻮﺩ ﻛﻪ ﺍﻳﻦ ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻣﺎﻛﺰﻳﻤﻢ ﺧﻮﺍﻫﺪ
ﺑﺮﺍﺑﺮ ﺍﺳﺖ ﺑﺎ:
] )P = P1 − [(K − 1) × (P2 + 1 ﺑﻮﺩ.
ﺗﻤﺮﻳﻦ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 10ﺍﺯ ﺳﻪ ﺑﺨﺶ ﺗﺸﻜﻴﻞ ﻳﺎﻓﺘﻪ ﺍﺳﺖ.
ِ
ﮔﺮﺍﻑ Kﺑﺨﺸﻰ ﺑﺮﺍﺑﺮ ﺍﺳﺖ ﺑﺎ: ﺣﺪﺍﻛﺜﺮ ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ ﭼﻨﻴﻦ ⎞ ⎛8
ﺍﻳﻦ ﮔﺮﺍﻑ ﺣﺪﺍﻛﺜﺮ ﭼﻨﺪ ﻳﺎﻝ ﺩﺍﺭﺩ؟ )ﺟﻮﺍﺏ( ⎜ ⎟ = 28 :
⎟⎜2
⎞⎛P ⎞⎛ P2 + 1 ⎠ ⎝
⎜ × ) : ⎜ ⎟ + (K − 1ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ G ⎟ ﻣﺜﺎﻝ :ﮔﺮﺍﻑ Gﺍﺯ ﻣﺮﺗﺒﻪ ﻯ 12ﻓﻘﻂ ﺩﺍﺭﺍﻯ ﺩﻭ ﺭﺃﺱ ﺍﻳﺰﻭﻟﻪ ﺍﺳﺖ
⎟⎜2 ⎟ ⎜ 2
⎠ ⎝ ⎝ ⎠
ﻭ ﺍﺯ ﭼﻬﺎﺭ ﺑﺨﺶ ﺗﺸﻜﻴﻞ ﻳﺎﻓﺘﻪ ﺍﺳﺖ .ﺍﻳﻦ ﮔﺮﺍﻑ ﺣﺪﺍﻛﺜﺮ ﭼﻨﺪ ﻳﺎﻝ
ﺗﻤﺮﻳﻦ :ﺍﺯ ﮔﺮﺍﻑ ﻫﺎﻯ ﻛﺎﻣﻞ ﺑﺮﺍﻯ ﺑﻪ ﺩﺳﺖ ﺁﻭﺭﺩﻥ ﺷﺮﻁ ﻫﻢ ﺑﻨﺪﻯ ﻭ ﻣﻰ ﺗﻮﺍﻧﺪ ﺩﺍﺷﺘﻪ ﺑﺎﺷﺪ؟
ﻧﺎﻫﻢ ﺑﻨﺪﻯ ﭼﮕﻮﻧﻪ ﻣﻰ ﺗﻮﺍﻥ ﺍﺳﺘﻔﺎﺩﻩ ﻛﺮﺩ؟ ﺣﻞ :ﺍﺯ ِ 12
ﺭﺃﺱ ﮔﺮﺍﻑ ،Gﺩﻭ ﺭﺃﺱ ﺭﺍ ﺑﻪ ﺻﻮﺭﺕ ﺍﻳﺰﻭﻟﻪ ﻛﻨﺎﺭ
ﭘﻲﻧﻮﺷﺖ
.1ﻣﺮﺗﺒﻪ ﻯ ﮔﺮﺍﻑ :ﺗﻌﺪﺍﺩ ﺭﺃﺱ ﻫﺎﻯ ﻳﻚ ﮔﺮﺍﻑ ﺭﺍ ﻣﺮﺗﺒﻪ ﻯ ﺁﻥ ﮔﺮﺍﻑ ﻣﻰ ﮔﻮﻳﻴﻢ.
ﻣﻰ ﮔﺬﺍﺭﻳﻢ ﻭ ﺑﻴﻦ ﺩﻭ ﺭﺃﺱ ﺩﻳﮕﺮ ﻳﻚ ﻳﺎﻝ ﺭﺳﻢ ﻣﻰ ﻛﻨﻴﻢ ﻭ ﺑﺎ 8ﺭﺃﺱ
.2ﺩﺭﺟﻪ ﻯ ﻳﻚ ﺭﺃﺱ :ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻳﻰ ﻛﻪ ﺍﺯ ﻳﻚ ﺭﺃﺱ ﻋﺒﻮﺭ ﻣﻰ ﻛﻨﻨﺪ ،ﺩﺭﺟﻪ ﻯ ﺁﻥ ﺑﺎﻗﻰ ﻣﺎﻧﺪﻩ ،ﻳﻚ ﮔﺮﺍﻑ ﻛﺎﻣﻞ ﺗﺸﻜﻴﻞ ﻣﻰ ﺩﻫﻴﻢ .ﺩﺭ ﺍﻳﻦ ﺣﺎﻟﺖ ،ﮔﺮﺍﻑ G
ﺭﺃﺱ ﻧﺎﻣﻴﺪﻩ ﻣﻰ ﺷﻮﺩ. ⎞ ⎛8
ﺩﺍﺭﺍﻯ ﻣﺎﻛﺰﻳﻤﻢ ﺗﻌﺪﺍﺩ ﻳﺎﻝ ،ﻳﻌﻨﻰ ⎜ ⎟ + 1 = 29ﻳﺎﻝ ﺍﺳﺖ.
.3ﺍﻧﺪﺍﺯﻩ ﻯ ﮔﺮﺍﻑ :ﺗﻌﺪﺍﺩ ﻳﺎﻝ ﻫﺎﻯ ﻳﻚ ﮔﺮﺍﻑ ﺭﺍ ﺍﻧﺪﺍﺯﻩ ﻯ ﺁﻥ ﮔﺮﺍﻑ ﻣﻰ ﮔﻮﻳﻴﻢ. ⎟⎜2
⎠ ⎝
ﻣﺘﻮﺳﻄﻪ
ﺩﻭﺭﻩﻱ ﺑﻴﺴﺘﻢ /ﺷﻤﺎﺭﻩﻱ 1
7
ﭘﺎﻳﻴﺰ 1389