پیدا کردن گراف دوبخشی کامل یکرنگ
حداکثر تعداد یالهای گراف بدون مثلث
اثبات همبند بودن مکمل گراف ناهمبند
همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1
رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
پیدا کردن مولفه های قویا همبند گراف جهت دار
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
سلام دوستان
قضیه گراف توران سال 1941 توسط جناب پال توران مطرح شد . همون زمان تا چند سال حلش افراد قدری تو زمینه ی گراف رو به چالش کشید ...
بزارید اول چن تا نماد قراردادی بگم که بیشترشو همتون بلدبن ((( کرم دارم باید بگم !!! :):):) ))) گراف ساده ی G با مجموعه رئوس { V = { v1 , v2 , v3 , v4 , ... , vn و مجموعه یالهای E داریم . اگر vi و vj با هم مجاور باشند میگوییم : vivj عضو E . هر p-خوشه در G زیر گراف کاملی از G با p راس است که با Kp نشان داده میشود . پال توران سوال زیر را مطرح کرد ::
فرض کنید G گراف ساده ای باشد که شامل p-خوشه نیست .در این صورت G حداکثر چند یال میتواند داشته باشد ؟؟؟؟؟؟؟
خوش باشید !
الان این نماد ها دقیقا چه ربطی به صورت سوال داشت؟ :-) منم میگم G حداکثر h یال داره که تابع $h$ تابع شمردن حداکثر تعداد یالهای گراف بدون p-خوشه هست
2014-08-26 01:29:38 -0600 کلاه قرمزیدوست عزیز کلاه قرمزی :: الآن منظورت کدوم نماد ها بود ؟؟؟؟
بعدش مگه چن نفر گفتن که G ,حداکثر h تا یال داره که شمامیگی " منم "
2014-08-26 04:59:17 -0600 هه هه ههسازشاطرجان توی کاهو کسی حق توهین به هیچ کسی رو نداره. این جور نظرات پاک می‌شن و در صورت تکرار اکانت فرد خاطی بسته میشه.
2014-08-27 06:40:42 -0600 کاهواثبات این سوال توسط خود توران خیلی سادس و بامزه است ولی غیر منطقی است :دی اما اثبات های دیگه ای برای این قضیه اعلام شده و یکم سخت ولی منطقی می باشد : فرض می کنیم گراف kr را نداشته باشد
جواب :$$\frac{n^2}{2}.\frac{r-2}{r-1}$$
این جواب (البته کف جواب !) به ما میگه که گراف رو m-1 بخشی کنیم و هرچقد می تونیم یال بزاریم (!)
اثابت بهینگی :برای این اثبات از خود مفاهیم این گراف استفاده می کنیم .
اگر $w \mapsto v$ و $w \mapsto u$ :
1) اگر $d(u)>d(w)$ یا $d(u)>d(w)$ :
آنگاه $ w $ را حذف کرده و ان را به تمام همسایه های $u$ وصل می کنیم در این صورت نیز kr یافت نمی شود (چرا؟ (اثباتش بدیهیه :دی))
2) اگر $d(w)\geq d(u)$ و $d(w)\geq d(v)$:
آنگاه $u$ و $v$ را حذف می کنیم و به همسایه های $w$mوصل می کنیم در این صورت باز نیز kr نداریم (چرا؟)
پس ثابت شد همه همسایه های یکسانی دارند پس گراف m-1 بخشی که بیشترین تعداد یال را داراست می باشد !(چرا؟)
برگرفته از کتاب وست !
اگه نفهمیدید بگید !(دقت کنید اثبات بهینگی بالا است !)
خوب ثابت کردید که میتونه اینقدر یال داشته باشه. پس اثبات اینکه بیشتر از این نمیتونه داشته باشه کو؟؟
2015-03-24 14:38:02 -0600 پروفسوراگه دقت کرده باشید اونجا گفتم تعداد همسایه های هر کسی چقدر می تونه باشه !
2015-03-25 06:11:57 -0600 چشمکمن که هیچی از گراف نمیدونم. ولی به نظر اثبات خوبی میاد! :دی ╬╬╬╬╬╬╬╬╬╠
2015-03-26 10:02:36 -0600 سی پلاس پلاس