جواب درست »

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

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

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

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::.$$