پرسش

با عرض سلام
سوال اول:
آیا عكس قضیه « اگر G درختی با p راس و q یال باشد آنگاه : P = q + 1 » درست است ؟
اگر درست است دلیل چیست و اگر اشتباه است مثال نقض بزنید .
سوال دوم:
آیا فرمولی برای تعیین تعداد مسیر های یك گراف كامل وجود دارد؟ چیست.
با تشكر

پاسخ

عكس قضیه فوق در حالت كلی درست نیست مثلا گراف ناهمبندی را در نظر بگیرید كه 5 راس دارد و بین 4 راس آن یك دور وجود دارد یعنی 4 یال دارد پس در رابطه فوق صدق می كند اما واضح است كه یك درخت نیست.
اما در مورد سوال دوم:
اگر به هر راس یك برچسب نسبت دهیم هر مسیر دنباله ای از رئوس است پس،كافیست دنباله ای از رئوس را در نظر بگیرید.فرض كنید دنباله ای از رئوس به طول p داریم هر ترتیب از این رئوس یك مسیر به طول p را معین می كند.تعداد كل این ترتیب ها برابر است با p! o .نكته ای كه باید توجه داشت این است كه هر مسیر دو بار شمرده می شود زیرا یك مسیر از یك A شروع و به B ختم شود و مسیر دیگری كه همین مسیر را در جهت عكس طی می كند و از B به A می رود یك مسیر است كه چون دو ترتیب متفاوت از رئوس است پس دو بار شمرده می شود پس باید در انتها تقسیم بر دو گردد.(توجه كنید علت متمایز بودن ترتیب متمایز بودن A,B است پس تنها برای مسیرهای با طول بیش از صفر تقسیم بر دو می كنیم.)پس تعداد مسیرها ی با طول ناصفر كه با s نشان می دهیم عبارتست از:
P(n,2)+P(n,3)+. . . +P(n,n) }=2s }(به ضریب 2 s دقت كنید).
كه P(n,k) برابر تعداد ترتیب های k تایی از n عدد است.