از ویکیپدیا، دانشنامه آزاد

 

این مقاله در مورد جنبه های ترکیبی حداکثر مجموعه های مستقل رأس در یک نمودار است. برای سایر جنبه های مجموعه های راس مستقل در تئوری نمودار ، مجموعه مستقل (تئوری نمودار) را ببینید . برای انواع دیگر مجموعه های مستقل ، به مجموعه مستقل (ابهام زدایی) مراجعه کنید .

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

در تئوری نمودار ، یک مجموعه مستقل حداکثر (MIS) یا مجموعه پایدار حداکثر یک مجموعه مستقل است که زیر مجموعه هیچ مجموعه مستقل دیگری نیست. به عبارت دیگر ، هیچ راس خارج از مجموعه مستقل وجود ندارد که بتواند به آن بپیوندد زیرا با توجه به ویژگی مجموعه مستقل حداکثر است.

به عنوان مثال ، در نمودار P_ {3}، مسیری با سه راس آ، ب، وج، و دو لبه آب و قبل از میلاد مسیح، مجموعه ها \ {b \} و \ {a ، c \}هر دو حداکثر مستقل هستند. مجموعه\{آ\} مستقل است ، اما حداکثر مستقل نیست ، زیرا زیر مجموعه ای از مجموعه مستقل بزرگتر است \ {a ، c \}. در همین نمودار ، حداکثر کلیک ها مجموعه ها هستند\ {a ، b \} و \{قبل از میلاد مسیح\}.

یک MIS نیز یک مجموعه غالب در نمودار است و هر مجموعه غالب مستقل باید حداکثر مستقل باشد ، بنابراین MIS ها را نیز مجموعه های غالب مستقل می نامند .

نمودار P3 دارای دو مجموعه حداکثر مستقل است. {a} یا {c} به تنهایی یک مجموعه مستقل را تشکیل می دهد ، اما حداکثر نیست.

دو نفر برترP_ {3}نمودارها حداکثر مجموعه های مستقل هستند در حالی که دو پایین مجموعه های مستقلی هستند ، اما حداکثر نیستند. حداکثر مجموعه مستقل در سمت چپ بالا نشان داده می شود.

یک نمودار ممکن است دارای بسیاری از MIS ها در اندازه های مختلف باشد. [1] بزرگترین یا احتمالاً چندین MIS به همان اندازه بزرگ یک نمودار را حداکثر مجموعه مستقل می نامند . نمودارهایی که در آن همه مجموعه های حداکثر مستقل دارای اندازه یکسان هستند نمودارهای پوشیده شده نامیده می شوند .

از عبارت "حداکثر مجموعه مستقل" نیز برای توصیف حداکثر زیرمجموعه های عناصر مستقل در ساختارهای ریاضی غیر از نمودارها ، و به ویژه در فضاهای برداری و ماترویدها استفاده می شود .

مجموعه های مستقل برای یک نمودار ستاره ای نمونه ای از تفاوت اندازه اندازه حداکثر مجموعه مستقل با حداکثر مجموعه مستقل است. در این نمودار ، نمودار ستاره S8 با انتخاب گره داخلی حداکثر مجموعه مستقل از اندازه 1 را دارد. همچنین با انتخاب هر گره ترک ، حداکثر (و همچنین حداکثر مجموعه مستقل) اندازه 8 را دارد.

دو مجموعه مستقل برای نمودار ستاره S_ {8} نشان می دهد که دو مجموعه حداکثر مستقل (در حداکثر صحیح) در اندازه چقدر متفاوت هستند.

دو مسئله الگوریتمی با MIS ارتباط دارند: یافتن یک MIS واحد در یک نمودار معین و لیست کردن تمام MIS ها در یک نمودار داده شده .

 

فهرست

تعریف [ ویرایش ]

