عدد صفر تحميلي گراف‌ها

اصفهان : دانشگاه صنعتي اصفهان

رياضي

كارشناسي ارشد

يكي از ﭘﺎراﻣﺘﺮﻫﺎي تحميلي ﮔﺮاف،ﻋﺪد ﺻﻔﺮ تحميلي اﺳﺖ ﮐﻪ ﺑﻪ ﺻﻮرت زﯾﺮ ﺗﻌﺮﯾﻒ ميﺷﻮد. اﮔﺮ G يك ﮔﺮاف ﺑﺎﺷﺪ ﮐﻪ ﻫﻤﻪي رأسﻫﺎي آن ﺑﺎ دو رﻧﮓ سياه و ﺳﻔﯿﺪ رﻧﮓآﻣﯿﺰي ﺷﺪه‌اﻧﺪ و u يك رأس سياه از اﯾﻦ ﮔﺮاف ﺑﺎﺷﺪ ﮐﻪ دﻗﯿﻘﺎً داراي يك ﻫﻤﺴﺎﯾﻪي ﺳﻔﯿﺪ مانند v اﺳﺖ، آنﮔﺎه رﻧﮓ v ﺑﻪ سياه ﺗﻐﯿﯿﺮ ﭘﯿﺪا ﮐﺮده و ميﮔﻮﯾﯿﻢ رأس u ، رأس v را تحميل ﮐﺮده اﺳﺖ. اﯾﻦ فرايند، قانون ﺗﻐﯿﯿﺮ رﻧﮓ ﻧﺎﻣﯿﺪه ميﺷﻮد. ﻣﺠﻤﻮﻋﻪي ﺻﻔﺮ تحميلي Z، زﯾﺮﻣﺠﻤﻮﻋﻪاي از رأسﻫﺎي G اﺳﺖ ﺑﻪ ﻃﻮري ﮐﻪ اﮔﺮ اﺑﺘﺪا رأسﻫﺎي درون Z سياه و ﺑﻘﯿﻪي رأسﻫﺎ ﺳﻔﯿﺪ ﺑﺎﺷﻨﺪ، بعد از بكارگيري تعداد متناهي قانون تغيير رنگ، تمام رئوس G ، سياه شوند. عدد ﺻﻔﺮ تحميلي، ﻋﺒﺎرت اﺳﺖ از ﮐﻮچكترﯾﻦ اﻧﺪازه‌ي ﻣﺠﻤﻮﻋﻪي ﺻﻔﺮ تحميلي Z براي گراف G،‌ و ﺑﺎ Z(G) ﻧﺸﺎن داده ميﺷﻮد. در اﯾﻦ ﭘﺎﯾﺎنﻧﺎﻣﻪ، ﻗﺼﺪ دارﯾﻢ ﭘﺎراﻣﺘﺮ تحميلي ﮔﺮاف يعني ﻋﺪد ﺻﻔﺮ تحميلي را مطالعه ﮐﺮده و آن را در ﻣﻮرد ﺧﺎﻧﻮادهﻫﺎي ﻣﺨﺘﻠﻒ ﮔﺮافﻫﺎ ﺑﺮرسي ﮐﻨﯿﻢ و در اداﻣﻪ كرانﻫﺎي عدد صفر تحميلي براي برخي از گرافﻫﺎ بيان كنيم.

215822

رياضي كاربردي (گراف و تركيبيات)

رياضي

دانشگاه صنعتي اصفهان

غلامرضا اميدي، رامين جوادي

بهناز عمومي