قضیه منگر

قضیه منگر (انگلیسی: Menger's theorem) در رشتهٔ ریاضی در تئوری گراف این قضیه می‌گوید که در یک گراف، اندازهٔ یک مجموعه برش حداقل برابر با حداکثر تعداد مسیرهای ناهمگون است که می‌توان بین هر جفت رأس یافت. این قضیه توسط کارل منگر در سال ۱۹۲۷ اثبات شد، این ویژگی اتصال یک نمودار را مشخص می‌کند. این قضیه با قضیه برش حداکثر جریان، که یک نسخه وزن دار و لبه است، تعمیم می‌یابد و به نوبهٔ خود یک مورد خاص از قضیه دوگانگی قوی برای برنامه‌های خطی است.

اتصال لبه

نسخه اتصال لبه قضیه منگر به شرح زیر است:

به فرض این که G یک گراف متناهی بدون جهت و x و y دو رأس مجزا باشد. سپس اندازه حداقل برش لبه برای x و y (حداقل تعداد یال‌هایی که حذف آنها x و y را قطع می‌کند) برابر است با حداکثر تعداد مسیرهای جفتی لبه جدا از x به y. مفهوم نمودار G نسخه زیر است:

یک گراف به k یال متصل است (پس از حذف کمتر از k یال به هم متصل می‌ماند) اگر و تنها در صورتی که هر جفت رأس دارای k مسیرهای پراکنده یال باشد.

اتصال ورتکس

عبارت رأس اتصال قضیه منگر به شرح زیر است:

یک گراف به k راس متصل است (بیش از k رأس دارد و پس از حذف کمتر از k رأس به هم متصل می‌ماند) اگر و تنها اگر هر جفت رأس حداقل k مسیر ناهم‌پیوسته درونی بین آن‌ها داشته باشد.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Menger's theorem». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۶ مه ۲۰۲۴.