درخت (نظریه گراف): تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات ردهٔ همسنگ (۲۶) +تمیز (۱۱.۵ core): + رده:درختان (نظریه گراف) |
جز ←با توجه به حکم کلی زیر درخت ها از این نظر مستثنی هستند.: اصلاح متن با استفاده از AWB |
||
خط ۶۴:
به زبان نظریه ی گراف ها، این کار به معنی متناظر کردن هر رأس با فقط یکی از یال های متصل به آن است .این کار در مواردی عملی نیست؛ به عنوان مثال همانطور که گفته شد، تعداد رأس های هر درخت از تعداد یال های آن یکی بیشتر است . گراف شکل (1) را در نظر بگیرید . در این گراف می توان هر رأس را با یالی که از آن به سمت رأس a0 خارج می شود متناظر کرد . به این ترتیب، به جز ریشه، هر رأس با یالی متناظر می شود.
==
رأس های گراف همبند غیر درخت را می توان با یال های متصل به آن ها متناظر کرد.
اثبات:هر گرافی که n رأس را به هم متصل می کند دارای حداقل n-1 یال است و با حذف برخی از یال ها قابل تبدیل به درخت است . فرض کنید a0b0 = e0 یکی از یال هایی باشد که با حذف آن ها گراف ما به یک درخت، مثلاً T، تبدیل می شود . a0 را به عنوان ریشه ی T انتخاب کنید. در T هر أس به جز a0 را می توان با یالی متصل به آن متناظر کرد؛ یال اضافی e0 از گراف را نیز می توان با a0 متناظر کرد. به این ترتیب هر رأس گراف با یالی متصل به آن متناظر شده است.
با توجه به بحث پیشین، توجه به این نکته مفید است که همیشه می توان در گراف، ر أس ها را با یال های متصل به آن ها، یا یال ها را با رأس های متصل به آنها متناظر کرد. می توانیم هر دو کار را انجام دهیم، اگر و تنها اگر تعداد رأس ها و یال های گراف مساوی باشند . چنین گرافی نمی‌تواند درخت باشد و بنابراین، نتیجه می گیریم که بایستی مانند گراف شکل (3) فقط دارای یک مدار c باشد . در واقع تناظری وجود دراد که دو سویی عمل می کند، یال ها را با رأس ها متناظر می کند، و رأس ها را با یال ها .کافی است یال های c را با رأس های c، و هر رأس غیر متعلق به c را با نزدیکترین یال متصل به آن نسبت به c متناظر کرد .
| |||