سلام دوستان
سوالی که واسم در مبحث گراف پیش امده در مورد مسیرها در گراف های سودار هستش فصل دوم قلی پور(ساختمان گسسته)
استادمون یه مثال حل کرده نمی دونم درسته، غلطه واقعا سر در نمی یارم
سوال: فرض کنید {A={1,2,3,4 و رابطه R در مجموعهA به صورت زیر تعریف شده باشد.
{(R={(1,1),(1,2),(2,3),(2,4),(3,3),(3,4),(4,4
الف:R^2 , R^3 رو بدست بیاورید
خوب حالا R^2 یعنی ۲ مسیر داشته باشه درسته
و R^3 یعنی ۳ مسیر باشه درسته
{(R^2={(1,1),(1,2),(1,3),(1,4),(2,3),(2,4),(3,3),(3,4),(4,4
{(R^3={(1,1),(1,2),(1,3),(1,4),(2,3),(2,4),(3,3),(3,4),(4,4
حالا مشکل من اینه که چطور تو ۱ و ۱ یبار ۲ تا مسیر هست(R^2) یه با ۳ تا مسیر(R^3)
اگه فرض بگیریم که اره دو مسیر تو R^2 بین ۱ و ۱ هست پس ۱ پس ۱ و ۲ میشه ۳ مسیر واسه بیقیه قسمت ها هم همین طوره مثل ۱و ۴ و ... .
خواهش میکنم منو از این سردر گمی نجات دهید
دوتا مسیر نیست. مسیر بطول ۲ هست. R^n معرف مسیر بطول n هست نه n مسیر. برای مثال توی R^3 زوج مرتب (۱,۱) رو داریم. یعنی از ۱ به ۱ یک مسیر بطول ۳ یافت میشه. از یک میریم به ۱ و بعد میریم به ۱/ شاید این یکم گیج کننده باشه. یه مثال دیگه توی R^2 زوج مرتب (۱,۴) داریم که توی R نداریم. یعنی از ۱ به ۴ مسیر بطول ۲دو هست ولی بطول یک نیست. از ۱ میریم به ۲ و از ۲ میریم به ۴/
خوب یعنی هر گره های بازخورد(یا همون ( ۱و۱) ) مسیری همیشه به طول n دارند که تو R^2 گره ۱و۱، مسیری به طول ۲ دارد و تو R^3 مسیری به طول ۳ وجود دارد تا اینجا درست.
خوب حالا رابطه های در R^2 رو بررسی می کنیم خوب
اینجا میگه
{(R^2={(1,1),(1,2),(1,3),(1,4),(2,3),(2,4),(3,3),(3,4),(4,4
خوب ۱ به ۱ چند مسیر داره ۲ مسیر داره
بعدش میاد میگه ۱ به ۲ چند مسیر داره باز دو مسیر یعنی چی مگه ۱ به ۱ دو مسیر نداشت خوب ۱ به ۲، ۳ مسیر داره پس اینجا باز تناقض هست یا میتونیم بگیم که دل بخواهیه ممکنه ۳۰۰ مسیر باشه فقط ما دو مسیر مد نظرمون هست و بس.
پس چرا تو ۲ به ۳ خوب یه مسیر هست اون مسیر دوممون کجاست
فکر کنم شما متوجه حرفم نشدید. اگه یه زوج مرتب توی R^2 باشه یعنی از مقدمش به تالیش مسیر بطول دو وجود داره. نمیگه چند مسیر وجود داره. ماتریس رابطه فقط مشخص کننده وجود مسیره. به هیچ وجه تعداد مسیرو نمیگه. این ماتریستون برای مثال مناسب نیست. چون از R^2 به بعد، همشون رابطه تعدی دارن و ماتریسشون یکی میشه.
یه مثال دیگه میزنم:
R={(1,2),(2,3),(3,4),(4,1)}
R^2={(1,3),(2,4),(3,1),(4,2)}
R^3={(1,4),(2,1),(3,2),(4,3)}
R^n=...
بنظرم این مثال بهتر باشه. حالا بهتر میشه روی R^iها نظر داد.