ميان ترم گراف دكتر ميرابراهيمي دانشگاه فردوسي مشهد 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. قضيه ي اويلر را بيان كنيد و از آن نتيجه بگيريد گراف هاي   و هامني نيستند.