دانلود مقاله اندیس PI در گرافها

چکیده
اندیس PI در گرافها
اندیس PI معرف پایداری گراف است که به صورت جمع، حاصل جمع‌های با مد نظر قرار دادن کلیه یالهای گراف همبندی به صورت e=ur تعریف می‌شود.

تعداد یالهایی از G است که به u از v نزدیکترند و تعداد یالهایی از G هستند که به v از u نزدیکترند.

در این حاصل جمع کلیه یالهای مد نظر قرار می‌گیرند تنها یالهایی که از دو انتهای e به یک فاصله‌اند در محاسبه اندیس PI به حساب نمی‌آیند این رابطه یک فرمول موثر برای محاسبه اندیس PI در کلاس گرافهای شیمیایی مهم می‌باشد.

صنم روایی

مقدمات
در قرن هیجدهم میلادی شهر کوینسگبرگ از دو ساحل یک رودخانه و دو جزیره تشکیل شده و در آن زمان 7 پل این چهار منطقه را به هم وصل می‌کردند معمای زیر سالها شهروندان را سرگرم کرده بود.

آیا امکان دارد با آغاز از یکی از این مناطق در شهر کشتی زد از هر پل یک بار تنها یکبار گذشت و به مکان اول بازگشت؟

اویلر در سال 1736 با حل مسأله پلهای کوینگسبرگ نظریه گراف را بنیان گذاشت وی به هر یک از چهار منطقه نقطه‌ای از صفحه را تخصیص داد و به ازای هر پل بین دو منطقه پاره خط یا کمانی بین دو نقطه متناظر با آنها رسم کرد بدین ترتیب مطابق شکل زیر به مدلی ریاضی دست یافت و به سادگی پاسخ معما را که منفی است دریافت در دنیای اطراف ما وضعیت‌های فراوانی وجود دارد که می‌توان توسط نموداری متشکل از یک مجموعه نقاط به علاوه خطوطی که برخی از این نقاط را به یکدیگر متصل می‌کنند به توصیف آنها پرداخت.

تجدید ریاضی این وضعیت‌ها به مفهوم گراف منتهی می‌شود.

* تعریف 1 : گراف G یک سه تایی مرتب است که تشکیل شده از یک مجموعه ناتهی V(G) از رأس‌ها، یک مجموعه E(G) از یالها و یک تابع وقوع VG که به هریال G یک زوج نامرتب از رأس‌های G را که الزاماً متمایز نیستند.

نسبت می‌دهد اگر e یک یال و v, u دو رأس باشند بطوریکه در اینصورت گفته می‌شود که e ، رأس‌های v, u را به یکدیگر وصل کرده است و رأس‌های v,u دو سریال e نامیده می‌شوند.

برای رسم یک گراف روش یکتایی وجود ندارد، بدین دلیل که موقعیت نسبی نقاط و خطوط که به ترتیب نمایانگر رأس‌ها و ریال‌های گراف هستند برای ما اهمیتی ندارد.

نمودار یک گراف فقط رابطه وقوعی را که بین رأس‌ها و یالها برقرار است نشان می‌دهد.

تعریف 2 : دو رأس که برروی یال مشترکی واقعند مجاور نیست اگر هیچ یالی از هیچ رأسی به آن وجود نداشته باشد.

تعریف 3 : دو یال واقع بر روی یک رأس مشترک نیز مجاورند و یک یال با دو سر یکسان طوقه و یک یال با دو سر متمایز یال پیوندی است.

تعریف 4 : اگر مجموعه رأس‌ها و مجموعه یالهای یک گراف متناهی باشند گراف مزبور را متناهی می‌نامند.

تعریف 5 : گرافی را که یک رأس داشته باشد بدیهی و سایر گراف‌ها را غیربدیهی می‌نامیم.

تعریف 6 : یک گراف ساده است اگر هیچ طوقه‌ای نداشته باشد و بین هر دو رأس آن بیش از یک یال نباشد.

تعریف 7 : گراف تهی، گرافی است که هیچ یالی نداشته باشد.

تعریف 8 : دو گراف H,G هسمان‌اند اگر و و نوشته می‌شود در این حالت G , H یکریخت نامیده می‌شوند.

تعریف 9 : تعدادی اعضای V(G) را مرتبه گویند و تعداد اعضای E(C) را اندازه G گویند.

تعریف 10 : درجه هر رأس برابر با تعداد یالهایی است که از آن رأس می‌گذرد.

تعریف 11 : گراف G را –r منتظم گویند هر گاه درجه هر رأس آن برابر rباشد.

تعریف 12 : گراف از مرتبه p را که (p-1) منتظم باشد، گراف کامل گویند و آنرا با kp نشان می‌دهند.

تعریف 13 : زوج مرتب (V,E) که در آن V متناهی و ناتهی و E زیر مجموعه‌ای از مجموعه تمام زوجهای مرتب متشکل از اعضای V است راگراف جهتدار می‌گویند پس در گراف جهتدار به ازای هر حداکثر دویال جهتدار از u به v یا از v به u وجود دارد.

