چكيده

” نمايش تصويري گراف ها چنان قابل فهم و واضح است كه اغلب، شيمي دان ها بي توجه به ساختار جبريشان، آن ها را بررسي مي كنند، اما بديهي است كه آشنايي با نظريه ي گراف ها، براي درك عميق تر ويژگي گراف ها ضروري است. ”

ولادو پريلاگ[1

درك عميق تر اكثر موضوعات، بر پايه ي شناخت ساختار رياضي دستگاه مورد بررسي است، كه گراف ها نيز از اين امر مستثني نيستند. هر چه بيشتر راجع به گراف ها بدانيم، بهتر مي توانيم از آن ها، براي كاربرد هاي شيميايي استفاده كنيم.

در اين پايان نامه، روي يك توصيف گر مولكولي معروف كه از آن به منظور بررسي خصوصيات فيزيكي- شيميايي متعدد مولكول ها، به طور گسترده استفاده مي شود، متمركز مي شويم. هم چنين گراف هاي مولكوليي را در نظر مي گيريم كه مي توانند داراي مقدار اكسترمال اين انديس ويژه باشند.

اولين سؤالي كه مي توان مطرح كرد اين است كه چرا در شيمي، مقادير اكسترمال ثابت هاي رياضي، مورد توجه خاص هستند. شايد براي برخي از خوانندگان حيرت انگيز باشد كه پاسخ اين سؤال، با قديمي ترين و مهم ترين شاخه ي نظريه ي گراف شيميايي، يعني تعداد ايزومر ها، ارتباط عميقي دارد.

اين پايان نامه، از يك طرف مي تواند مورد توجه خوانندگاني باشد كه مي خواهند تحليل اين توصيف گر مولكولي را براي تعدادي از توصيف گر هاي مولكولي ديگر بسط دهند و از طرف ديگر تأكيد مي كند، زمان آن كه شيمي از رياضي اجتناب كند، گذشته است.

” به عقيده ي من، در هر شاخه اي از علوم، رياضي يافت مي شود. ”

ايمانوئل كانت[2]

كلمات كليدي: درجه؛ گراف اكسترمال؛ انديس رانديك؛ انديس همبندي؛ برنامه ريزي خطي

فهرست

مقدمه

فصل1. تعاريف مقدماتي             5

1.1. تعاريف اوليه ي گراف ها                                                                                      6

فصل2. انديس رانديك در درخت ها      11       2.1. تعريف ديگر انديس رانديك             12

مقدار اكسترمال انديس رانديك 14

انديس رانديك در درختاني با دنباله درجه ي مشخص 18

مقدار اكسترمال انديس رانديك در 1Tn,n 19

بررسي انديس رانديك درختان شيميايي به روش برنامه ريزي خطي 28

مقدار اكسترمال انديس رانديك در درختان شيميايي 29

مينيمم انديس رانديك در درختاني با m– تطابق 33

فصل3. انديس رانديك تعميم يافته در درخت ها              40       3.1 مينيمم انديس رانديك تعميم يافته        41

كران خطي براي انديس رانديك تعميم يافته 44

كران پايين دقيق (R1(T       48

كران (Rα(T به ازاي 0<α≤1−       52

3.5درختان شيميايي                                                                                            55

3.5.1 كران دقيق (R1(T                                                                                55

3.5.2 كران بالاي دقيق (Rα(T به ازاي 0>α                                                  63

3.5.3 كران پايين (Rα(T به ازاي 1(,1−)∈α                                                   67

3.6 مينيمم انديس رانديك تعميم يافته در درختاني با m– تطابق                               68

 

فصل4. انديس رانديك (تعميم يافته) مرتبه ي صفر در درخت ها    71       4.1 سه مقدار اول اكسترمال انديس هاي توپولوژيك  72

4.2 دو مقدار اول اكسترمال (Rα(T0 در درختاني با دنباله درجه ي مشخص               75

 

فصل5. رانديك و گراف هاي تك دور                                                                                  77

فهرست

  78                       5.1 مينيمم انديس رانديك تعميم يافته به ازاي (∞+,1−]∈α
  83                       5.2 گراف هاي رده ي Un,k
  87                   5.3 گراف هاي رده ي Unk
  90 فصل6. مسائل باز
  94 مراجع
  98 واژه نامه

فهرست علائم و اختصارات

الف. پارامتر هاي گراف

ماكزيمم درجه ي G)                                                                                         G)∆

عدد رنگي χ(G)                                                                                                  G

مينيمم درجه ي δ(G)                                                                                           G

زير گراف القايي حاصل از رئوس غير برگ درخت C(T)                                                    T

دنباله درجه ي رئوس D(G)                                                                                    G

مجموعه ي همسايه هاي رأس N(u)                                                                           u

انديس رانديك                                                                                                       R

انديس  رانديك تعميم يافته                                                                                     Rα

انديس رانديك مرتبه ي صفر                                                                                    R0

انديس رانديك تعميم يافته ي مرتبه ي صفر                                                                Rα0

مجموعه ي رئوس آويزان V1(T)                                                                                 T

درجه ي رأس d(u)                                                                                               u

فاصله ي بين دو رأس x و d(x, y)                                                                            y

diam(G)                                                                                                     G قطر

g(G)                                                                                                          G كمر

ميانگين فاصله ي بين رئوس l(G)                                                                             G

اندازه (ي گراف m                                                                                                (G

مرتبه (ي گراف n                                                                                                (G

تعداد رئوس درجه ni                                                                                               i

ح

شعاع r(G)                                                                                                         G

wα(uv)                                                                                             uv وزن يال-α

تعداد (i, j)- يال ها                                                                                                xij

 

ب. خانواده ي گراف ها

دور                                                                                                                   Cn

ستاره ي دنباله دار                                                                                        (1CS(n,n

مسير                                                                                                                  Pn

ستاره                                                                                                                 Sn

دو ستاره                                                                                                           Sp,q

مجموعه ي زنجير هاي آويزان درخت P (T)                                                                 T

مجموعه ي درختانn رأسي با 1n رأس آويزان                                                            1Tn,n

مجموعه ي درختان با دنباله درجه ي [ 13,4T 1                                                        [3,2n

مجموعه ي درختان با دنباله درجه ي [14,6T 2                                                       [32,2n

مجموعه ي ستاره هاي تعميم يافته  با 1n رأس آويزان                                                     1Tn

مجموعه ي درختان (1n,3)-منظم                                                                             *1Tn

مجموعه ي گراف هاي تك دور مرتبه n با k رأس آويزان                                             Un,k

مجموعه ي گراف هاي تك دور مرتبه n با k– دور                                                        Unk

 

مقدمه

حدود اواسط قرن پيش، شيمي دانان نظري، متذكر شدند كه ويژگي هاي متنوع ساختار مولكولي

مواد آلي را مي توان با امتحان ثابت هاي ساختاري مناسب گراف مولكولي مربوطه به دست آورد. اين

ثابت هاي گرافي كه براي اهداف شيميايي مفيد هستند ،”انديس هاي توپولوژيك” [3] يا “توصيف گر

هاي ساختار مولكولي” [4] ناميده شدند و كاربرد اصلي آن ها در طراحي QSPR[5] و    QSAR[6]  مي

باشد. در اين جا ،”S” نماد ساختار مولكولي ،”P” نماد خصوصيت فيزيكي يا شيميايي و منظور از “A” ويژگي دارويي، زيستي، سم شناسي و موارد مشابه است و فرض مي شود كه هر دوي “P” و

A” كميت هاي عددپذيرند.

در سال 1975، دانشمند كروات، ميلان رانديك[7]، سعي در ساختن يك مدل رياضي مناسب براي

توضيح شاخه اي از مولكول هاي آلي به ويژه آلكان ها (ساده ترين هيدرو كربني كه فرمول عمومي آن

عبارت است از 2+CnH2n ) داشت. براي اين منظور، رانديك انديس شاخه اي[8] را مطرح كرد كه با (R= R(G نمايش داده مي شود. در اين جا ،G معرف يك گراف مولكولي است، يعني گرافي كه

اسكلت كربن-اتم هيدرو كربن مربوطه را نمايش مي دهد. براي جزئيات گراف هاي مولكولي،[21,52]

را ملاحظه نماييد.

در مطالعات QSPR و QSAR، كميت R از ارزش بالايي برخوردار بوده و كارايي آن از هدف اوليه

ي رانديك (يعني مفهوم شاخه اي) پا فراتر نهاد. بدين سبب، نام R به انديس همبندي [9] يا “انديس همبندي مولكولي [10] يا انديس همبندي رانديك [11] يا انديس رانديك [12] تغيير يافت. در

اين جا از R به عنوان انديس رانديك ياد مي كنيم.

لازم به ذكر است كه در[49]، از نماد χ (خي يوناني)، براي اين انديس استفاده شده و هنوز اين

نماد به طور گسترده در متون شيمي استفاده مي شود. در حالي كه رياضي دانان، نماد R را ترجيح

مي دهند كه منشأ آن بديهي است.

رانديك در [49] متوجه شد كه يك همبستگي خوب بين R و برخي خصوصيات فيزيكي-

شيميايي آلكان ها موجود است، از جمله مي توان به محاسبه ي نقاط جوش، زمان هاي بازداري

كروماتوگرافيك[13]،آنتالپي تشكيل، پارامتر هاي معادله ي آنتوني[14] براي فشار بخار، مساحت رويه ،…

پرداخت . در سال هاي بعد، كاربرد هاي بي شماري از R گزارش شد كه اكثر آن ها مرتبط با زمينه

هاي پزشكي و دارويي بودند. مراجع [18,27,28,48,50] با ديدگاه شيمي، به بررسي R پرداخته اند.

اغراق نيست اگر ادعا كنيم امروزه، انديس رانديك، عمومي ترين و گسترده ترين توصيف گر ساختار

گراف مولكولي است كه براي پيش بيني خصوصيات فيزيكي-شيميايي و مخصوصاً دارويي تركيبات

آلي به كار مي رود. شايسته است عنوان كنيم كه در سال هاي اخير، تلاش هاي زيادي براي يافتن

يك توصيف فيزيكي (يا حداقل يك رابطه) از موفقيت فوق العاده ي انديس رانديك در كاربرد هاي QSPR و QSAR شده است [5,11,12,29,51].

رانديك در مطالعه ي آلكان ها ،توصيف گر ساختاري مربوطه را به ازاي 1−=α معرفي كرد. وي

2

نشان داد اگر براي n ثابت، آلكان ها به گونه اي مرتب شوند كه مقادير 1R  آن ها كاهش يابد، آن 2−

گاه تعداد شاخه هاي آن ها افزايش مي يابد[49]. در سال 1998، بولوباش[15] و اردوش[16]، با   تعويض

1− با هر عدد حقيقي α، اين انديس را تعميم دادند كه به آن انديس رانديك تعميم يافته گويند. به

2

هر حال، مقادير ديگر α نيز بررسي شدند، به ويژه ،1−=α (توسط خود رانديك[49]) و 1+=α (در اين حالت از انديس زاگرب دوم سخن به ميان مي آيد[3,22,44])[17]. به علاوه، توان α، به عنوان يك پارامتر قابل تنظيم، به گونه اي انتخاب مي شود كه خطاي ناشي از مقدار Rα و برخي

ويژگي هاي خاص رده ي انتخابي از تركيبات آلي را بهبود بخشد. براي جزئيات بيشتر [19,23] و

مراجع موجود در آن ها را ملاحظه نماييد.

عليرغم استقبال گسترده ي شيمي دانان از انديس رانديك و با وجود اين كه تعريفش به سادگي

قابل درك است، اين انديس براي مدت طولاني مورد بي توجهي رياضي دانان قرار گرفت. به نظر مي

رسد كه در بيست سال اول پس از انتشار مقاله ي رانديك [49]، تعداد خيلي معدودي رياضي دان

دريافتند كه مسائل نظريه ي R و Rα چقدر مشكل و چقدر جالب هستند. در اين جا تنها متذكر مي

شويم كه برنامه ي فجلوويسز گرافيتي[18][13,14,15] انديس رانديك گراف هايي با تعداد يال ها و يا

تعداد رئوس غير تنهاي مشخص را در حالت هاي گوناگون پيش بيني كرده است. جالب آن كه اين

چنين حدس ها، سبب تحقيق رياضي وار در نظريه ي انديس رانديك شده است ([16,17] را ببينيد).

نقطه ي عطف بررسي رياضي وار انديس رانديك و انديس رانديك تعميم يافته در نيمه ي دوم دهه

ي 1990 رخ داد ،زماني كه تحقيقات قابل توجه و سريعي در اين زمينه شروع و منجر به انتشارات

گوناگون شد. در اين جا لازم است از كارهاي [6,7] پائول اردوش[19] (كه چندين سال قبل از چاپ آن

ها، در دسترس بود) ياد شود، زيرا سبب تشويق ديگران براي مطالعه ي R و Rα شد.

*****

 

انديس رانديك[20]، يك ثابت گرافي است كه به صورت

R= R(G) =∑ 1

u,v d(u)d(v)

تعريف مي شود. (d(u، درجه ي رأس u را نشان مي دهد و عمل جمع روي تمام زوج رئوس مجاور

انجام مي شود.

 

انديس  رانديك تعميم يافته[21] عبارت است از

Rα= Rα(G) =∑(d(u)d(v))α

u,v

كه α عددي حقيقي مي باشد. واضح است كه انديس رانديك، حالت خاصي از انديس رانديك تعميم

يافته است كه 1−=α .

2

 

از ديدگاه رياضي، اولين سؤالي كه مطرح مي شود اين است كه مينيمم و ماكزيمم مقدار R در

رده ي (انتخابي مناسب از) گراف ها كدام است و كدام گراف هاي اين رده ،مقدار اكسترمال[22] (مينيمم

و ماكزيمم) R  را دارند. اغلب يافتن جواب چنين سؤالاتي به هيچ وجه ساده نيست و گراف هاي

اكسترمال در برخي مواقع، ساختار هاي كاملاً عجيب و جالب دارند.

 

 

 

 

 

 

 

 

 

 

 

 

 

1.1 تعاريف اوليه ي گراف ها

در سرتاسر اين پايان نامه، منظور از گراف، گراف ساده و متناهي است. در اين فصل، كليه ي

مفاهيم و تعاريفي را كه در فصل هاي بعد مورد نياز است، ارائه مي دهيم.

دو رأس u و v از G را مجاور يا همسايه گويند، اگر uv يالي از G باشد. فرض كنيد (d(u و (N(u به ترتيب درجه و همسايه هاي رأس u را نشان دهند. مينيمم و ماكزيمم درجه ي G را به

ترتيب با (δ(G و (G)∆ نشان مي دهيم. اگر G داراي ai رأس درجه i =1,2,…,t) ،di) باشد كه

t

(G) = d1 > d2 > … > dt =δ(G)∆ و ai = n∑، آن گاه دنباله درجه ي (D(G را چنين تعريف

i=1

مي كنيم: [D(G) = [d1a[23],d2a[24] ,…,dtat . اگر 1=ai ، آن گاه براي راحتي، به جاي diai از di استفاده مي كنيم. رئوس درجه 0 و 1 را به ترتيب ،رئوس تنها1 و آويزان2 نامند. رأس آويزان را با نام برگ[25] نيز

مي شناسند. مجموعه ي رئوس آويزان درخت T را با (V1(T نمايش مي دهيم. اگر بين يك برگ و

اولين رأس با درجه ي بزرگ تر از 2، k  رأس درجه 2 داشته باشيم، چنين ساختاري را k– برگ مي

ناميم.

يك گراف همبند بدون دور ،درخت[26] است. مجموعه ي درختان n رأسي با 1n رأس آويزان كه 2−n1 n  ≤ 3، با 1Tn,n نشان داده مي شود. مسير[27] Pn، يك درخت مرتبه n است كه دقيقاً دو

رأس آويزان دارد.فرض كنيد Ps = v0v1vs مسيري از T باشد كه 2 = (1d(v1) = … = d(vs (مگر اين كه 1=s  باشد). اگر 1= (0d(v و 3 ≥ (d(vs ، آن گاه Ps را يك زنجير آويزان[28] T ناميم. اگر 3 ≥ (d(v0),d(vs ، آن گاه Ps، زنجير داخلي[29]T  ناميده مي شود. مجموعه ي زنجير هاي آويزان

درخت T را با (P (T نشان مي دهيم. ستاره[30] ي مرتبه Sn ،n، درختي با 1−n رأس آويزان است.

اگر رأس يكتايي  مانند (uV(T موجود باشد كه 3 ≥d(u) = m و به ازاي هر رأس ديگر

d(v) ≤ 2،v، آن گاه T يك ستاره ي تعميم يافته[31] است. مجموعه ي ستاره هاي تعميم يافته كه

داراي 1n رأس آويزان هستند را با 1Tn نشان مي دهيم. دو ستاره[32] ي Sp,q، درختي با 2−p+q

رأس آويزان، يك رأس درجه p و يك رأس درجه q است. اگر 1≤pq  باشد، دو ستاره را

متعادل[33] ناميم. يك گراف همبند ساده را تك دور[34] گوييم، اگر داراي دقيقاً يك دور باشد.  +Sn، گراف

تك دور n رأسي است كه از اتصال دو رأس آويزان در Sn به دست مي آيد.  يك ستاره ي دنباله

دار[35]، درختي متشكل از يك ستاره و مسير آويزان است. به ازاي هر عدد n با فرض 1−n1 n≤ 2،

ستاره ي دنباله دار مرتبه n با 1n رأس آويزان را با (1CS(n,n نشان مي دهيم كه درخت حاصل از

انطباق يك رأس انتهايي مسير 1Pnn با يك رأس آويزان ستاره ي 1+1Sn مي باشد .( 1Sn(p1,…, pn،

درختي n رأسي است كه از الحاق مسير هايي به طول 1pn1 ، … ، p2 ، p به 1n رأس آويزان 1+1Sn

n1

حاصل مي شود و n=n1 +1+∑pi كه 0≥pi . اگر به ازاي هر pi ≥1 ، i باشد، مجموعه ي چنين

i=1

n}−n1−1

درختاني را با Tn1n نشان مي دهيم. همچنين تعريف مي كنيم (1,…,1,0,…,0)Knn1 = Sn . بنا بر اين

.Tn1n ⊆Tn,n1 و Knn1 ∈Tn,n1 نتيجه مي شود كه

 

T T5                                    S4,6                  CS(8,5)

 

T را يك درخت (1n,3)-  منظم[36] ناميم، اگر درختي با 1n رأس آويزان بوده و درجه ي هر رأس

غير آويزاني مانند v، 3 باشد. در اين حالت داريم 2− 1V(T) =2n. مجموعه ي چنين درختاني را

با *1Tn نمايش مي دهيم. (1n1) Le(n,n زوج است) را چنين تعريف مي كنيم: اين درختان متشكل از

ستاره هاي 5S هستند كه با مسير هايي حتي به طول صفر، به هم وصل مي شوند. يك درخت را با 2(,3)T نشان مي دهيم، اگر هر رأس آويزان آن روي يك مسير آويزان به طول حداقل 2 بوده و تمام

رئوس به غير از رئوس درجه 1 و 2، از درجه ي 3 باشند و نيز، زيرگراف القايي رئوس درجه 3، يك

درخت باشد.

يك نيم درخت[37]، درختي مانند T است با يك يال اضافي  كه به رأس 0v  ازT  و نه به هيچ رأس

ديگري، اضافه مي شود. اين يال را يال معلق[38] مي نامند.

0v را ريشه ي T ناميم. گوييم T بديهي است، اگر تنها از 0v و يال معلق تشكيل شود.

 


مقطع : کارشناسی ارشد

دانلود بخشی از انديس رانديک در درخت ها و گراف هايی با يک دور

قبل از خرید فایل می توانید با پشتبانی سایت مشورت کنید