قیاس منطقی دست به دست

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
در این گراف، یک تعداد زوج از رئوس ( چهار راس عدد گذاری شده 2 ، 4 ، 5 و 6 ) درجات فرد دارند . مجموع درجات رئوس 2 + 3 + 2 + 3 + 3 + 1 = 14, است که دو برابر عدد یال‌هاست .

قیاس منطقی دست به دست
در قضیه با نظریه گراف، یکی از شاخه های ریاضیات ، قیاس دست به دست موقعیتی است که در آن هر گراف بدون جهت محدود، یک تعداد زوج راس با درجه فرد دارد . به اصطلاح، در یک مهمانی که افراد با هم دست می دهند، تعداد زوجی از افراد باید با تعداد فردی از افراد دیگر دست داده باشند.
قیاس منطقی دست به دست نتیجه فرمول مجموع درجه است ( که در بعضی مواقع قیاس منطقی دست به دست نامیده می شود)

\sum_{v\in V} \deg(v) = 2|E|

در یک گراف‌ی که در آن v راس و E یال می باشد .هر دو نتایج توسط لئونهارد اویلر(۱۷۳۶)در روزنامه معروف وی در سون بریج کونیگز برگ اثبات گردیدند که سبب آغاز مطالعه نظریه گراف شد.
رئوس با درجه فرد در یک گراف در بعضی مواقع گره های فرد یا رئوس فرد نامیده می شوند; در این مجموعه اصطلاحات، قیاس منطقی دست به دست می تواند این توضیح را ارائه دهد که هر گراف‌ی یک عدد زوج از گره های فرد دارد .

اثبات[ویرایش]

