انديس PI در گرافها

چكيده
انديس PI در گرافها
انديس PI معرف پايداري گراف است كه به صورت جمع، حاصل جمع‌هاي با مد نظر قرار دادن كلية يالهاي گراف همبندي به صورت

e=ur تعريف مي‌شود.

تعداد يالهايي از G است كه به u از v نزديكترند و تعداد يالهايي از G هستند كه به v از u نزديكترند. در اين حاصل جمع كليه يالهاي مد نظر قرار مي‌گيرند تنها يالهايي كه از دو انتهاي e به يك فاصله‌اند در محاسبة انديس PI به حساب نمي‌آيند اين رابطه يك فرمول موثر براي محاسبة انديس PI در كلاس گرافهاي شيميايي مهم مي‌باشد.
صنم روايي

مقدمات
در قرن هيجدهم ميلادي شهر كوينسگبرگ از دو ساحل يك رودخانه و دو جزيره تشكيل شده و در آن زمان ۷ پل اين چهار منطقه را به هم وصل مي‌كردند معماي زير سالها شهروندان را سرگرم كرده بود. آيا امكان دارد با آغاز از يكي از اين مناطق در شهر كشتي زد از هر پل يك بار تنها يكبار گذشت و به مكان اول بازگشت؟
اويلر در سال ۱۷۳۶ با حل مسأله پلهاي كوينگسبرگ نظريه گراف را بنيان گذاشت وي به هر يك از چهار منطقه نقطه‌اي از صفحه را تخصيص داد و به ازاي هر پل بين دو منطقه پاره خط يا كماني بين دو نقطه متناظر با آنها رسم كرد بدين ترتيب مطابق شكل زير به مدلي رياضي دست يافت و به سادگي پاسخ معما را كه منفي است دريافت در دنياي اطراف ما وضعيت‌هاي فراواني وجود دارد كه مي‌توان توسط نموداري متشكل از يك مجموعة نقاط به علاوة خطوطي كه برخي از اين نقاط را به يكديگر متصل مي‌كنند به توصيف آنها پرداخت. تجديد رياضي اين وضعيت‌ها به مفهوم گراف منتهي مي‌شود.
* تعريف ۱ : گراف G يك سه تايي مرتب است كه تشكيل شده از يك مجموعة ناتهي V(G) از رأس‌ها، يك مجموعة E(G) از يالها و يك تابع وقوع VG كه به هريال G يك زوج نامرتب از رأس‌هاي G را كه الزاماً متمايز نيستند.

نسبت مي‌دهد اگر e يك يال و v, u دو رأس باشند بطوريكه در اينصورت گفته مي‌شود كه e ، رأس‌هاي v, u را به يكديگر وصل كرده است و رأس‌هاي v,u دو سريال e ناميده مي‌شوند.
براي رسم يك گراف روش يكتايي وجود ندارد، بدين دليل كه موقعيت نسبي نقاط و خطوط كه به ترتيب نمايانگر رأس‌ها و ريال‌هاي گراف هستند براي ما اهميتي ندارد. نمودار يك گراف فقط رابطة وقوعي را كه بين رأس‌ها و يالها برقرار است نشان مي‌دهد.
تعريف ۲ : دو رأس كه برروي يال مشتركي وا

قعند مجاور نيست اگر هيچ يالي از هيچ رأسي به آن وجود نداشته باشد.
تعريف ۳ : دو يال واقع بر روي يك رأس مشترك نيز مجاورند و يك يال با دو سر يكسان طوقه و يك يال با دو سر متمايز يال پيوندي است.
تعريف ۴ : اگر مجموعة رأس‌ها و مجموعة يالهاي يك گراف متناهي باشند گراف مزبور را متناهي مي‌نامند.
تعريف ۵ : گرافي را كه يك رأس داشته باشد بديهي و ساير گراف‌ها را غيربديهي مي‌ناميم.
تعريف ۶ : يك گراف ساده است اگر هيچ طوقه‌اي نداشته باشد و بين هر دو رأس آن بيش از يك يال نباشد.
تعريف ۷ : گراف تهي، گرافي است كه هيچ يالي نداشته باشد.
تعريف ۸ : دو گراف H,G هسمان‌اند اگر و و نوشته مي‌شود در اين حالت G , H يكريخت ناميده مي‌شوند.
تعريف ۹ : تعدادي اعضاي V(G) را مرتبة گويند و تعداد اعضاي E(C) را اندازة G گويند.
تعريف ۱۰ : درجة هر رأس برابر با تعداد يالهايي است كه از آن رأس مي‌گذرد.
تعريف ۱۱ : گراف G را –r منتظم گويند هر گاه درجة هر رأس آن برابر rباشد.
تعريف ۱۲ : گراف از مرتبة p را كه (p-1) منتظم باشد، گراف كامل گويند و آنرا با kp نشان مي‌دهند.
تعريف ۱۳ : زوج مرتب (V,E) كه در آن V متناهي و ناتهي و E زير مجموعه‌اي از مجموعة تمام زوجهاي مرتب متشكل از اعضاي V است راگراف جهتدار مي‌گويند پس در گراف جهتدار به ازاي هر حداكثر دويال جهتدار از u به v يا از v به u وجود دارد.
تعريف ۱۴ : گرافي كه مي‌توان مجموعة رأس‌هاي آنرا به دو زير مجموعة Y,X چنان افراز كرده يك سر تمام يالهاي آن در X و سر ديگر آنها در Y باشد را گراف دو بخشي گويند. اگر هر رأسX به هر رأس Y وصل شده باشد آنرا گراف دو بخش كامل گويند.

