پایان ترم گراف دکتر میر ابراهیمی 29/3/1386
رای دهی: 5 / 5
نام آزمون : پایان ترم گراف
نام استاد : دکتر میر ابراهیمی
تاريخ برگزاري : 29/3/1386
دانشگاه : فردوسی مشهد
دانشكده : علوم ریاضی
رشته : ریاضی
1. پل را در یک گراف تعریف و نشان دهید هر دو پل متداخل ؛ چاوله یا 3-پل های هم رزند.
2. قضیه ی کوراتفسکی را بیان کنید.
3. حدس چهار رنگ و دو حکم معادل با آن را بیان کنید.
4. قضیه ی پنج رنگ را بیان و اثبات کنید.
5. قضیه ی گرین برژ را بیان و اثبات کنید.
6. چه رابطه ای بین طول مسیرهای جهت دار در یک گراف جهت دار و ساختار اصلی گراف زمینه ی آن وجدو دارد؟
7. تورنمنت را تعریف کنید و نشان دهید:
الف : هر تورنمنت شامل یک مسییر همیلتنی است.
ب : هر تورنمنت شمل رأسی است که از آن ، هر رأس دیگر گراف ، با حداکثر دو گام دسترس پذیر است .
8. ثابت کنبد در یک گراف بحرانی، برش رأسی یک خوشه نیست و نتیجه بگیرید هر گراف بحرانی یک بلوک است.
9. حدس هیوش را بیان کنید.
10. چندجمله ای رنگی یک گراف را تعریف و برای هر یال e از گراف G نشان دهید :
11. چند جمله ای رنگی هر یک از گراف های زیر را با استدلال بدست آورید :
الف : گراف کامل
ب : گراف تهی
ج : درخت
د : 
