دانلود مقاله اندیس 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 برای خانواده گرافهای بنزوئیدی چگالیده که شامل سه سطر با طولهای متفاوت از شش ضلعی‌ها هستند می‌پردازیم در این خانواده از