تعريف ۱۵ : اگر v,u دو رأس دو به دو متفاوت از گراف دلخواه G باشند يك مسير از u به v دنباله‌اي متشكل از m+1 رأس دو به دو متفاوت كه از u آغاز و به v ختم مي‌شود و هر دو رأس متوالي اين دنباله مجاورند عدد m را طول مسير گويند.
تعريف ۱۶ : گراف G راهمبند گويند هر گاه بين هر دو رأس آن مسيري وجود داشته باشد.
تعريف ۱۷ : دنباله ناصفر متناهي را يك گشت گويند بطوريكه جملات آن يك در ميان از رأس‌ها و يالها بوده و دو سريال باشند رأس‌هاي را ابتدا و انتهاي با شرط متشكل از رأس از G است كه در آن ها دو به دو متمايزند و هر دو رأس متوالي در آن مجاورند. M را طول اين

دور از گراف G مي‌نامند در حقيقت يك گذرگاه بسته را كه ابتدا و رأس‌هاي داخلي آن متمايز باشند دور مي‌نامند و گرافي كه هيچ دوري نداشته باشد آنرا گراف بي دور مي‌نامند.
تعريف ۲۰ : درخت يك گراف بي دورهمبند است در درخت هر دو رأس با يك مسير يكتا به يكديگر متصلند.
تعريف ۲۱ : حاصلضرب دكارتي گرافهاي H,G را با نماد (H  G) نشان مي‌دهند، مجموعة رئوس گراف حاصل و يك يال از گراف حاصل است هر گاه هر يك از حالتهاي زير اتفاق بيفتد:

تعريف ۲۲ : گراف H يك زير گراف ايزومتريك از G است اگر براي هر دو رأس بطوريكه نشاندهندة كوتاهترين مسير بين در G است.
تعريف ۲۳: G را گراف همينك نسبي گويند اگر G يك زير گراف ايزومتريك از حاصلضرب دكارتي گرافهاي كامل باشد.
تعريف ۲۴ : گراف G را –k همبند گويند هر گاه با حذف رئوس گراف G تا تعداد k تا گراف حاصل همبند باقي بماند و اگر بيشتر از k تا كم كنيم گراف حاصل ناهمبند خواهد بود.
تعريف ۲۵ : گراف 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 در هيدروكربنهاي بنزوئيدي ابتدا به بيان مقدماتي در خصوص هيدروكربنها مي‌پردازيم.
هيدروكربنهاي بنزوئيدي با توجه به نحوة چيدمان قدرتمندشان (و گاه اسرار آميز) و خواص الكترونيكي‌شان ۱۵۰ سال كه توانستند علاقة شيميدانهاي نظري را به خود جلب كنند بعلاوه به عنوان مواد خام در صنعت شيمي كاربرد دارند(استفاده مي‌شوند براي توليد رنگ و پلاستيك) اما آنها جزء خطرناك ترين آلوده كننده‌ها هستند در حدود ۱۰۰۰ نوع هيدروكربنهاي بنزوئيدي شناخته شده است كه بعضي از آنها بيشتر از ۱۰۰ شش ضلعي دارند. هيدروكربنهاي بنزوئيدي سيستمهاي شش ضلعي هستند.
يك سيستم شش ضلعي يك نمودار مسطح است بدون رئوس از هم جدا به طوريكه تمام شش ضلعيهاي داخلي هم قابل رؤيت هستند (همة

شش ضلعيها قابل رؤيت هستند) و دو شش ضلعي يا از هم جدا هستند يا دقيقا يك يال مشترك دارند و هيچ سه شش ضلعي در يال مشتركي سهيم نمي‌باشد. مجموعة همه سيستمهاي شش ضلعي و مجموعة همة سيستمهاي شش ضلعي با h شش ضلعي را به ترتيب با HSh , HS نشان مي‌دهند.

شش ضلعي‌هايي را كه يك يال مشترك دارند مجاور گويند. دو تا شش ضلعي از يك سيستم شش تايي يا دو رأس مشترك دارند (اگر مجاور باشند) يا هيچ رأس مشتركي ندارند (اگر مجاور نباشند)
رأسي كه متعلق به سه شش ضلعي باشد را راس داخلي گويند و تعداد رئوس داخلي را با ni نشان مي‌دهند اگر باشد سيستم را چگاليده گويند. مجموعة همه سيستم‌هاي شش ضلعي چگاليده و مجموعة همه سيستم‌هاي چگاليده با h شش ضلعي را به ترتيب با نشان مي‌دهند. اگر يك سيستم شش ضلعي حداقل يك رأس داخلي داشته باشد سيستم را فشرده خارجي گويند.
شش ضلعي r از يك سيستم شش ضلعي چگاليده كه يك يا دو سه شش ضلعي در همسايگي آن هستند اگر r با يك شش ضلعي همسايه باشد آنرا خروجي گويند اگر با سه شش ضلعي همسايه باشد آنرا انشعاب يا شاخه گوئيد شش ضلعي‌ها مجاورند دقيقاً با دو شش ضلعي به صورت زاويه‌اي يا خطي. شش ضلعي r مجاور يا دوشش ضلعي كه دقيقا دو رأس از درجة ۲ دارند اگر اين دو رأس مجاور باشند، همبند زاويه‌اي است براي كوتاه كردن مي‌گوئيم r از نوع راست و اگر اين دو رأس مجاور نباشند، همبند خطي است مي‌گوئيم r از نوع«خ» است.

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