تعریف 14 : گرافی که می‌توان مجموعه رأس‌های آنرا به دو زیر مجموعه Y,X چنان افراز کرده یک سر تمام یالهای آن در X و سر دیگر آنها در Y باشد را گراف دو بخشی گویند.

اگر هر رأسX به هر رأس Y وصل شده باشد آنرا گراف دو بخش کامل گویند.

تعریف 15 : اگر v,u دو رأس دو به دو متفاوت از گراف دلخواه G باشند یک مسیر از u به v دنباله‌ای متشکل از m+1 رأس دو به دو متفاوت که از u آغاز و به v ختم می‌شود و هر دو رأس متوالی این دنباله مجاورند عدد m را طول مسیر گویند.

تعریف 16 : گراف G راهمبند گویند هر گاه بین هر دو رأس آن مسیری وجود داشته باشد.

تعریف 17 : دنباله ناصفر متناهی را یک گشت گویند بطوریکه جملات آن یک در میان از رأس‌ها و یالها بوده و دو سریال باشند رأس‌های را ابتدا و انتهای با شرط متشکل از رأس از G است که در آن ها دو به دو متمایزند و هر دو رأس متوالی در آن مجاورند.

M را طول این دور از گراف G می‌نامند در حقیقت یک گذرگاه بسته را که ابتدا و رأس‌های داخلی آن متمایز باشند دور می‌نامند و گرافی که هیچ دوری نداشته باشد آنرا گراف بی دور می‌نامند.

تعریف 20 : درخت یک گراف بی دورهمبند است در درخت هر دو رأس با یک مسیر یکتا به یکدیگر متصلند.

تعریف 21 : حاصلضرب دکارتی گرافهای H,G را با نماد (H G) نشان می‌دهند، مجموعه رئوس گراف حاصل و یک یال از گراف حاصل است هر گاه هر یک از حالتهای زیر اتفاق بیفتد: تعریف 22 : گراف H یک زیر گراف ایزومتریک از G است اگر برای هر دو رأس بطوریکه نشاندهنده کوتاهترین مسیر بین در G است.

تعریف 23: G را گراف همینک نسبی گویند اگر G یک زیر گراف ایزومتریک از حاصلضرب دکارتی گرافهای کامل باشد.

تعریف 24 : گراف G را –k همبند گویند هر گاه با حذف رئوس گراف G تا تعداد k تا گراف حاصل همبند باقی بماند و اگر بیشتر از k تا کم کنیم گراف حاصل ناهمبند خواهد بود.

تعریف 25 : گراف G راK یال همبند گویند هر گاه با حذف کمتر از k تا یال از تعداد کل یالهای G زیر گراف حاصل همبند باقی بماند.

ساختار یک مولکول را می‌توان به روشهای مختلفی نمایش داد.

اطلاعات مربوط به یک ساختار شیمیایی از یک مولکول معمولاً توسط گراف مولکولی نمایش داده می‌شود و نظریه گراف با ارائه ابزارهای مفید و متنوع زمینه مناسبی را برای شیمی دانها فراهم نموده است از جمله این ابزارها می‌توان به اندیسهای توپولوژیکی اشاره نمود که بعنوان تشریح کننده ساختار مولکولی مورد استفاده قرار می‌گیرند این اندیسها ارتباط نزدیکی با خواص شیمیایی ترکیبات دارند از این رو به منظور تشریح خواص مولکولی مختلف اندیسهای توپولوژیکی زیادی طراحی شدند و روز به روز بر تعداد آنها افزوده می‌شود در حقیقت برای طراحی ترکیبات شیمیایی با استفاده از خواص فیزیکی یا شیمیایی موجود یا کاربردهای زیست شناسی و داروئی از اندیسهای توپولوژیکی استفاده می‌شود.

معروفترین اندیس توپولوژیکی اندیس وینر (wiener) یا عدد وینر است و کاربرد این اندیس در ترکیبات شیمیایی است که ساختار مولکولی غیر دوری دارند در حقیقت گراف مولکولی متناظر این ترکیبات درختها هستند.

Coworkers , Gutman یک نسل جدیدی از اندیس وینر ( w) را برای گرافهای دوری معرفی کرده‌اند تحت عنوان اندیس اس – زد (seged) مزیت اصلی اندیس اس- زد (sz) اینست که اصلاح شده اندیس وینر (w) است در سیستمهای غیر دوری این دو اندیس با هم برابر و منطبقند.

این دو اندیس بر روی فواصل در گراف مولکولی پایه گذاری شده‌اند.

اندیس وینر (w) برابر است با مجموع فواصل بین هر زوج از رئوس در گراف مولکولی مربوطه .

