مقاطع تحصیلی
جستجو در منظومه
نتیجه: تعداد رأس های فرد هر گراف، عددی زوج است.اثبات: فرض کنیم G یک گراف و A ٔ مجموعه ٔ همه ِ رئوس ِ فرد گراف G و B ٔ مجموعه ٔ همه رئوس ِ زوج گراف G باشد. دراین صورت داریم deg(v(∑ + deg) v(∑ = deg) v) ∑ .B ∈ v A ∈ v V(G) ∈ vاز طرفی deg(v) ∑ و deg(v) ∑ زوج اند. (چرا؟) بنابراین deg(v) ∑ نیز عددی زوج است و این نتیجه می‌دهدV(G) ∈ v B ∈ v A ∈ vکه A() n عددی زوج است. (چرا؟)فعالیتیک جمع 7 نفره از دانش آموزان یک کالس را در نظر بگیرید. فرض کنید دوستی بین اعضای این گروه یک ٔ رابطه دوطرفهاست، یعنی ِ هر دو نفر از آنها یا هر دو با هم دوست اند و یا هیچ یک با دیگری دوست نیست. اکنون:الف) گراف 7 رأسی G را تشکیل دهید به این صورت که به ازای هر دانش آموز یک رأس قرار دهید، سپس هر دو رأس رابه هم وصل کنید اگر و تنها اگر دانش آموزان متناظر با آن دو رأس با هم دوست ِ باشند.ب) با استفاده از ٔ قضیه قبل نشان دهید که امکان ندارد ٔ درجه تمام ِ رئوس گراف حاصل برابر با 3 باشد.پ) با توجه به مراحل قبل و با استفاده از گراف نشان دهید که اگر تعداد افراد یک جمع عددی فرد باشد امکان ندارد تمامنفرات آن جمع، دارای تعداد فردی دوست در آن جمع باشند.فعالیتفرض کنید G یک گراف باشد و داشته باشیم 4 ≥ G() δ . می‌خواهیم نشان دهیم که G شامل یک مسیر به طول بزرگ تر یامساوی 4 است.1 رأس دلخواه v 1 را در G در نظر می‌گیریم. حتماً v 1 به رأس دیگری متصل است. (چرا؟) فرض کنیم آن رأس v 2 باشد.٢ حتماً v 2 به رأسی به جز رأس v 1 متصل است. (چرا؟) فرض می‌کنیم آن رأس v 3 باشد.٣ حتماً v 3 به رأسی از ٔ مجموعه } v 1, v 2 { - V(G) وصل است (چرا؟) فرض می‌کنیم آن رأس v 4 باشد.٤ حتماً v 4 به رأسی از ٔ مجموعه } v 1, v 2, v 3 { - V(G) وصل است (چرا؟) فرض می‌کنیم آن رأس v 5 باشد.٥ مسیر v 1 v 2 v 3 v 4 v 5 یک مسیر به طول 4 در گراف G است.کار در کالسدر هر یک از حالت های زیر تعداد یال های گراف G را به دست آورید.الف) G یک گراف n رأسی K ـ منتظم است.ب) G یک گراف n رأسی کامل است. (= K n)Gفصل دوم: گراف و مدل سازی 40