چکیده

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

ولادو پریلاگ[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 و یال معلق تشکیل شود.

 


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

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

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