اندیس sz از نوع اندیسهای حاصل از ضرب فواصل از رئوس است که در حقیقت تلفیق پراکندگی بین رئوس است.

با توجه به مراتب فوق معرفی یک اندیس توپولوژیکی جمعی طبیعی به نظر می‌رسد که در آن ارتباط بین فواصل یالها مورد بررسی قرار بگیرد.

اخیراً اندیس توپولوژیکی جدیدی به نام اندیس padmakar – Ivan با علامت اختصاری PI معرفی شده است که در مقایسه با اندیسهای w,sz در موارد مشابه نتیجه بهتری می‌دهد و همچنین بدلیل محاسبه آسانتر آن نسبت به دو اندیس دیگر، اندیس PI یک اندیس توپولوژیکی با اهمیت تری برای مطالعه است.

همانطور که ذکر شد اندیس sz عمل تلفیق پراکندگی رئوس را در یک گراف مولکولی انجام می‌دهد در حالیکه اندیس PI این عمل را در مورد یالها انجام می‌دهد از اینرو به نظر می‌رسد ترکیب این دو اندیس نیز نتیجه مطلوبی در مطالعات حاصل کند.

در این مقاله ما به بررسی و محاسبه اندیس PI در موارد ذیل الاشاره می‌پردازیم.

اندیس PI در گرافهای بنزوئیدی محاسبه اندیس PI در هیدروکربنهای بنزوئیدی با استفاده از روشهای برشهای متعامد محاسبه اندیس PI با استفاده از PI افزارها محاسبه اندیس PI در گرافهای حاصل از حاصلضرب دکارتی گرافها محاسبه اندیس PI در زنجیرهای پلی آمینو هیدروکربنهای بنزوئیدی با توجه به کاربرد ویژه اندیس PI در هیدروکربنهای بنزوئیدی ابتدا به بیان مقدماتی در خصوص هیدروکربنها می‌پردازیم.

هیدروکربنهای بنزوئیدی با توجه به نحوه چیدمان قدرتمندشان (و گاه اسرار آمیز) و خواص الکترونیکی‌شان 150 سال که توانستند علاقه شیمیدانهای نظری را به خود جلب کنند بعلاوه به عنوان مواد خام در صنعت شیمی کاربرد دارند(استفاده می‌شوند برای تولید رنگ و پلاستیک) اما آنها جزء خطرناک ترین آلوده کننده‌ها هستند در حدود 1000 نوع هیدروکربنهای بنزوئیدی شناخته شده است که بعضی از آنها بیشتر از 100 شش ضلعی دارند.

هیدروکربنهای بنزوئیدی سیستمهای شش ضلعی هستند.

یک سیستم شش ضلعی یک نمودار مسطح است بدون رئوس از هم جدا به طوریکه تمام شش ضلعیهای داخلی هم قابل رؤیت هستند (همه شش ضلعیها قابل رؤیت هستند) و دو شش ضلعی یا از هم جدا هستند یا دقیقا یک یال مشترک دارند و هیچ سه شش ضلعی در یال مشترکی سهیم نمی‌باشد.

مجموعه همه سیستمهای شش ضلعی و مجموعه همه سیستمهای شش ضلعی با h شش ضلعی را به ترتیب با HSh , HS نشان می‌دهند.

شش ضلعی‌هایی را که یک یال مشترک دارند مجاور گویند.

دو تا شش ضلعی از یک سیستم شش تایی یا دو رأس مشترک دارند (اگر مجاور باشند) یا هیچ رأس مشترکی ندارند (اگر مجاور نباشند) رأسی که متعلق به سه شش ضلعی باشد را راس داخلی گویند و تعداد رئوس داخلی را با ni نشان می‌دهند اگر باشد سیستم را چگالیده گویند.

مجموعه همه سیستم‌های شش ضلعی چگالیده و مجموعه همه سیستم‌های چگالیده با h شش ضلعی را به ترتیب با نشان می‌دهند.

اگر یک سیستم شش ضلعی حداقل یک رأس داخلی داشته باشد سیستم را فشرده خارجی گویند.

شش ضلعی r از یک سیستم شش ضلعی چگالیده که یک یا دو سه شش ضلعی در همسایگی آن هستند اگر r با یک شش ضلعی همسایه باشد آنرا خروجی گویند اگر با سه شش ضلعی همسایه باشد آنرا انشعاب یا شاخه گوئید شش ضلعی‌ها مجاورند دقیقاً با دو شش ضلعی به صورت زاویه‌ای یا خطی.

شش ضلعی r مجاور یا دوشش ضلعی که دقیقا دو رأس از درجه 2 دارند اگر این دو رأس مجاور باشند، همبند زاویه‌ای است برای کوتاه کردن می‌گوئیم r از نوع راست و اگر این دو رأس مجاور نباشند، همبند خطی است می‌گوئیم r از نوع«خ» است.

