7327

راضيه مسيبي

كارشناسي ارشد

رياضي كاربردي (تحقيق در عمليات )

پيام نور , كتابخانه مركزي دانشگاه پيام نور

1391

74ص

شيردل ، غلام حسن

فرهمند راد، شهريار

68-65ص

پ مسيبي ، راضيه , ع

گراف G قطبي است اگر مجموعه رئوس آن به A وB تقسيم شوند ،به طوريكه زير گراف توليد شده توسطA ، يك گراف چند بخشي كامل و زير گراف توليد شده توسطB ، اجتماع گسسته اي از خوشه ها باشد.گراف هاي قطبي مشابه گراف هاي دو بخشي و گراف هاي دو نيم شده (جدا) است .بنابراين در حالت كلي ، مساله تشخيص گراف هاي قطبي شناخته شده ،يك مساله - NP كامل است .در اين پايان نامه ، قطبيت در گراف هاي خطي را مطالعه مي كنيم و مشخص مي كنيم كه يك گراف قطبي - خطي است اگر گراف خطي ما، قطبي نيز باشد و زيرگرافهاي ممنوعه ي گرافهاي قطبي -خطي را تعريف كرده وثابت مي كنيم هيچ كدام قطبي -خطي نبوده و اجتماع انها نيز قطبي خطي نيست و در آخر الگوريتمي ارائه مي دهيم كه مي تواند زيرگرافهاي ممنوعه ي گرافهاي قطبي خطي را تشخيص دهد

فصل اول : تعاريف و مفاهيم پايه اي. فصل دوم : گرافهاي قطبي ، گرافهاي قطبي -خطي . فصل سوم : زير گرافهاي ممنوعه ي گرافهاي قطبي _ خطي . فصل چهارم : نتيجه گيري وكاربردها و پيشنهادات

2931/30/10

7327پ

1

21174