اندیس PI در گرافها 50 ص

لینک دانلود و خرید پایین توضیحات

فرمت فایل word  و قابل ویرایش و پرینت

تعداد صفحات: 49

چکیده

اندیس 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باشد.