هر شش ضلعی همبند زاویه‌ای و شاخه‌ای در یک سیستم شش ضلعی فشرده را پیچ می‌نامند (در نقطه مقابل خروجی و همبند خطی) در شکل زیر پیچ‌ها را با k نشان داد‌ه‌ایم.

یک زنجیر خطی با h شش ضلعی یک سیستم چگالیده بودن پیچ است (از اینرو برای تا خروجی دارد و h-2 شش ضلعی از نوع «خ») یک قطعه یک زنجیر غیر خطی ماکسیمال در یک سیستم فشرده است شامل پیچ‌ها و یا شش ضلعی‌های خروجی در انتهای آن.

یک قطعه شامل یک شش ضلعی خروجی را قطعه خروجی گویند.

تعداد شش ضلعی‌ها در یک قطعه که s را طول آن گویند که آنرا با (s) L نشان می‌دهند برای هر قطعه از همواره .

G شامل قطعات با طولهای می‌باشد برای مثال در شکل (*) یک قطعه به طول 3 و چهار قطعه بطول 2 داریم.

1- اندیس PI در گرافهای بنزوئیدی : در این قسمت به معرفی روش‌های محاسبه اندیس PI برای خانواده گرافهای بنزوئیدی چگالیده که شامل سه سطر با طولهای متفاوت از شش ضلعی‌ها هستند می‌پردازیم در این خانواده از گرافها هر رأس داخلی متعلق به سه، شش ضلعی است و ترکیبات این خانواده دارای خواص شیمیایی و فیزیکی و ریاضی قابل توجهی هستند.

فرض کنیم G یک گراف همبند و غیر جهتدار بدون یالهای چند گانه و طوقه باشد.

مجموعه رئوس و یالهای G را به ترتیب با نشان می‌دهیم.

اگر یک زیر گرافی از شامل همه یالهای از G که دو رأس از V’ را به هم متصل می‌کنند باشد G’ زیر گراف حاصل از G بوسیله V’ است و به صورت G[V] نشان داده می‌شود.

قرار می‌دهیم e=ny یک یال ازG باشد.

X یک زیر مجموعه از رئوس G که به رأس n نزدیکترند تا Y,y یک زیر مجموعه از رئوس G که به رأس y نزدیکترندتا x : نشاندهنده فاصله بین دو رأس v ,u از G است.

قرار می‌دهیم .

اگر G یک گراف دو بخشی باشد در اینصورت تعداد یالهایی که به رأس x نزدیکترند تا تعداد یالهایی است که به رأس y نزدیکترند تا x.

اندیس PI در گراف دو بخشی G به صورت زیر تعریف می‌شود: در گرافهای دوری یالهایی وجود دارند که از دو سر یک یال به یک فاصله قرار دارند در هنگام محاسبه اندیس PI این یالها به شمار نمی‌آیند.

قرار می‌دهیم [X,Y] را به عنوان نشاندهنده زیر مجموعه‌ای از یالهای بین رئوس تعداد یالهای متساوی الفاصله از دو سریال e را مشخص می‌کند در حقیقت از این رابطه حاصل می‌شود.

برای گراف همبند و دو بخش G داریم: بنابراین برای محاسبه اندیس PI در گراف دو بخشی G کافیست را به ازای محاسبه کنیم.

حال به محاسبه اندیس PI در گرافهای بنزوئیدی با استفاده از برشهای مقدماتی می‌پردازیم: قرار می‌دهیم دو یال از باشند اگر در اینصورت e’ , e متساوی الفاصله هستند یک برش مقدماتی مانند c(e) نسبت به یال e مجموعه تمام یالهای که از e به یک فاصله هستند.

قرار می‌دهیم برشهای مقدماتی بطور Li باشند برای و متناظراً اعداد را در نظر می‌گیریم: در اینصورت رابطه (1) برابر می‌شود با رابطه قرار می‌دهیم گرات بنزوئیدی چگالیده در شکل 1-1 در زیر نشان داده شده است.

بدون آنکه خللی به کلیت واقع شود را فرض کردیم.

قضیه 1-1 : فرض کنیم گراف را که در شکل 2-1 نشان داده شده است را در نظر می‌گیریم در اینصورت داریم: برهان : 5 نوع برس مقدماتی برای گراف وجود دارد.

پس داریم : قضیه 2-1: فرض کنیم حال گراف را با شرط که در شکل 3-1 نشان داده شده است در نظر می‌گیریم در اینصورت خواهیم داشت: برهان : 6 نوع برش مقدماتی وجود دارد به صورت : با استفاده از تساوی (2) داریم : و بدین ترتیب حکم ثابت می‌شود.

