اختصاصی از
فی لوو دانلود مقاله اندیس 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 در موارد ذیل الاشاره می‌پردازیم.
1- اندیس PI در گرافهای بنزوئیدی
2- محاسبة اندیس PI در هیدروکربنهای بنزوئیدی با استفاده از روشهای برشهای متعامد
3- محاسبة اندیس PI با استفاده از PI افزارها
4- محاسبة اندیس PI در گرافهای حاصل از حاصلضرب دکارتی گرافها
5- محاسبة اندیس 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 را با نماد <X> نشان می‌دهیم. OX را مجموعه‌ای از یالهای G با یک رأس انتهایی درX در نظر می‌گیریم بطوریکه رأس انتهایی دیگر در X نباشد.
گراف h یک زیر گراف ایزومتریک از G است اگر برای هر دو رأس به طوریکه dG نشاندهندة کوتاهترین مسیر در G است . G یک گراف همینگ نسبی است اگر با زیر گرافهای حاصل از حاصلضرب دکارتی از گرافهای کامل ایزومتریک باشد.
فایل از گراف G را در نظر می‌گیریم: مجموعه‌های را به صورت زیر تعریف می‌کنیم:
بطوریکه مجموعه‌ای از رئوس است که به u از v نزدیکترند در حالیکه شامل آن رئوسی است که به v از u نزدیکترند. توجه داشته باشید اگر یال e=vu باشد نقش معاوضه می‌شود از اینرو این دو مجموعه را معمولاً باید برای هر جفت در نظر گرفت و این ابهام در تعریف کلی اشکالی ایجاد نمی‌کند.
معرفی این دو مجموعه صرفاً جهت ساده کردن نمایش یالها میباشد. در گراف دو بخشی G برای هر یال e از G ، مجموعه‌های افزارهایی از را تشکیل می‌دهند.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله50 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود با لینک مستقیم
دانلود مقاله اندیس PI در گرافها 
