ورود ثبت‌نام راهنما درباره‌ی کاهو
پرسش‌ها برچسب‌ها کاربر‌ها سوال بپرسید!

آمار پرسش:

  • پرسیده شده: 2014-08-01 09:25:39 -0500
  • مشاهده شده: 560 بار
  • بروز شده: 2014-08-01 17:49:56 -0500

پرسش‌های مشابه:

شرط وجود 2 کینگ در گراف کامل جهت دار

شبکه $n\times n$ پایدار

پیدا کردن گراف دوبخشی کامل یکرنگ

حداکثر تعداد یال‌های گراف بدون مثلث

آیا گراف قویا همبند است؟

اثبات همبند بودن مکمل گراف ناهمبند

همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1

رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ

دنباله ی درجات گراف

پیدا کردن مولفه های قویا همبند گراف جهت دار

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

به چند طریق میتوان گرافی را جهت دار کرد به طوری که درجه خروجی هر راس حداکثر یک باشد ؟

2

گراف ساده همبند برچسب داری با n راس و m یال موجود است . میخواهیم یالهایش را طوری جهت دار کنیم که از هر راس حداکثر یک یال خارج شده باشد . به چند طریق میتوانیم این کار را انجام دهیم ؟

منبع » وبلاگ امیر گوهر شادی

(;

گراف گراف-جهتدار
2014-08-01 09:25:39 -0500
سماق دو 1349 ● 7 ● 19 ● 37
پاک‌کردن   ویرایش سوال
نظرات

داش خیلی ممنون

2014-08-01 09:29:05 -0500 طوفان

خب اگر m از n بیشتر باشه درجه ی خروجی یه راسی بیشتر از یک میشه پس m< n

اگر هم از n-1 کمتر باشه گراف همبند نیست پس n-1< m

پس m یا برابر n یا n-1

2014-08-01 09:56:11 -0500 طوفان

مسئله ی جالبی بود +1

2014-08-02 05:53:06 -0500 طوفان

سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com

2015-08-06 08:57:55 -0500 امیر شکری

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-27 08:05:39 -0500 امیر شکری

1 پاسخ

2

جواب درست »

خب واضحه که دو تا حالت بیشتر نداریم . یا تعداد یالها برابر راس هاست یا یک واحد کمتر (چراشو طوفان گفته)

حالت اول اینکه 1 - m = n . یعنی یک گراف همبند با n- 1 یال داریم . خب به این گراف میگن درخت (چرا ؟ ) الان باید مشخص کنیم که یک درخت رو به چند طریق میشه جهت دار کرد به طوری که از هر راس حداکثر یک یال خارج شده باشه .
سادست . یک برگ A رو در نظر میگیریم و میخواهیم جهتدارش کنیم (یالش رو ) . یال متصل به اون دو حالت میتونه داشته باشه :

1. وارد برگ شده : در این صورت راس متصل به A ، یعنی طرف دیگه ی اون یال ، یک خروجی خواهد داشت و چون هر راس نمیتونه بیشتر از یه خروجی داشته باشه ، ازینرو جهت تمام یال های متصل به اون راس به طور یکتا معلوم میشه . برای راس های جدید هم اکنون هر یک یک خروجی دارن پس برای یال های اونها هم اینحالت پیش میاد و همینطور الی آخر تا تمام یالهای درخت مشخص بشن . به عبارت ساده تر اگر یال ابتدایی به برگ A وارد شده باشه ، اونوقت اگه درخت رو از A آویزون کنیم ، جهت یال ها همگی به سمت بالا خواهد بود . مثل یه سر چشمه برعکس یا اتشفشانی که جهت فورانش از اطراف به درونه ( تصویر برای درک بیشتر !) همینطور میدونیم هیچ یالی نیست که جهتش به طور یکتا معلوم نشه چون با شروع از A میشه به هر راسی رسید (ِdfs) یال های بینشون جهتش رو به بالا میشه و اگه قرار باشه یالی از قلم بیفته ، یعنی راس متصل به اون یال به A مسیری نداره image description

2. از برگ خارج شده : در این حالت میتونیم برگ (A) رو حذف شده فرض کنیم ( چرا ؟ ) و مساله رو برای گرافی با یک راس کمتر حل کنیم (استقرا )

به صورت بازگشتی میگیم » اگه (a(n برابر تعداد روش های جهت دهی برای یک درخت n راسی باشه ، اونوقت طبق توضیحات بالا » $$a(n) = a(n - 1) + 1$$

برای n = 2 واضحه که دو طریق میشه . پس برای n راس هم میشه n طریق . یعنی یک درخت n راسی رو میشه به n طریق به این صورت جهتگذاری کرد.


حالت دوم اینکه m = n . در اینجا درختی داریم که شامل یک دور ( دقیقن یک دور ) هست . (چرا ؟ چون همبنده و میدونیم هر گراف n راسی شامل دوره ، از طرفی اگه یک یال از این دور حذف بشه گراف ما تبدیل به درخت میشه . پس در واقع با افزودن یک یال به یک درخت به این گراف رسیدیم و میدونیم با افزودن یک یال به یک درخت دقیقن یک دور تشکیل میشه )

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


در مجموع چنین نتیجه ای گرفتیم :

1 - اگر m = n آنگاه به 2 روش میتوان جهت گذاری کرد
2- اگر m = n- 1 آنگاه به n روش میتوان جهت گذاری کرد

$$.::The End::.$$

2014-08-01 17:49:56 -0500
سماق دو 1349 ● 7 ● 19 ● 37
پاک‌کردن   ویرایش پاسخ
نظرات

خوب بود . +1

2014-08-02 04:17:57 -0500 حمید کاملی

من هم تقریبا حل کرده بودم :) +1

2014-08-02 05:51:30 -0500 طوفان

پاسخ شما

فقط در صورتی که پاسخی برای این پرسش دارید، آن را اینجا بنویسید و برای بحث کردن از قسمت «ثبت‌ نظر» استفاده کنید. شما می‌توانید قبل از وارد شدن به سایت پاسخ خود را بنویسید. این پاسخ ذخیره می‌شود و زمانی که شما وارد سایت شدید یا ثبت‌نام کردید منتشر می‌شود.

پیش‌نمایش:

کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر است.