18009

15722

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

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

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

1401

هشت،32ص.: نمودار

بهناز عمومي

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

1401/08/04

كتابنامه

رياضي

رياضي

1401/08/22

2873117

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

A dynamic coloring of the vertices of a graph G starts with an initial subset Z of Black vertices, with all remaining vertices being white. For a graph G, the forcing process have define as follows: Let Z ⊆ V (G) be an initial set of vertices. At step zero, each vertex in Z is Black and any other vertex is white. For i ⩾ 1, at step i, each Black vertex v with exactly one white neighbor forces its white neighbor to be Black. At each step i, the set of newly get Black vertices is denoted by Vi that in particular V0 = Z. This process will continiue until there is no more possible change. At the end of the process, the set of Black vertices is called the derived set. A forcing set (zero forcing set) of G is a set Z ⊆ V (G) of initially Black vertices if the corresponding derived set is equal to V (G), i.e., V (G) = S Vi. In this thesis, we investigated the zero forcing number of graphs and its related concepts

بهناز عمومي

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