اثبات فرمول مجموع درجه اویلر از تکنیک دوبار شمارش استفاده می کند : او تعداد جفتهای وابسته یا متلاقی( v،e) را که در آن e یال و v نقطه پایانی هستند به دو صورت شمارش می کند . راس v به جفت (deg(v تعلق دارد که در آن (deg(v ( درجه v ) تعداد یال های وابسته با آن است. بنابراین تعداد جفتهای وابسته ( متلاقی) مجموع درجات می باشد. در حالی که، هر یال در نمودار دقیقاً به دو جفت متلاقی متعلق است، برای هر کدام از نقاط پایانی یک جفت وجود دارد، در نتیجه تعداد جفتهای متلاقی۲|E| است . از آنجایی که این دو فرمول عناصر مشابهی را شمارش می کنند باید ارزشهای برابر داشته باشند.
در یک مجموعه اعداد صحیح، توازن ( زوجیت ) مجموعه با ارقام زوج در جمع تاثیری نمی‌گذارد ; جمع کل در صورتی زوج می شود که یک تعداد زوج از ارقام فرد وجود داشته باشد و زمانی که یک تعداد فرد از اعداد فرد موجود باشد آنگاه فرد می گردد. از آنجایی که یک طرف فرمول مجموع درجات عدد زوج ۲|E| است، مجموع طرف دیگر باید تعداد زوجی از ارقام فرد را داشته باشد. این بدین معنی است که باید تعداد زوجی از رئوس درجه فرد وجود داشته باشد.

گراف‌های منظم[ویرایش]

فرمول مجموع درجات این را متذکر می شود که هر گراف‌های منظم (r) با n راس rn/۲ یال دارد.[۱] خصوصاً، اگر r فرد است، تعداد یال ها باید به صورت زوج به r بخشپذیر باشند.

گراف‌های نامحدود[ویرایش]

قیاس دست به دست به گراف‌های نامحدود صدق نمی‌کند، حتی زمانی که آن‍ها تنها یک تعداد متناهی از رئوس درجه فرد دارند. به عنوان مثال، گراف مسیر نامحدود با یک نقطه پایانی تنها دارای یک راس درجه فرد به جای داشتن یک تعداد زوج از رئوس است.

گراف‌های تبادل[ویرایش]

ساختارهای ترکیبی متعددی که توسط رادموندز و کامرون ۱۹۹۹ فهرست شده اند، ممکن است با ارتباط دادنشان به رئوس فرد در یک " گراف تبادل" مناسب به صورت عدد زوج نشان داده شوند . برای مثال، همانگونه که C.A.B smithاثبات کرد، در هر گراف مکعبی G باید یک تعداد زوج از دایره های همیلتونی در مسیر هر یال ثابت uv وجود داشته باشد; توماسون (۱۹۷۸) از یک اثبات بر اساس قیاس منطقی دست به دست استفاده کرد تا بتواند این نتیجه را به گراف‌های G در آنها همه رئوس درجات فرد دارند تعمیم دهد . توماسون یک گراف تبادل H تعریف کرد که در آن رئوسش تبادل یک به یک با راه های همیلتون دارند که از u شروع می شوند و در مسیر v ادامه پیدا می کنند. دو تا از این راه ها p۱ و p۲ از یک یال به H وصل هستند، اگر یکی با اضافه کردن یک یال جدید به انتهای P۱ و حذف کردن یال دیگر از وسط P۱ به P۲ برسد، این یک رابطه سیستماتیک می شود. در نتیجه H یک نمودار غیر مستقیم است . اگر راه P در راس W ختم شود، پس راس مرتبط با P در H درجه برابر با تعداد راه هایی دارد که در آن P می تواند از طریق یک یال که با u ارتباط بازگشتی ندارد گسترده شود. این بدین معنی است که درجه این راس در H یا deg(w)-۱ ( یک عدد زوج) می باشد در صورتی که P یک بخشی از دایره همیلتونی را در مسیر uv تشکیل ندهند، و یا deg(w)-۲ ( یک عدد فرد ) می شود اگر P بخشی از دایره همیلتونی را در مسیرuv تشکیل دهد. از آنجایی که H تعداد زوجی از رئوس فرد را دارد ، G باید یک تعداد زوج از دایره های همیلتونی در مسیر uv را داشته باشد.

پیچیدگی محاسبات[ویرایش]

در ارتباط با روش گراف تبادل برای اثبات موجودیت ساختارهای ترکیبی، جالب است که بپرسیم این ساختارها چقدر کاربردی می توانند باشند. برای مثال، فرض کنید به یکی یک دایره همیلتونی در گراف مکعبی به عنوان ورودی داده شده است ; در فرضیه smith این گفته می شود که در ادامه آن یک دایره دومی هم وجود دارد. با چه سرعتی این دایره دوم پیدا می شود؟ پاپادی میتریو (۱۹۹۴) پیچیدگی محاسباتی اینگونه سوالات را یا به طور کلی تر پیدا کردن یک راس درجه فرد دومی را در زمانی که یک راس فرد تنها در یک گراف تعریف شده مجازی داده شده است بررسی کرد . او مقطع پیچیدگی PPA را تعریف کرد تا اینکه بتواند از این قبیل مسئله ها را حقظ کند; یک مقطع خیلی مربوط به روی گراف‌های مستقیم تعریف گردید، PPAD، و توجه ویژه ای را در نظریه بازی الگوریتمی به خود جلب کرد زیرا محاسبه موازنه نش (Nash) از نظر محاسباتی با سخت ترین مسائل در این مقطع برابری می کند.[۲]

دیگر کاربردها[ویرایش]

قیاس منطقی دست به دست در اثباتهای قیاس منطقی اسپرنر و موقعیت طولی ( خطی) تکه ای در مسئله کوهنوردی نیز استفاده می شود .

منابع[ویرایش]

پانویس[ویرایش]

  1. Aldous, Joan M.; Wilson, Robin J. (2000), "Theorem 2.2", Graphs and Applications: an Introductory Approach, Undergraduate Mathematics Series, The Open University, Springer-Verlag, p. 44, ISBN 9781852332594 
  2. Chen, Xi; Deng, Xiaotie (2006), "Settling the complexity of two-player Nash equilibrium", Proc. 47th Symp. Foundations of Computer Science, pp. 261–271, doi:10.1109/FOCS.2006.69, ECCC TR05-140