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

بندانگشتی|دنباله نمونه‌ای از درختان ریشه‌دار که از مجموعه‌ای با ۳ برچسب (قرمز، سبز، آبی) برچسب‌گذاری شده‌اند، که در آن درخت nام حداکثر n گره دارد و هیچ درختی در هیچ درخت بعدی در این دنباله قابل جاسازی در inf نیست.
**قضیه درخت کروسکال** نقشی اساسی در علم کامپیوتر ایفا می‌کند. این قضیه توسط آندرو وزسونی حدس زده شده و توسط جوزف کروسکل ثابت شده‌است؛ شخص نش ویلیامز هم کمی در اثبات این قضیه نقش داشته‌است. این قضیه از زمانی که یک مثال برجسته در ریاضیات معکوس شناخته شد به عنوان بیانیه ای است که نمی‌توان آن را با ATR0 ثابت کرد (یک شکل از ریاضیات نامحدود معکوس) و یکی از استفاده‌های این قضیه شدت رشد سریع تابع درخت است.

<nowiki/>

در سال ۲۰۰۴ این نتیجه کلی از درختان، به عنوان قضیه رابرتسون–سیمورگراف، به گراف‌ها تعمیم یافت. یکی از نتایج ثابت شده از آن در ریاضی معکوس بسیار برجسته است و حتی ممکن است ریاضیات را برای رسیدن به توابع SSCG با رشد سریعتر هدایت کند.

## بیانیه
ما اثبات‌کننده این قضیه را نش ویلیامز در نظر می‌گیریم اگرچه فرمول کروسکال به گونه ای بهتر است. یک درخت ریشه دار را T و دو رأس را V و W در نظر بگیرید. V را جانشین W گویند اگر یک مسیر از ریشه تا V شامل W هم شود و V را جانشین مستقیم W گویند اگر مسیر W تا V شامل رأس دیگری نباشد.X را یک مجموعه نیمه مرتب شده در نظر بگیرید. T1 و T2 را دو درخت ریشه دار با رأسهایی در مجموعه X در نظر بگیرید، می‌گوییم T1 در T2 جایگذاری شده‌است اگر یک نگاشت مثل F از رأس‌های T1 به رأس‌های T2 وجود داشته باشد به گونه ای که
* به ازای هر رأس v در T1، رأس v از رأس به وجود آمده طبق نگاشت f مقدم تر باشد.
* اگر w جانشین v در درخت T1 باشد، آنگاه نگاشت w هم جانشین نگاشت v باشد.
* اگر w1 و w2 دو رأس مجاور و جانشین v باشند، آنگاه مسیر نگاشت w1 به نگاشت w2 در درخت T2 شامل نگاشت v باشد.

نتیجه می‌شود که به ازای هر درخت ریشه دار که رأس‌های آن‌ها در مجموعه X باشد یک درخت مثل i داریم که در درخت j جایگذاری شده باشد به شرط اینکه i از j کوچکتر باشد.

## کار فریدمن
برای یک مجموعه محدود از رأس‌ها مثل X، قضیه درخت کروسکال می‌تواند توسط قضیه مرتبه دوم ریاضی بیان و ثابت شود. اگرچه، مثل قضیه گودزتین یا قضیه پاریس-هرینگتون، در بعضی موارد خاص این قضیه می‌تواند توسط زیرسیستم‌های مرتبه دوم ریاضی خیلی کندتر از زیرسیستم‌ها بیان شود. این موضوع اولین بار توسط هاروی فریدمن در اوایل سال ۱۹۸۰ مشاهده شد، یک موفقیت که بعدها زمینه ریاضیات معکوس شد. در این مورد که درختان بدون رأس برچسب گذاری شده در نظر گرفته شوند، فریدمن کشف کرد که نتیجه در ATR غیرقابل اثبات است پس اولین مثال از نتیجه قابل پیش‌بینی با یک اثبات غیرقابل پیش‌بینی و قابل اعتماد زده شد. این مورد از قضیه هنوز در Π11-CA۰ **قابل اثبات است، اما با اضافه کردن یک «شرط جزئی» به تعریف مرتب‌سازی درخت‌ها در بالا، او یک تغییر طبیعی در تئوری یافت که در این سیستم غیرقابل اثبات بود** . مدت‌ها بعد، رابرستون سیمور یک قضیه غیرقابل اثبات دیگر را در Π11-CA۰ **مطرح کرد**.

تحلیل و بررسی وصفی، استحکام قضیه کراسکال را تأکید می‌کند.

### درخت(۳)
فرض کنید (P(n این بیانیه باشد

: وجود دارد تعدادی m که اگر *T*1,... ,*T**m* یک دنباله محدود از درخت‌های ریشه دار باشد، هروقت *T**k* دارای *n*+*k* رأس باشد آنگاه *T**i*&#x20;&#x2264;&#x20;*T**j* برای برخی *i* 1,... ,*T**m ***از درخت‌های ریشه دار برچسب گذاری شده از یک مجموعه n برچسبی، وقتی که ****<sub>Ti حداکثر i رأس دارد، در این شرایط</sub>**  *T*i &#x20;&#x2264;&#x20; *T*j صدق نمی‌کند برای هر *i* 64(4) هستند که خیلی کوچکتر از کران پایین (187196)(1) هستند. می‌توان نشان داد که درجه رشد تابع درختی در سلسله مراتب رشد سریع حداقل  هست.

## جستارهای وابسته
* قضیه پاریس–Harrington
* قضیه Kanamori–McAloon
* قضیه رابرتسون–سیمور

## یادداشت
: فریدمن در ابتدا این تابع را با n]TR] نشان می‌داد.
: (n(k تعریف می‌شود به عنوان بلندترین دنباله ممکن که با یک الفبای k حرفی می‌تواند ساخته شود به گونه ای که هیچ بلوک از حرف x, ,... ,x2i **یک بلوک از دنباله بعدی**  xj,... ,x2j نباشد. *n *(1) = ۳ و *n *(2) = ۱۱ و *n *(3)> 2 [7199] 158386.

## منابع

* رده:خوش بنیانی
رده:درختان (نظریه گراف)
رده:صفحه‌های دارای ارجاع با متغیر تکراری
رده:قضیه‌ها در ریاضیات گسسته
رده:منطق ریاضی
رده:نظریه ترتیب
رده:ویکی‌سازی رباتیک