قیاس منطقی دست به دست
قیاس منطقی دست به دست
در قضیه با نظریه گراف، یکی از شاخه‌های ریاضیات، قیاس دست به دست موقعیتی است که در آن هر گراف متناهی غیرجهت‌دار، تعداد رأس‌های با درجه فرد آن زوج است. به اصطلاح، در یک مهمانی که افراد با هم دست می‌دهند، تعداد زوجی از افراد هستند که با تعداد فردی از افراد دیگر دست داده باشند.
قیاس منطقی دست به دست نتیجه فرمول مجموع درجه است (که در بعضی مواقع قیاس منطقی دست به دست نامیده می‌شود)
در یک گرافی که در آن 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) از نظر محاسباتی با سخت‌ترین مسائل در این مقطع برابری می‌کند.
دیگر کاربردها
قیاس منطقی دست به دست در اثباتهای قیاس منطقی اسپرنر و موقعیت طولی ( خطی) تکه‌ای در مسئله کوهنوردی نیز استفاده می‌شود .
منابع
- Cameron, Kathie; Edmonds, Jack (1999), "Some graphic uses of an even number of odd nodes", Annales de l'institut Fourier, 49 (3): 815–827, MR 1703426.
- Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140. Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press.
- Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.
- Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, MR 0499124.
پانویس
- ↑ 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
- ↑ 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