قضیه درخت کروسکال

قضیه درخت کروسکال نقشی اساسی در علم کامپیوتر ایفا می کند. این قضیه توسط آندرو وزسونی حدس زده شده و توسط جوزف کروسکل ثابت شده است؛ شخص نش ویلیامز هم کمی در اثبات این قضیه نقش داشته است. این قضیه از زمانی که یک مثال برجسته در ریاضیات معکوس شناخته شد به عنوان بیانیه ای است که نمی توان آن را با ATR0 ثابت کرد (یک شکل از ریاضیات نامحدود معکوس) و یکی از استفاده های این قضیه شدت رشد سریع تابع درخت است.
به ازای هر رأس v در T1، رأس v از رأس به وجود آمده طبق نگاشت f مقدم تر باشد.
اگر w جانشین v در درخت T1 باشد، آنگاه نگاشت w هم جانشین نگاشت v باشد.
اگر w1 و w2 دو رأس مجاور و جانشین v باشند، آنگاه مسیر نگاشت w1 به نگاشت w2 در درخت T2 شامل نگاشت v باشد.
در سال ۲۰۰۴ این نتیجه کلی از درختان، به عنوان قضیه رابرتسون–سیمورگراف، به گراف ها تعمیم یافت. یکی از نتایج ثابت شده از آن در ریاضی معکوس بسیار برجسته است و حتی ممکن است ریاضیات را برای رسیدن به توابع SSCG با رشد سریعتر هدایت کند.
ما اثبات کننده این قضیه را نش ویلیامز در نظر می گیریم اگرچه فرمول کروسکال به گونه ای بهتر است. یک درخت ریشه دار را T و دو رأس را V و W در نظر بگیرید. V را جانشین W گویند اگر یک مسیر از ریشه تا V شامل W هم شود و V را جانشین مستقیم W گویند اگر مسیر W تا V شامل رأس دیگری نباشد.X را یک مجموعه نیمه مرتب شده در نظر بگیرید. T1 و T2 را دو درخت ریشه دار با رأسهایی در مجموعه X در نظر بگیرید، می گوییم T1 در T2 جایگذاری شده است اگر یک نگاشت مثل F از رأس های T1 به رأس های T2 وجود داشته باشد به گونه ای که
نتیجه می شود که به ازای هر درخت ریشه دار که رأس های آن ها در مجموعه X باشد یک درخت مثل i داریم که در درخت j جایگذاری شده باشد به شرط اینکه i از j کوچکتر باشد.