جزوه دست نویس گسسته مبحث گراف

جزوه دست نویس گسسته مبحث گراف

جزوه دست نویس گسسته مبحث گراف

یک جزوه بسیار عالی از گسسته مبحث گراف به صورت دست نویس خیلی تمییز و مرتب

کمی از داخل جزوه :

گراف نظریه ای است استوار بر دو تعریف راس و یال که اگر راسی نباشد اصلا گرافی تعریف نمی شود ولی اگر راس باشد و یال نباشد آن گراف را تهی می نامیم.

گراف ساده : گرافی است که بین هر دو راس متمایز آن حداکثر یک یال وجود داشته باشد.

تذکر : تعداد اعضای مجموعه رئوس (مجموعه v) را تعداد راس های گراف یا مرتبه ی گراف می نامند و با p نمایش می دهند.

تذکر : تعداد اعضای مجموعه یال ها (مجموعه ی e ) را تعداد یال های گراف یا اندازه ی گراف می نامند و با q نمایش می دهند.

درجه ی یک راس : به تعداد یال هایی که از یک راس خارج می شود درجه ی آن راس می گویند.

نتیجه و نکته ی بسیار مهم : تعداد رئوس با درجه ی فرد در هر گراف ساده قطعا عددی زوج است پس تعداد رئوس با درجه ی زوج وابسته به مرتبه است یعنی اگر مرتبه زوج باشد آن ها نیز زوج و اگر مرتبه فرد باشد آن ها نیز فرد هستند.

*تعداد رئوس درجه فرد که همواره زوج است (بدون هیچ شرطی و همیشه) اما تعداد رئوس با درجه ی زوج وابسته به مرتبه است چون مرتبه زوج بوده پس آن ها نیز زوج هستند.

راس فول درجه : در هر گراف به راسی که به تمام راس های دیگر یال داده است با همه دوست است راس فول درجه می گوییم .

نکته مهم : اگر در گرافی k نفر(راس) فول درجه باشند و(با همه دوست باشند) آن گاه در آن گراف هر فردی غیر از فول درجه ها اگر درجه اش را نگوید ما می فهمیم که درجه ی آن حداقل k می باشد .