ساختمان های گسسته - فصل سوم - نظریه گراف

صفحه 1:
به نام خدا ساختمان های گسسته - نظریه گراف Discrete Structures - Graph Theory تابستان 99 

صفحه 2:


صفحه 3:
* تعریف 1. گراف (ساده) شامل یک مجموعه غير تهى از رئوس به نام و یک مجموعه یال ها به نام مى باشد. # تعریف 2. هر یال با دو راس در ارتباط است که نقاط انتهایی آن یال گفته می شوند. مجموعه یال یک مجموعه زوح مرتب از رئوس است. ۶ حرگزاف غیرجهت:دار تیب زوج:هاآ مهم یست: 

صفحه 4:
‎ae”‏ انمرین 2.یک گزراف كه ازساط بين آثالت :ها راامشخص مى ‎ ‎Detroit ‎ ‎New York ‎San Francisco ‎ ‎Los Angeles ‎ 

صفحه 5:
* تمرین 1. یک گراف که ارتباط بین ایالت ها را مشخص می کند. ‎Ml‏ مجموعه رئوس ‎| = { (San Francisco, Los Angeles), (San Francisco, Denver), :اه ‏ا مجموعه يال‎ (Los Angeles, Denver), (Denver, Chicago), ‎(Chicago, Detroit), (Detroit, New York), ‎(New York, Washington), (Chicago, Washington), ‎(Chicago, New York) } ‎ 

صفحه 6:
* تعریف 3. مالتی گراف گرافی می گویند که بین رئوس بیش از یک یال قرار ‎iat‏ Detroit یب san Chicago Washington Los Angeles 

صفحه 7:
* تعریف 4. سودو گراف گرافی می گویند که هم دارای یال چندگانه باشد طوقه بتواند در آن باشد. Detroit NewYork San/Francisco Deaver Chicago ‎Washington‏ تسس ر اص ‎ ‎ ‎Los Angeles ‎en's ‎ 

صفحه 8:
* تعریف 5. گراف جهندار شامل یک مجموعه غیر تهی از رئوس به نام و یک مجموعه یال ها به نام می باشد. مجموعه یال یک مجموعه زوج مرتب از رئوس آننت .که در آن قزتیب زو ها منقخصکننده دو یل جداگانه است. > به یال در گراف جهت دار بردار نیز می گویند. 

صفحه 9:
3 * تعریف 6. مالتی گراف جهتدار گرافی جهتدار می گویند که هم دارای ‎saul Synalar adele amounts ailing Sli‏ ‎Denver 7‏ \ الوه ‎Cc —‏ ‎Chicago‏ سس ‎gee Washington‏ — ‎Lh ‎Los Angeles ‎ ‎ 

صفحه 10:
* تعریف 7. دو راس را که با یک یال به هم وصل هستند را راس مجاور یا راس همسایه می نامیم. * تعریف 8. درجه هر راس برابر تعداد یال های متصل به آن راس است. < درچه راس را با نمایش می دهیم. < برای سودو گراف , حلقه به تنهایی 2 تا به درچه آن راس اضافه می کند. 

صفحه 11:
@ % * تمرین 2. در گراف زیر درجه هر راس و مجموع درجات را تعیین کنید. * جدول 1 - درجه رئوس ۶ مجموع درجات برایر با 40 می باشد. 

صفحه 12:
@ % * تمرین 3. در یک مسابقه تیم یکبار تیم , تیم یکبار تیم , تيم دوبار تيم , تیم یکبار تیم و تیم یکبار تیم را می برد , با استفاده از گراف , اين متانعه را مدلسالى كو CoN رز ) 

