مقاله کامل انديس PI در گرافها
مقاله کامل انديس 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 اين عمل را در مورد يالها انجام ميدهد از اينرو به نظر ميرسد تركيب اين دو انديس نيز نتيجة مطلوبي در مطالعات حاصل
فایل : 50 صفحه
فرمت : Word
- کاربر گرامی، در این وب سایت تا حد امکان سعی کرده ایم تمام مقالات را با نام پدیدآورندگان آن منتشر کنیم، لذا خواهشمندیم در صورتی که به هر دلیلی تمایلی به انتشار مقاله خود در ارتیکل فارسی را ندارید با ما در تماس باشید تا در اسرع وقت نسبت به پیگیری موضوع اقدام کنیم.