ميان ترم گراف دكتر ميرابراهيمي دانشگاه فردوسي مشهد 31/2/8
نام آزمون : ميانترم گراف
نام استاد : دكتر ميرابراهيمي
تاريخ برگزاري : 31/2/86
دانشگاه : فردوسي مشهد
دانشكده : علوم رياضي و آمار
1. عددرنگي يالي گراف را تعريف و مقدار آن را براي گراف هاي دوبخشي تعيين كنيد. ( ادعاي خود را ثابت كنيد. )
2. صورت كلي قضيه ي وايزينگ را بيان كنيد.
3. در حالت كلي چه ارتباطي بين عدد استقلال و عدد پوششي يك گراف وجود دارد؟ ادعاي خود را ثابت كنيد.
4. نشان دهيد اگر G ساده بوده و . آنگاه G شامل يك مثلث است.
5. عدد رمزي يك گراف را تعريف كرده و براي هر دو عدد طبيعي k و l ثابت كنيد :
الف : .
ب : كه
پ : قضيه ي معروف ‹‹ اردوش ، سكرش ، گرين وود و گليسن ›› را بيان و با استفاده از آن نشان دهيد .
6. فرض كنيد v رأسي از گراف هامني G باشد. در اين صورت G را مي توان به گونه اي در صفحه نشاند كه v روي مرز وجه بيروني نشانده شود.
7. نشان دهيد اگر يك گراف هامني خود-دوگان باشد ( با دوگان خودش يكريخت باشد) ، آنگاه e = 2v -2 .
8. قضيه ي اويلر را بيان كنيد و از آن نتيجه بگيريد گراف هاي و هامني نيستند.