صفحه 13:
** قضيه 1. قضیه دست دادن فزض کنید یک گراف نی سو باشد و تعدادیال های گراف بانشند. 27-( veV * قضیه 2. در یک گراف بی سو باشد تعداد یال با درجه فرد , زوج است. 

صفحه 14:
aS % تعریف 9. وقتی یک یال جهت دارگراف باشد می گوییم مجاور به است و یا مجاور از است. به راس اولیهو به راس پایانی می گویند. تعریف 10. در گراف جهتدار راس درجه ورودی بیانگر تعداد پردار ورودی به آن راس است و درجه ورودی راس را یا نمایش می دهیم. به طور مشایه راس درچه خروجی بیانگر تعداد بردار خروجی از آن راس است و درجه خروجی راس را با نمایش می دهیم . 

صفحه 15:
*# قضیه 3. فرض کنید یک گراف جهتدار باشد و تعداد یال های گراف باشد. ا ال( veV veV 

صفحه 16:
*# تعریف 11. گراف کامل , گرافی است که در آن بین هر دو راس حتما یک یال وجود دارد. ۳ راف كافك ل .وان رزانبا: تغازتشن,می‌آذفيم. 

صفحه 17:
@ 6 * تمرین 4. ثابت کنید در گراف کامل تعداد یال ها برایر با است. در گراف کامل درچه هر راس پرابر با می باشد. بنابراین با توجه به اینکه راس داریم مجموع درجه کل رئوس برابر با می باشد. - اه و1 - ورام( ‎deg(‏ >=2£ vev 2 

صفحه 18:
* تعریف 12. گراف دور , گرافی است که تنها یک دور کامل به طول (اندازه تعداد رئتوس گراف) دارد که از همه رئوس آن عبور می کند. ۳ گراقتآذون‌با! راش‌براابا: تماننش.میذاقیم. ۶-۹ و ‎ee‏ ؟ 37 2 / \ | \ يا / 6< 2 6 2 * كراف دوز ‎she‏ 

صفحه 19:
*# تعریف 13. گراف چرخ , گرافی است که اگر به یک گراف دور یک راس جدید اضافه کنیم و از هر راس گراف یک یال به آن متصل نماییم تشکیل می شود. 88 قرا حرا راس رايا ملس من بعس * كراف دوز ‎she‏ 

صفحه 20:
* تعریف 14. گراف -مکعب , گرافی است که رئوس آن را با رشته صفر ويك به طول نامگذاری شده و بین هر دو راس که تنها در یک بیت با یکدیگر تفاوت دارند یک یال رسم شده است. + كرا ق ستقضب با اراس رايا ماش من حمس ‎i‏ 119 مد وه 100041 ‎eo 1 po) 611‏ 001 900 وه ‎a nu‏ 4 49 9 ‏* كراف -مكعب ‎sly‏ ‎ 

صفحه 21:
% تعریف 15. یک گراف ساده را یک گراف دوبخشی می نامند وقتی بجوانتجیوعه:رانن های گزاف را نبه‌ سوه سجرآی و آفزآز‌سووبه به قسمی که هر یال یک راس از یکی از مجموعه ها را به راسی در مجموعه ‎silanes. Sip‏ 

صفحه 22:
# قضیه 4. یک گراف ساده دوبخشی است اگر و فقط اگر بتوان با دو تنها دو رنگ راس های گراف را رنگ نمود به طوری که هیچ دو راس مجاوری از یک رنگ نباشند. 

صفحه 23:
* تعریفب 16::یک گراتساده را یک گراف,دوبخشی کامل: می نامند. اگر هر راس از یک قسمت به تمام رئوش از قسمت دیگر مجاوز باشد. < گراف دو بخشی کامل را با نمایش می دهیم ( تعداد رئوس دو قسمت هستند) . وآ 2 

صفحه 24:
* تعریف 17. یک زیرگراف از گراف را به صورت گراف زیر تعریف می کنیم : اگر و 2 Cs 

صفحه 25:
له © تعريقف 18. اجتماع دو گراف ساده و را به صورت زیر تعریف ‎wo‏ کنیم : 

صفحه 26:
% gut. JES an Gai gulland aplsl ‏درگراف زیر راش شال‎ Si gayest ‏اداره را به هم وصل می کند مشروط بر اينکه یک ارتباط مخابراتی بین آن دو‎ ‏آذارة وعود واسع اسم هر آتارهمی ایا آداره دنگزی از ظزیی که‎ ‏ارتباط مستقیم مخابراتی یا از طریق اداره دیگری که پیفام را تقویت می کند‎ ارتباط مخابراتی داشته باشد. 

صفحه 27:
% # تهرین. .ای )با آراید نک متال ان دهد ارتباط مجابرآنی تینما ادارات حتی اگر بعضی از خطوط ارتباطی قطع شود , نیز برقرار می شود. 

صفحه 28:
@ * تمرین 5. ب ) حداکثر خطوطی که می تواند بین ادارات قطع شود اما ارتباط همچنان برقرار باشد , چند تا است؟ 

صفحه 29:
@ 4 * تمرین 5. ج ) گرافی رسم کنید حداکثر خطوطی که می تواند بین ادارات قطع شود اما ارتباط همچنان برقرار باشد را نشان دهد.