چکیده
اندیس 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 را طول مسیر گویند.