درخت در نظریه گراف؛ یالها، برگها و مسیر یکتا
آموزش تعریف درخت، رابطه تعداد رأس و یال، برگها، مسیر یکتا و تشخیص سریع گرافهای درختی در تست.
پاسخ کوتاه
درخت گرافی همبند و بدون دور است. این دو شرط چند ویژگی همارز میسازند که در تستها اجازه میدهند بدون رسم کامل، تعداد یالها یا اثر حذف و افزودن یک یال را تشخیص دهیم.
تعریف و رابطه یال
درخت با n رأس دقیقاً n-1 یال دارد. شرط n-1 یال بهتنهایی کافی نیست؛ گراف باید همبند باشد یا نبود دور نیز ثابت شود. یک گراف ناپیوسته میتواند n-1 یال داشته باشد و همچنان درخت نباشد.
مسیر یکتا
بین هر دو رأس یک درخت دقیقاً یک مسیر ساده وجود دارد. اگر دو مسیر متفاوت وجود داشت، ترکیب آنها یک دور میساخت. اگر هیچ مسیر نبود، گراف همبند نبود. این ویژگی گاهی بهترین راه اثبات درختبودن است.
حذف و افزودن یال
حذف هر یال درخت آن را به دو مؤلفه جدا میکند؛ پس همه یالهای درخت پل هستند. افزودن یک یال تازه میان دو رأس موجود نیز دقیقاً یک دور میسازد، چون پیش از افزودن بین آن دو یک مسیر یکتا وجود داشته است.
برگها
برگ رأسی با درجه یک است. هر درخت با دستکم دو رأس حداقل دو برگ دارد. درخت مسیر دقیقاً دو برگ دارد، اما درخت ستارهای با n رأس دارای n-1 برگ است. رأس منفرد در قرارداد معمول درجه صفر دارد.
مثال و تست کوتاه
گرافی همبند با 12 رأس و 11 یال حتماً درخت است. اگر یک یال دیگر به آن اضافه شود، تعداد یالها 12 میشود و دقیقاً یک دور ایجاد میگردد. حذف یالی از درخت اولیه نیز آن را به دو مؤلفه تبدیل میکند.
چکلیست حل تست
- درخت n رأسی دقیقاً n-1 یال دارد.
- بین هر دو رأس درخت یک مسیر یکتا است.
- هر درخت غیرتکرأسی دستکم دو برگ دارد.