قضیه 103 : فرض کنیم و a,b و ، گراف را که در شکل 104 نمایش داده شده در نظر می‌گیریم در اینصورت: 5 نوع برش مقدماتی وجود دارد پس داریم : با استفاده از معادله (2) داریم : قضیه 104 : فرض کنیم ، گراف که در شکل 105 نشان داده شده را در نظر می‌گیریم در اینصورت داریم: برهان : 6 نوع برش مقدماتی وجود دارم پس داریم : حال با استفاده از معادله (2) داریم : نتایج اصلی 2- محاسبه اندیس PI در هیدروکربنهای بنزوئیدی با استفاده از روش برشهای متعامد: همانطور که در قسمت اول شرح دادیم اندیس PI یک کمیت عددی است مربوط به ساختار مولکولی که از رابطه زیر بدست می‌آید: بطوریکه e = uv یک یال از تعداد یالهایی از G که به رأس u نزدیکترند تا v و nev تعداد یالهایی از G که به رأس v نزدیکترند تا u.

در این قسمت ما با استفاده از برشهای متعامد محاسبه اندیس PI در زنجیرهای شش ضلعی را ساده تر می‌کنیم.

قرار می‌دهیم که یک گراف دو بخش و مسطح است و به ترتیب نشان دهنده مجموعه رئوس و یالهای G می‌باشند.

تعداد یالهای G را به صورت زیر نمایش می‌دهیم.

و را به عنوان کوتاهترین مسیر ارتباطی بین دو رأس تعریف می‌کنیم.

یال از گراف G را با رئوس انتهایی v,u در نظر می‌گیریم در اینصورت یال از G را متساوی الفاصله از e می‌نامیم اگر و تنها اگر داشته باشیم: یا (ترجیحاً : ) یال از G را قویاً متساوی الفاصله از e اگر و فقط اگر داشته باشیم: یا بالعکس برای (ترجیحاً : ) در شکل 202 می‌توان تفاوت بین را مشاهده کرد: یک برش عمودی c(e) نسبت به یالe یک مجموعه از همه یالهای است به طوریکه نسبت به e قویاً هم فاصله است: مجموعه را به عنوان مجموعه مکمل c(e) به صورت زیر تعریف می‌کنیم.

که به این معنی است که e* با e قویاً هم فاصله نیست.

قرار می‌دهیم نشاندهنده تعداد یالهایی از G که با e رابطه sco دارند.

و را نیز به صورت زیر تعریف می‌کنیم: بدیهی است که برای هر یال رابطه زیر برقرار خواهد بود.

از معادله (1) نتیجه می‌شود که : با جایگذاری رابطه (2) در معادله (3) خواهیم داشت: لذا رابطه زیر حاصل می‌گردد: رابطه قویاً هم فاصله (sco) در گذاره‌های زیر صدق می‌کند: (1) خاصیت بازتابی : برای هر یال داریم : (2) خاصیت تقارنی : برای یالهای از از اینکه نتیجه می‌دهد که - (استثنا : برای همه گرافهای دو بخشی صدق نمی‌کند مانند شکل 201) (3) خاصیت تعدی : برای یالهای از اگر داشته باشیم آنگاه داریم : .

گراف را یک گراف Sco گویند اگر و تنها اگر رابطه بین یالها در زیر مجموعه از یک رابطه هم ارزی باشد.