برای یک نمودار G = (V ، E)، یک مجموعه مستقل سیک مجموعه مستقل ماکسیمال اگر برایv \ در V، یکی از موارد زیر درست است: [2]

  1. v \ در S
  2. N (v) \ cap S \ neq \ emptyset جایی که N (v) همسایگان را نشان می دهد v

موارد فوق را می توان مجدداً بیان کرد زیرا یک راس یا به مجموعه مستقل تعلق دارد یا حداقل دارای یک راس همسایه است که به مجموعه مستقل تعلق دارد. در نتیجه ، هر لبه نمودار حداقل یک نقطه پایانی دارد که در آن نیستس. با این حال ، این درست نیست که هر لبه نمودار حداقل یک یا حتی یک نقطه انتهایی داردس

توجه داشته باشید که هر همسایه به یک راس در مجموعه مستقل قرار دارد س نمی تواند در باشد س زیرا این رئوس با تعریف مجموعه مستقل جدا نیستند.

مجموعه های راس مرتبط [ ویرایش ]

اگر S در بعضی از نمودارها یک مجموعه حداکثر مستقل باشد ، یک نمودار حداکثر یا حداکثر زیرنویس کامل در نمودار مکمل است . جمع حداکثر مجموعه ای از رئوس است که یک زیرگراف کامل را القا می کند ، و این زیرمجموعه رأس هر زیرگراف کامل بزرگتر نیست. یعنی این یک مجموعه S است به گونه ای که هر جفت رئوس S با یک لبه متصل می شود و هر راس که در S نیست یک لبه حداقل یک راس در S را از دست می دهد . یک نمودار ممکن است کلیک های حداکثر زیادی داشته باشد ، در اندازه های مختلف. یافتن بزرگترین آنها حداکثر مشکل کلیک است .

بعضی از نویسندگان حداکثر را به عنوان بخشی از تعریف یک دسته می دانند و از حداکثر کلیک ها صرفاً به عنوان کلیک یاد می کنند.

چپ یک مجموعه حداکثر مستقل است. وسط یک دسته است ،K_ {3}، روی مکمل نمودار. سمت راست یک پوشش راس روی حداکثر مکمل مجموعه مستقل است.

مکمل یک مجموعه مستقل ماکسیمال، این است که، مجموعه ای از رئوس متعلق به مجموعه مستقل نیست، به شکل یک پوشش راسی حداقل . یعنی ، متمم یک پوشش راس است ، مجموعه ای از رئوس است که حداقل یک نقطه انتهایی از هر لبه را شامل می شود و از این نظر کم است که هیچ یک از رئوس آن را نمی توان با حفظ خاصیت پوششی بودن آن حذف کرد. حداقل پوشش راس در مکانیک آماری در ارتباط با مدل گاز شبکه سخت کره ، یک انتزاع ریاضی از انتقال حالت جامد سیال ، مورد مطالعه قرار گرفته است . [3]

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

نمودار کردن خصوصیات خانواده [ ویرایش ]

خانواده های نمودار خاصی نیز از نظر حداکثر کلیک یا مجموعه حداکثر مستقل مشخص شده اند. مثالها شامل نمودارهای غیرقابل کاهش حداکثر کلی و نمودارهای غیر قابل کاهش حداکثر کلیک ارثی است. نمودار گفته می شود حداکثر دار و دسته غیر قابل تقلیل اگر هر دسته حداکثری تا به لبه است که متعلق به هیچ دسته حداکثری دیگر، و ارثی حداکثر دار و دسته غیر قابل تقلیل اگر ملک همان درست است برای هر زیرگراف القایی است. [4] ارثی حداکثر باند نمودار غیر قابل تقلیل شامل گراف آزاد-مثلث ، گرافهای دوبخشی ، و نمودار فاصله .

كراگ ها را می توان گرافیكی توصیف كرد كه در آن هر كلیك حداكثر از هر مجموعه حداكثر مستقل تلاقی كرده باشد و در آن ویژگی خاص در همه زیرگرافهای القایی صادق باشد.

منبع

https://en.wikipedia.org/wiki/Maximal_independent_set