ميان ترم گراف دكتر ميرابراهيمي 10/2/1386

نام آزمون : ميان ترم گراف

تاريخ برگزاري :10/2/1386

نام استاد : دكتر ميرابراهيمي

دانشگاه : فردوسي مشهد

دانشكده : علوم رياضي و آمار

1. نشان دهيد گراف هاي زير يكريختند.

2. فرض كنيد گراف G دوبخشي باشد. نشان دهيد رأس هاي G را مي توان به گونه اي شماره گذاري كرد كه ماتريس مجاورت آن به شكل روبرو باشد.

3. نشان دهيد گراف G دوبخشي است اگر و فقط اگر دوري به طول فرد نداشته باشد.

4. نشان دهيد در هر گروه متشكل از دو يا چند نفر، هميشه دو نفر وجود دارند كه دقيقا ً داراي يك تعداد دوست در داخل گروه اند.

5. ثابت كنيد هر درخت نابديهي، حداقل داراي دو رأس از درجه ي يك است.

6. فرض كنيد G گرافي با يال باشد، نشان دهيد G همبند است اگر و تنها اگر درخت باشد.

7. نشان دهيد اگر G ساده و ، آنگاه G داراي مسيري به طول k است.

8. نشان دهيد اگر G داراي رأس هاي درجه فرد نباشد، آنگاه دور هاي مجزا يال وجود دارند به طوري كه

9. يك گراف همبند ناتهي اويلري است اگر و تنها اگر داراي راس با درجه ي فرد نباشد.

10. اگر G گراف ساده با و باشد، آنگاه G هميلتني است.