‌[زیر مجموعه که در خواص (1) تا (3) صدق می‌‌نماید‍[ در چنین گرافی برای یال e# عضو c(e) داریم مجموعه c(e) نشاندهنده برش عمودی نسبت به یال e از G است در یک گراف SCO مجموعه یالهای E(G) یک اجتماعی از کلاسهای هم ارزی دو به دو جدا از هم از برشهای عمودی از گراف G است قرار می‌دهیم که نشاندهنده تعداد یالهای مشمول در برش عمودی است.

حال معادله (4) به صورت زیر درمی‌آید: عدد m(e) برای هر یال در یک گراف sco مانند G برابر است یعنی مجموع داخلی در سمت راست رابطه (5) به صورت زیر در می‌آید: با جایگذاری * در معادله (5) خواهیم داشت: حال معادله (4) برای محاسبه اندیس PI گرافهای SCO به صورت زیر درمی‌آید: (7) اگر نشاندهنده مجموعه همه برشهای متعامد از G باشد در اینصورت معامله جدیدی با جایگذاری در رابطه (7) ایجاد می‌شود: (8) مثال 201 : مطابق شکل 204 یک گراف sco است: از اینرو داریم : 382 = 21 = تعداد کل یالها 1 = تعداد برش عمودی شامل 4 تا یال 3 = تعداد برش عمودی شامل 3 تا یال 4 = تعداد برش عمودی شامل 2 تا یال با جایگذاری موارد فوق در رابطه (8) اندیس محاسبه گردید.

مثال 202 : محاسبه اندیس PI (phynalenes) گراف متناظر هیدروکربنهای بنزوئیدی یک گراف sco است بنابراین برای محاسبه اندیس PI این گرافها نیز می‌توان از روش برشهای متعامد و در نتیجه از معادله (8) استفاده نمود.

حال چند مثال دیگر را در نظر می‌گیریم: مثال 203 : محاسبه اندیس PI در Lh .

بنابراین بطوریکه به طور مشابه می‌توان اندیس PI را برای ترکیبات با استفاده از معادله (8) محاسبه نمود.

مثال 204 : محاسبه اندیس PI ، Fibonacenes (Fh) مثال 205 محاسبه اندیس PI (Hh) Helicenes مثال 206، محاسبه اندیس (Poly) polyphenylenes, PI - نتایج اصلی روش محاسبه اندیس PI در هیدروکربنهای بنزوئیدی با استفاده از برشهای متعامد از روش تک پایه اولیه مناسب تر است با استفاده از این روش تنها تعداد یالهایی که در برشهای متعامد شرکت دارند را در نظر می‌گیریم به اضافه تعداد نهایی یالها.

لذا محاسبه سریعتر صورت می‌پذیرد.

3- محاسبه اندیس PI با استفاده از PI افزارها : همانطور که درقسمتهای پیشین تشریح گردید اندیس PI یک اندیس توپولوژیکی یال جمعی است و روابطی نیز برای محاسبه آن ارائه گردید در این قسمت با معرفی PI افزارها روش ساده‌تری را برای محاسبه اندیس PI ارائه می‌دهیم از این روش در گرانهایی که PI افزارهای غیر بدیهی را می‌پذیرند استفاده می‌شود.

هر گرافی PI افزارهای بدیهی را می‌پذیرد اما محاسبه زمانی مفهوم دارد که گرافهای در نظر گرفته شده افزارهایPI غیر بدیهی را بپذیرد.

کلاس وسیعی از گرافها این افزارها را می‌پذیرند.

سیستمهای بنزوئیدی، فلزها و ساختارهای مولکولی دیگر از جمله گرافهای هینگ نسبی هستند.

گراف همیتگ نسبی زیر گرافی از حاصلضرب دکارتی گرافهای کامل است که خانواده این گرافها PI افزارهای غیر بدیهی را می‌پذیرند.

برای محاسبه اندیس PI در این بخش ابتدا مقدمات زیر را بیان می‌کنیم: همه گرافها در این بخش همبند فرض شده‌اند.

قرار می‌دهیم یک گراف باشد.

را به ترتیب به عنوان تعداد رئوس و یالهای G در نظر می‌گیریم بطوریکه : .

اگر در اینصورت زیر گراف تولید شده از G توسط X را با نماد نشان می‌دهیم.

OX را مجموعه‌ای از یالهای G با یک رأس انتهایی درX در نظر می‌گیریم بطوریکه رأس انتهایی دیگر در X نباشد.

گراف h یک زیر گراف ایزومتریک از G است اگر برای هر دو رأس به طوریکه dG نشاندهنده کوتاهترین مسیر در G است .

G یک گراف همینگ نسبی است اگر با زیر گرافهای حاصل از حاصلضرب دکارتی از گرافهای کامل ایزومتریک باشد.

فایل از گراف G را در نظر می‌گیریم: مجموعه‌های را به صورت زیر تعریف می‌کنیم: بطوریکه مجموعه‌ای از رئوس است که به u از v نزدیکترند در حالیکه شامل آن رئوسی است که به v از u نزدیکترند.

توجه داشته باشید اگر یال e=vu باشد نقش معاوضه می‌شود از اینرو این دو مجموعه را معمولاً باید برای هر جفت در نظر گرفت و این ابهام در تعریف کلی اشکالی ایجاد نمی‌کند.

معرفی این دو مجموعه صرفاً جهت ساده کردن نمایش یالها می‌باشد.

در گراف دو بخشی G برای هر یال e از G ، مجموعه‌های افزارهایی از را تشکیل می‌دهند.

برای هر یال از گراف G قرار می‌دهیم (یا ) تعداد یالهای از زیر گراف G که توسط ایجاد شده (که توسط ایجاد شده) است مجدداً نقشهای می‌تواند تغییر کند.

حال اندیس PI از گراف G را به صورت زیر تعریف می‌کنیم : واضح است که اندیس sz نیز به صورت زیر تعریف می‌گردد.

فرض کنیم G یک گراف G هستند اگر برای هر i بطوریکه و هر داشته باشیم.

اگر e=uv یک یال از G باشد، را مجموعه همه رئوسی که در فاصله یکسانی از v,u قرار دارند در نظر می‌گیریم بنابراین : قضیه 301 : قرار می‌دهیم یک PI افراز از گراف G باشد در اینصورت خواهیم داشت : برهان : تعداد یالهای G = ||G|| تعداد یالهای افراز EJ = |Ei| تعداد یالهای زیر گراف تولید شده توسط تعداد یالهایی که یک رأس انتهایی آنها در قرار دارد و رأس انتهایی دیگر ابتدا رابطه کلی اندیس PI را در نظر می‌گیریم : حال با توجه به PI افرازهای داریم: پس رابطه زیر حاصل می‌گردد: که همان حکم مورد نظر می‌باشد.

اگر گراف G یک گراف دو بخش باشد در اینصورت و نتیجتاً خواهد بود در اینصورت نتیجه زیر حاصل می‌گردد: نتیجه 301 .

اگر افرازهای گراف دو بخش G باشند در اینصورت اثبات این رابطه با استفاده از قضیه 301 و اینکه در گرافهای دو بخشی بدیهی است.

فرض کنیم G یک گراف باشد و یالهای آن باشد افرازهای از E(G) را PI افرازهای بدیهی می‌نامند برای بکارگیری قضیه 301 ما امیدواریم افرازهای غیر بدیهی گراف G را بیابیم که البته این همیشه امکانپذیر نیست برای مثال دورهای زوج فقط افرازهای بدیهی را می‌پذیرند همانطور که در ابتدای این قسمت بیان شد کلاسی از گرافها که گرافهای همینگ نسبی به آن تعلق دارند افرازهای نابدیهی را می‌پذیرند.

فرض کنیم G یک گراف باشد و یالهایG باشند در اینصورت e با f رابطه (دی جی اوکویچ) Djokovic دارد اگر .

رابطه یک رابطه هم ارزی روی یالهای گراف همینگ نسبی G است.

بعلاوه اگر پس داریم : نتیجتاً افرازی از E(G) که توسط رابطه ~ القا می‌شود یک PI افراز از G است.

در حقیقت در سیستمهای بنزوئیدی چگالیده با h شش ضلعی باشد در اینصورت داریم : ||G||=5h+1 در اینصورت از نتیجه 301 نتیجه زیر حاصل می‌گردد.

نتیجه 302 : G یک سیستم بنزوئیدی با h شش ضلعی باشد و PI افرازها از G شامل برشهای عمودی از G باشد در اینصورت: حال برای نمایش روش ارائه شده در این قسمت مثالهایی از مهم ترین گرافهای مولکولی مختلف را ارائه می‌کنیم.

مثال : 301 محاسبه اندیس Linear chains Lh , PI با فرض بدیهی است شامل یک برش با h+1 یال و 2h برش شامل 2 یال خواهد بود.

بنابراین با بکارگیری نتیجه 302 داریم.

مثال 302 : محاسبه اندیس PI برای بطوریکه .

بدیهی است .

این ترکیب شامل یک برش عمودی با 2h یال و (h-1) + 2h برش شامل 2 یال است بنابراین با استفاده از نتیجه 301 داریم : مثال 303 : محاسبه اندیس PI ، (Fh) Fibonacenes Fh با h شش ضلعی شامل h-1 برش شامل 3 یال و h+2 برش شامل 2 یال است بنابراین با استفاده از نتیجه 302 داریم.

مثال 304 : محاسبه اندیس .

قوانین زیر مستقیماً نتیجه می‌شوند : (2) k تا برش عمودی شامل n+1 یال.

(3) n تا برش عمودی به صورت “\” شامل (k+1) یال دارد.

(4) (n-k+1) برش عمودی به صورت “/” شامل (k+1) یال یدارد.

(5) برای هر دو تا برش به صورت “/” شامل j یال دارد.

حال با توجه به مطالب فوق و با بکارگیری نتیجه 301 داریم: در حالت خاص اگر k=n خواهیم داشت: در حالت k=1 داریم : که در مثال 301 بررسی گردید.

نتایج اصلی : توجه می‌کنیم که این رابطه قبلا در قسمت دوم بررسی گردید اما بدیهی است که روش حاضر محاسبه را ساده تر کرده است.

4- محاسبه اندیس PI در گرافهای حاصلضربی : حاصلضرب دکارتی از گرافهای H , G یک گراف با مجموعه رئوس اگر هر یک از حالتهای زیر اتفاق بیفتد : برای مثال اگر دو گراف باشند به صورت زیر در می‌آید.

در ابتدای این بخش هم فاصله را بیان می‌کنیم : لم 401 (لم فاصله) فرض می‌کنیم H, G دو گراف باشند و رئوس G H باشد در اینصورت : قضیه 401 : برای گرافهای H , G داریم : برهان : یالهای گراف G H طبیعتاً در دو گروه تقسیم می‌شوند.

یالهای به طوریکه و یالهای به طوریکه a=b.

به عبارت دیگر گروه اول یالها G و گروه دوم یالهای H را می‌پوشانند.

این دو زیر مجموعه از یالهای H G را به ترتیب با نشان می‌دهیم واضح است که : برای یال e از را آن یالی از G که پوشیده می‌شود قرارمی‌دهیم و به طور مشابه آن یالی از H است که پوشیده می‌شود تا یال حاصل گردد.

قرار می‌دهیم : یالی از (G H) باشد بنابراین .

بنابراین لم فاصله ایجاب می‌کند که : موارد فوق در شکل 401 تشریح گردیده و در آن با نشان داده شده است.

از اینکه داریم : می‌توان عبارت بصورت زیر تجزیه نمود : اولین جمله رابطه (2) را در نظر می‌گیریم.

با استفاده از (1) می‌توان آنرا به صورت زیر نوشت : می‌توان عبارت فوق را به صورت زیر نوشت : تحت نگاشت تصویر، تصویر |H| یال از G H می‌باشد.

بنابراین رابطه (3) را می‌توان به صورت زیر نوشت: (4) حال رابطه (4) را به این صورت می‌نویسیم : که نتیجه می‌دهد : با استفاده از خاصیت جابجایی حاصلضرب دکارتی جمله دوم رابطه (2) را می‌توان به صورت زیر نوشت : (6) از ترکیب روابط (5) و (5) حکم نتیجه می‌شود.

همانطور که قبلا ذکر کردیم در گراف دو بخش G و با در نظر گرفتن یال e از آن نتیجه 401 : برای هر گراف دو بخش H , G داریم : به عنوان یک مثال ساده گرافهای شبکه را در نظر می‌گیریم که بصورت حاصلضرب فواصل می‌باشد شکل 402 را ببینید.

فرض کنید T یک درخت باشد با n رأس بدیهی است : از اینرو نتیجه 401 منجر می‌شود به : این حالت ساده تر می‌شود اگر ما حاصلضرب دکارتی یک گراف را با خودش در نظر بگیریم، در حالت دو بخشی نتیجه زیر را داریم.

* نتیجه 402 برای هر گراف دو بخش G داریم : حاصلضرب دکارتی شرکت پذیر است از این رو قوانین زیادی قابل تعریف‌اند.

حال حاصلضرب دکارتی از n کپی گراف G یعنی Gn .

قضیه 402 : برای هر گراف دو بخش G و داریم : برهان : برای n=1 حکم به صورت بدیهی نتیجه می‌شود.

اگر قرار دهیم n=2 با استفاده از نتیجه 402 حکم نتیجه می‌شود.

برای ادامه استقرا ابتدا توجه کنیم با یک استقرای ساده می‌توان حدس زد برای هر و هر گراف G خواهیم داشت : حال فرض می‌کنیم حکم برای برقرار است و را در نظر می‌گیریم با استفاده از نتیجه 401 و رابطه (7) داریم.

توجه به این نکته که دو فرم دیگر نیز برای نمایش حاصلضرب دکارتی گرافها وجود دارد نیز مفید خواهد بود.

G X H , G+ H لم 402 H , G دو گراف باشند در اینصورت داریم : (3) همبند است اگر و فقط اگر H , G همبند باشند.

(4) ضرب دکارتی شرکت پذیر می‌باشد.

لم 403.

: یادآوری می‌کنیم برای گراف G و : فرض کنید دو رأس مجاور از رئوس باشند به طوریکه G , H دو بخش باشند در اینصورت اثبات بطور مستقیم از لم 402 نتیجه می‌شود.

صورت دیگری برای قضیه 401 فرض کنیم H , G دو گراف همبند دو بخش باشند در اینصورت : اثبات با استفاده از لم‌های 401 و 402 و 403و تعریف اندیس PI داریم : کد اثبات را کامل می‌کند.

5- محاسبه اندیس PI در زنجیرهای پلی آمیند همانطور که گفته شد اندیس توپولوژیکی یک عدد حقیقی مربوط به یک گراف است بطوریکه پایداری ساختاری و به نمایش تصویری گراف ارتباطی ندارد.

اندیسهای توپولوژیکی مختلفی تعریف شده‌اند و کاربردهای مختلفی در مدلسازی شیمیایی و داروئی و سایر ویژگیهای مولکولی پیدا کرده‌اند.

اندیس W اولین اندیس توپولوژیکی بود که در شیمی مورد استفاده قرار گرفت در سال 1947 میلادی توسط Harold wiener معرفی شد که در زمان شیمی اندیس w برابر است با مجموع کوتاهترین مسیرهای اتصال کربن – کربن در یک مولکول.

و در زبان تئوری گراف اندیس وینر برابر است با تعداد همه کوتاهترین فواصل در یک گراف خواهد بود.

اندیسهای sz , w در درختها یکی بوده و مربوط به فواصل بین رئوس است و اندیس PI یک اندیس توپولوژیکی منحصر به فرد که مربوط به توازی یالهاست زیرا در تعریف آن یالهایی که از دو انتهای یک یال به یک فاصله اند به حساب نمی‌آیند که این یالها را یالهای موازی گویند از واقعیت به دو راست که توازی در حالت کلی یک رابطه هم ارزی است اگر چه در مورد گرافهای دو بخش یک رابطه متقارن و بازتابی است اخیراً اندیس PI برای بعضی از ساختار نانوتیوپها با استفاده از خواص مقدماتی توازی محاسبه شده است.