موضوع مقاله: بستار تعدی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بستار تعدی | مقدمه: در ریاضیات بستار تعدی (تراگذری) یک رابطه دوتایی R در مجموعه X، کوچکترین رابطه از X، شامل R که متعدی باشد. | ## بخش 1: بستار تعدی | برای مثال اگر X یک مجموعه‌ای از فرودگاه‌ها و x R y به معنی "یک پرواز مستقیم از فرودگاه x به فرودگاه y وجود دارد" (برای x و y در X) باشد، سپس بستار تعدی R در X، رابطه R+ است به طوری که x R+ y به معنی آن است که "ممکن است برای پرواز از x به y یک یا چند پرواز انجام شود". به عبارت دیگر بستار تعدی مجموعه‌ای از تمام نقاطی را به شما می‌دهد که می‌توانید از هر نقطهٔ شروع به آن‌ها برسید. به صورت دقیق تر، بستار تعدی رابطه باینری R در مجموعه X، کوچکترین رابطه متعدی روی مجموعه X است به طوری که R+ شامل R باشد . اگر رابطهٔ دودویی به خودی خود متعدی باشد بسطار تعدی آن خود رابطه می‌شود؛ در غیر این صورت بستار تعدی رابطه‌ای دیگر می‌شود. روابط متعدی و نمونه‌ها رابطه R در مجموعه X متعدی است، اگر برای تمام x و y و zهای موجود در Xکه x R y و ،نتیجه بدهد . نمونه‌هایی از روابط متعدی عبارتند از: رابطهٔ برابری در هر مجموعه‌ای، رابطهٔ "کوچکتر یا مساوی " در هر مجموعهٔ مرتب خطی، و رابطهٔ "x قبل از y متولد شده" در مجموعهٔ همه مردم. یک مثال از یک رابطهٔ غیر متعدی: «میتوان از شهر y با پرواز مستقیم به شهر x رسید» در مجموعهٔ تمام شهرها. تنها به دلیل وجود یک پرواز مستقیم از شهری به شهر دوم و یک پرواز مستقیم از شهر دوم به سوم، پرواز مستقیم از شهر اول به شهر دوم وجود ندارد. بستار تعدی این رابطه متفاوت است، یعنی «دنباله‌ای از پروازهای مستقیم که در شهر X شروع می‌شود و در شهر y به پایان می‌رسد». به عنوان مثال یک رابطهٔ غیر تعدی که نسبت به تعدی بودن بسته نیست «روز x بعد از روز y در هفته هست». | ## بخش 2: بستار تعدی | این بستار تعدی این رابطه است: "چند روز x می‌آید بعد از y" که بدیهی است برای تمام روزهای هفته x و y (این معادل یک دستگاه دکارتی است که"x , y روزهای هفته‌اند") اثبات و شرح برای هر رابطه R، بستار تعدی R همیشه وجود دارد. برای مجموعه‌های متناهی ما می‌توانیم ساخت بستار تعدی را با شروع از R و اضافه کردن لبه‌های متعدی پیش ببریم. برای هر مجموعه X ما می‌توانیم ثابت کنیم که بستار تعدی توسط عبارت زیر به دست می‌آید: که در آن توان i از R به شکل زیر تعریف شده: و برای که در آن نشان دهنده ترکیب روابط است. برای نشان دادن تعریف بالا که R+ کوچکترین رابطهٔ متعدی حاوی R است، نشان می‌دهیم که آن شامل R است و آن متعدی است و کوچکترین مجموعه‌ای است که با هر دو این ویژگی‌ها را داراست. متعدی است: تمامی اعضای در یکی از ، بنابراین باید با استدلال زیر متعدی می‌شود: اگر و ، سپس از خاصیت شرکت پذیری، (و در) به خاطر تعریف . و چون متعدی است، هر گاه ، با توجه به ساختار و تعریف متعدی بودن، بنابراین، ، و بنابراین هست . برای به دست آوردن رابطه هم‌ارزی جدید یا preorder یکی باید بستار تعدی (یازتابی و تقارن در مورد روابط هم‌ارزی—خودکار هستند) باشد. در علوم کامپیوتر، مفهوم بستار تعدی را می‌توان به عنوان ساخت یک ساختار داده که امکان پاسخ به پرسش قابل دسترسی در نظر گرفت. یک رابطهٔ دوتایی فقط به شما می‌گوید که گره a به گره b متصل است و گره b به گره c متصل است، پس از ساخته شدن بستار تعدی، همان‌طور که در شکل زیر نشان داده شده‌است، در O(1) عملیات یکی می‌تواند تعیین کند که گره d قابل دسترسی است از گره یک. داده ساختارها معمولاً به عنوان یک ماتریس ذخیره می‌شوند، بنابراین اگر ماتریس[۱ ۴] = ۱ و یعنی که گره ۱ می‌تواند برود به گره ۴ از طریق یک یا چند گره. | ## بخش 3: بستار تعدی | این بستار تعدی یک گراف جهت‌دار غیرمدور (DAG) رابطهٔ دسترسی و از و مجموعهٔ مرتب جزیی است. در منطق و محاسبات پیچیده این بستارهای تعدی باینری رابطه به‌طور کلی نمی‌تواند بیان شود در مرتبه اول منطق(FO). این به این معنی است که کسی نمی‌تواند فرمولی بنویسد با استفاده از گزاره نمادهای R و T که راضی خواهد بود در هر مدل اگر و تنها اگر T بستار تعدی از Rاست. در محدود مدل تئوریبرای اولین بار-سفارش منطق (FO) تمدید با یک متعدی بسته شدن اپراتور است که معمولاً به نام متعدی بسته شدن منطقو به صورت مختصر FO(TC) یا فقط TC. دلیل این است که متعدی بسته شدن اموال است یک رابطه نزدیک با NL-کامل مشکل STCON برای پیدا کردن کارگردانی مسیر در یک گراف. زمانی که متعدی بسته اضافه شده‌است به مرتبه دوم منطق به جای ما به دست آوردن PSPACE. در پایگاه داده‌های پرس و جو زبان از سال 1980s پایگاه داده اوراکل اجرا کرده‌است اختصاصی SQL فرمت اتصال... شروع با که اجازه می‌دهد تا محاسبه متعدی بسته شدن به عنوان بخشی از یک اعلانی پرس و جو. | ## جمع‌بندی | الگوریتم الگوریتم‌های کارآمد برای محاسبه بستار تعدی یک گراف را می‌توان در Nuutila (1995) پیدا کرد.