تالار گفتمان مانشت

کسی میتونه تو تعیین تشکیل گراف دادن درجه ی نودها از طریق هاول حکیمی کمکی بهم بکنه؟
یه مثال بزنم :
سوال --> چند مورد از موارد زیر میتوانند درجه ی راسهای یک گراف باشند ؟
1. 5,5,5,3,2,2,1,1
2. 5,5,4,4,2,2,1,1
3. 5,5,5,4,2,1,1,1


ممنونم دوستان

(14 آذر 1393 05:39 ب.ظ)ziba.O نوشته شده توسط: [ -> ]کسی میتونه تو تعیین تشکیل گراف دادن درجه ی نودها از طریق هاول حکیمی کمکی بهم بکنه؟
یه مثال بزنم :
سوال --> چند مورد از موارد زیر میتوانند درجه ی راسهای یک گراف باشند ؟
۱/ ۵,۵,۵,۳,۲,۲,۱,۱
۲/ ۵,۵,۴,۴,۲,۲,۱,۱
۳/ ۵,۵,۵,۴,۲,۱,۱,۱


ممنونم دوستان

روند کار به این شکله:
ابتدا اعداد رو به صورت نزولی مرتب کنید.
عدد اول رو حذف کنید. مثلا 5
از اعداد باقیمانده 5تای اول رو یک واحد کاهش بدید
اعداد باقی مونده رو دوباره به صورت نزولی مرتب کنید.
و دوباره همین کارها رو تکرار کنید.
اگه به دنباله 0 رسیدید ، دنباله گرافیکی بوده
55532211
4421111
311100
00000
-----------------------
55442211
4331111
221100
11000
0000
---------------------
سومی نمیشه

بین اول سری اعدادمون رو مرتب میکنیم. عدد اول هر چی باشه ، اونو حذف میکنیم به تعداد عدد اولی، اعدادمون رو یک واحد کاهش میدیم.
اینجا توی مثال عدد اول سری، ۵ بود.۵ رو حذف میکنیم و از اعداد باقیمانده از ۵ تا اولش یک واحد کاهش میدیم و به همین ترتیب میریم

چرا از 5 تای اول یکی کم میشه؟ تو حل بعضیاشو کم کردی بعضیاشو نه. نفهمیدم

(14 آذر 1393 06:22 ب.ظ)ziba.O نوشته شده توسط: [ -> ]چرا از ۵ تای اول یکی کم میشه؟ تو حل بعضیاشو از کم کردی بعضیاشو نه. نفهمیدم

والا این چیزیه که من توی روش حلش دیدم.
بین اول سری اعدادمون رو مرتب میکنیم. عدد اول هر چی باشه ، اونو حذف میکنیم به تعداد عدد اولی، اعدادمون رو یک واحد کاهش میدیم.
اینجا توی مثال عدد اول سری، ۵ بود.۵ رو حذف میکنیم و از اعداد باقیمانده از ۵ تا اولش یک واحد کاهش میدیم و به همین ترتیب میریم جلو.عکس رو ببینید احتمالا متوجه میشید.

[attachment=17366]

(14 آذر 1393 06:36 ب.ظ)explorer نوشته شده توسط: [ -> ]

(14 آذر 1393 06:22 ب.ظ)ziba.O نوشته شده توسط: [ -> ]چرا از ۵ تای اول یکی کم میشه؟ تو حل بعضیاشو از کم کردی بعضیاشو نه. نفهمیدم

والا این چیزیه که من توی روش حلش دیدم.
بین اول سری اعدادمون رو مرتب میکنیم. عدد اول هر چی باشه ، اونو حذف میکنیم به تعداد عدد اولی، اعدادمون رو یک واحد کاهش میدیم.
اینجا توی مثال عدد اول سری ۵ بود.۵ رو حذف میکنیم و از اعداد باقیمانده از ۵ تا اولش یک واحد کاهش میدیم و به همین ترتیب میریم جلو.عکس رو ببینید احتمالا متوجه میشید.

ایول فهمیدم مرسی دستت درد نکنه.

سلام دوستان
یک سوال داشتم،دنباله ی زیر گرافی است؟
روش حل:
5,4,4,4,2,1
3,3,3,1,0
2,2,0,0

نقل قول: اگه به دنباله ۰ رسیدید ، دنباله گرافیکی بوده

به دنباله 0 نرسیدیم پس گرافی نیست!درسته؟

بله این دنباله ، دنباله درجات رئوس یه گراف(ساده) نیست.

در ارتباط با سوالتون که پرسیده بودید چرا دنباله درجات رئوس رو مرتب میکنیم و بعدش اولین عدد رو حذف میکنیم و از اعداد باقیمانده در دنباله به اندازه اوون عدد یکی کم میکنیم:
ما در این روش روال ساخت گراف رو برعکس طی میکنیم.فرض کنید گراف رو به شما دادن.اول اینکار رو میکنید اولین راس با بالاترین درجه رو حذف میکنیم. این به معنی حذف اوون راس و تموم یالهای مرتبط با اوونه. مثلا اگه درجه این راس 7 باشه پس از حذف این راس باید 7 یال هم حذف بشن. این 7 یال وابسته به اووون راس بودن. بخاطر همین در ادامه کار از 7 تا عدد بعدی در دنباله ، از هر کدوم یکی کم میکنه.
امیدوارم واضح گفته باشم.