جزوه..
جمعه, ۲ خرداد ۱۳۹۳، ۰۲:۴۵ ب.ظ
*اگر از گراف G به ازای هر تقاطع انقدر یال حذف کنیم که دیگر تقاطع نباشد به گراف G' میرسیم که مسطح است. چون گراف مسطح است تعداد یالهای آن از مرتبهی تعداد رأسهای آن است. پس m' < m+x است که x تعداد تقاطعهای گراف G است.
*روش احتمالاتی: هر رأس را با احتمال p در گراف نگه میداریم. در نتیجه متوسط تعداد رأسها pn، متوسط تعداد یالها p^2 n و متوسط تعداد تقاطعها p^4 n میشود. طبق قضیه قبلی تعداد یالها به صورت متوسط جمع تعداد رأسها و تعداد تقاطعها است.
۹۳/۰۳/۰۲