گراف دو بخشی

نمونه ای از نمودار دو بخشی بدون چرخه

در حوزه ریاضی نظریه گراف ، نمودار دو بخشی (یا گراف ) گرافی است که رئوس آن را می توان به دو مجموعه جداگانه و مستقل تقسیم کرد $تو$ و $V$ به گونه ای که هر یال یا لبه یک راس را به داخل متصل می کند $تو$ به یک در $V$ . مجموعه های $تو$ و $V$ معمولاً به قسمتهای نمودار گفته می شوند. به طور معادل ، نمودار دو قسمتی گرافی است که شامل هیچ چرخه طول فرد نیست . [1] [2]

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

یکی اغلب می نویسد $G = (U ، V ، E)$ برای نشان دادن یک گراف دو بخشی که پارتیشن آن دارای قطعات است $تو$ و $V$ ، با $E$ علامت گذاری به لبه های نمودار. اگر نمودار دو بخشی متصل نباشد ، ممکن است بیش از یک تقسیم دو بخشی داشته باشد. [5] در این مورد ، $(U ، V ، E)$ علامت گذاری برای تعیین یک تقسیم دو بخشی خاص که ممکن است در یک برنامه مهم باشد مفید است. اگر $| U | = | V |$ ، یعنی اگر این دو زیر مجموعه دارای کاردینیت برابر باشند ، پس $G$ نمودار دو بخشی متعادل نامیده می شود . [3] اگر همه رئوس در یک طرف دو قسمت تقسیم شده اند ، درجه یکسانی دارند ، پس $G$ بی نظمی نامیده می شود .

فهرست

مثالها [ ویرایش ]

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

مثال دیگری که به طور طبیعی نمودارهای دو بخشی نشان داده می شود ، مسئله بهینه سازی راه آهن ( NP- کامل ) است که در آن ورودی یک جدول قطارها و توقف آنها است و هدف این است که مجموعه ای از ایستگاه های قطار را در کمترین حد ممکن پیدا کنید تا هر حداقل از یکی از ایستگاه های انتخاب شده بازدید می کند. این مسئله را می توان به عنوان یک مسئله مجموعه غالب در یک نمودار دو بخشی که یک راس برای هر قطار و هر ایستگاه دارد و یک لبه برای هر جفت یک ایستگاه و یک قطار که در آن ایستگاه متوقف می شود ، مدل کرد. [7]

نمونه سوم در زمینه دانشگاهی سکه شناسی است. سکه های باستانی با استفاده از دو برداشت مثبت از طرح (روبرو و معکوس) ساخته می شوند. نمودارهای سکه شناسی برای نشان دادن تولید سکه ها نمودارهای دو بخشی هستند. [8]

نمونه های انتزاعی تر شامل موارد زیر است:

هر درختی دوتکه است. [4]
نمودارهای چرخه ای با تعداد راس های زوج دو بخشی هستند. [4]
هر نمودار مسطحی که تمام چهره های آن حتی یکسان است ، دوتکه است. [9] موارد خاص این نمودارها و نمودارهای مربعی است که در آنها هر صورت داخلی از 4 لبه تشکیل شده است و هر راس داخلی چهار همسایه یا بیشتر دارد. [10]
گراف دوبخشی کامل در mو N راس، مشخص شده توسط K n و m نمودار دوبخشی است $G = (U ، V ، E)$ ، جایی که U و V به ترتیب مجموعه های جداگانه ای از اندازه m و n هستند ، و E هر راس U را با تمام رئوس V متصل می کند . به این ترتیب که K m، n دارای لبه های mn است . [11] نمودارهای تاج کاملاً مربوط به نمودارهای دوتکه ای کامل هستند که از نمودارهای کامل و کامل با حذف لبه های یک تطابق کامل تشکیل شده اند . [12]
نمودار مکعب ، مکعب جزئی ، و نمودار متوسط دوبخشی است. در این نمودارها ، راسها ممکن است توسط بردارهای برچسب گذاری شده باشند ، به گونه ای که دو راس مجاور باشند اگر و فقط در صورت اختلاف بردارهای bitve در یک موقعیت واحد. با جداسازی رأس هایی که بردارهای bit آنها دارای تعداد زوج یکسان از رأس ها با تعداد عجیب و غریب است ، می توان یک تقسیم دوتایی ایجاد کرد. درختان و نمودارهای مربع نمونه هایی از نمودارهای متوسط را تشکیل می دهند و هر نمودار متوسط یک مکعب جزئی است. [13]

خصوصیات [ ویرایش ]

گراف های دو بخشی ممکن است به چندین روش مختلف مشخص شوند:

یک نمودار دو بخشی است اگر و فقط اگر شامل یک چرخه فرد نباشد . [14]
یک نمودار دو بخشی است اگر و فقط اگر دو رنگ باشد ، (یعنی تعداد رنگی آن کمتر از یا برابر با 2 است). [3]
طیف از یک گراف متقارن است اگر و تنها اگر یک گراف دو بخشی است. [15]

قضیه کونیگ و گراف های کامل [ ویرایش ]

در گرافهای دوتایی ، اندازه حداقل پوشش راس برابر است با اندازه حداکثر تطبیق . این قضیه کونیگ است . [16] [17] یک شکل جایگزین و معادل این قضیه این است که اندازه حداکثر مجموعه مستقل به علاوه اندازه حداکثر مطابقت با تعداد رئوس برابر است. در هر نمودار بدون رئوس جدا شده اندازه حداقل پوشش لبه به علاوه اندازه حداکثر مطابقت با تعداد رئوس برابر است. [18]ترکیب این برابری با قضیه Kőnig به این واقعیت ها منجر می شود که ، در نمودارهای دوتایی ، اندازه حداقل پوشش لبه برابر است با اندازه حداکثر مجموعه مستقل ، و اندازه حداقل پوشش لبه به علاوه اندازه حداقل پوشش راس برابر است با تعداد رئوس.

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

طبق قضیه قوی گراف کامل ، نمودارهای کامل دارای یک توصیف گراف ممنوع هستند که شبیه گرافهای دو قسمتی است: یک نمودار دو بخشی است اگر و فقط اگر چرخه فرد به عنوان یک زیرگراف نداشته باشد ، و یک نمودار کامل است اگر و فقط اگر داشته باشد بدون چرخه فرد یا مکمل آن به عنوان یک زیرنویس القایی . نمودارهای دوتکه ، نمودارهای خطی نمودارهای دوتایی و مکمل های آنها ، چهار مورد از پنج کلاس اساسی گرافهای کامل را که در اثبات قضیه قوی و کامل نمودار استفاده می شود ، تشکیل می دهند. [20]

درجه [ ویرایش ]

برای یک راس ، به تعداد رئوس مجاور درجه راس گفته می شود و مشخص می شود $\ deg (v)$ . فرمول مجموع درجات برای کشورهای گراف دو بخشی که

$\ sum_ {v \ in V} \ deg (v) = \ sum_ {u \ in U} \ deg (u) = | E | \،.$

توالی درجه نمودار دو بخشی جفت لیستی است که هرکدام دارای درجات دو قسمت هستند $تو$ و $V$ . به عنوان مثال ، نمودار کامل دو بخشی K 3،5 دارای توالی درجه است $(5،5،5) ، (3،3،3،3،3،3)$ . نمودارهای دو بخشی ایزومورفیک توالی درجه یکسانی دارند. با این حال ، توالی درجه ، به طور کلی ، یک نمودار دو بخشی را مشخص نمی کند. در بعضی موارد ، نمودارهای دو پارچه غیرهم شکل ممکن است توالی درجه یکسانی داشته باشند.

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

ارتباط با گرافها و نمودارهای جهت دار [ ویرایش ]

ماتریس biadjacency از یک گراف دو بخشی $(U ، V ، E)$ یک ماتریس اندازه (0،1) است $| U | \ بار | V |$ که برای هر جفت رأس مجاور یک و برای رئوس غیر مجاور یک صفر دارد. [21] از ماتریس های Biadjacency می توان برای توصیف معادل سازی بین نمودارهای دو بخشی ، ابر نمودارها و نمودارهای جهت دار استفاده کرد.

hypergraph یک ساختار ترکیبی است که، مانند یک گراف بدون جهت است، راس و لبه است، اما که در آن لبه ممکن است مجموعه های خودسرانه از رئوس به جای داشتن به دقیقا دو نقطه انتهایی. نمودار دو بخشی $(U ، V ، E)$ ممکن است برای مدل سازی یک ابرنواختر استفاده شود که در آن U مجموعه رئوس هایپراگراف است ، V مجموعه hyperedges است و E شامل یک لبه از راس hypergraph v به یک لبه hypergraph e دقیقا زمانی که v یکی از نقاط انتهایی است الکترونیکی . تحت این مکاتبات ، ماتریس های انحصار گرافیکی نمودارهای دو بخشی دقیقاً ماتریس های مربوط به ابر نوشتارهای مربوطه هستند. به عنوان یک مورد خاص از این مکاتبات بین نمودارهای دو بخشی و ابر نمودار ، هر چند نمودار(یک نمودار که در آن ممکن است دو یا چند لبه بین همان دو رئوس وجود داشته باشد) ممکن است به عنوان یک ابر نوشتار تفسیر شود که در آن برخی از hyperredge ها دارای مجموعه های نقطه انتهایی برابر هستند و توسط یک نمودار دو بخشی ارائه می شود که چندین مجاورت ندارد و در آن رئوس در یک طرف دو قسمت همه درجه دو دارند. [22]

تفسیر مجدد مشابه ماتریس همجواری ممکن است برای نشان دادن مکاتبه یک به یک بین نمودارهای هدایت شده (در تعداد مشخصی از راس های برچسب خورده ، اجازه حلقه های خودی) و نمودارهای دو طرفه متعادل ، با تعداد راس های مشابه در هر دو طرف تقسیم دو طرفه برای اینکه ، ماتریس مجاورت یک نمودار جهت دار با n راس می تواند از هر ماتریس (0،1) اندازه باشد $n \ n بار$ ، که می تواند بعنوان ماتریس همجواری نمودار دو بخشی با n راس در هر طرف تقسیم دو بخشی تفسیر شود . [23] در این ساخت و ساز ، نمودار دو بخشی ، پوشش دوتایی از نمودار جهت دار است.

الگوریتم ها [ ویرایش ]

آزمایش دو طرفه بودن [ ویرایش ]

می توان با استفاده از جستجوی عمق اول ، آزمایش کرد که آیا نمودار دو بخشی است و یا یک چرخه دو رنگ (در صورت دو بخشی) یا یک چرخه فرد (در صورت عدم وجود آن) را در زمان خطی برگرداند . ایده اصلی این است که به هر راس رنگی که در جنگل جستجوی عمق اول با رنگ والد آن متفاوت است اختصاص داده شود ، و رنگ ها را در یک پیش پیمایش از جنگل عمق جستجو اول اختصاص دهید . این لزوماً باعث ایجاد دو رنگ جنگل پوشا می شودمتشکل از لبه هایی است که رئوس را به والدین خود متصل می کند ، اما ممکن است برخی از لبه های غیر جنگلی را به درستی رنگ نکند. در یک جنگل جستجوی عمق اول ، یکی از دو نقطه انتهایی هر لبه غیر جنگلی از اجزای نقطه پایانی دیگر است و وقتی عمق برای اولین بار لبه ای از این نوع را کشف کرد ، باید بررسی کند که این دو راس دارای رنگ های مختلف هستند. اگر این کار انجام نشود ، مسیر در جنگل از جد به نسل ، همراه با لبه نامناسب ، یک چرخه عجیب و غریب را تشکیل می دهد ، که همراه با نتیجه عدم تقسیم نمودار از الگوریتم بازگردانده می شود. با این حال ، اگر الگوریتم بدون شناسایی یک چرخه فرد از این نوع خاتمه یابد ، پس هر لبه باید به درستی رنگ آمیزی شود ، و الگوریتم رنگ آمیزی را همراه با نتیجه دو بخشی بودن نمودار برمی گرداند. [24]

متناوباً ، یک روش مشابه ممکن است با جستجوی گسترده اول به جای جستجوی عمق اول استفاده شود. مجدداً ، به هر گره ، به ترتیب وسیع تر و اول ، رنگ مخالف والدین خود در جنگل جستجو داده می شود. اگر هنگامی که یک راس رنگی است ، لبه ای وجود دارد که آن را به یک راس قبلی رنگ با همان رنگ متصل می کند ، این لبه همراه با مسیرهایی که در جنگل جستجو برای اولین بار وجود دارد ، دو نقطه انتهایی آن را به پایین ترین جد مشترک خود متصل می کند چرخه فرد اگر الگوریتم بدون یافتن چرخه ای عجیب و غریب از این طریق خاتمه یابد ، پس باید رنگ مناسبی پیدا کرده باشد و با خیال راحت بتواند نتیجه بگیرد که نمودار دو بخشی است. [25]

برای نمودار تقاطع از $n$ بخشهای خط یا اشکال ساده دیگر در صفحه اقلیدسی ، می توان آزمایش کرد که آیا نمودار دو قسمتی است و یا یک چرخه دو رنگ یا یک فرد را در زمان باز می گرداند $O (n \ log n)$ ، حتی اگر نمودار خود تا حدودی داشته باشد ${\ displaystyle O \ چپ (n ^ {2} \ راست)}$ لبه ها. [26]

عرضی چرخه فرد [ ویرایش ]

مقاله اصلی: عرض چرخه فرد

نمودار با عرض چرخه فرد به اندازه 2: حذف دو رئوس پایین آبی یک نمودار دوتایی را به جا می گذارد.

عرضی چرخه فرد یک مسئله الگوریتمی کامل NP است که با توجه به یک نمودار G = ( V ، E ) و یک عدد k ، س asks ال می کند که آیا مجموعه ای از رئوس k وجود دارد که حذف آنها از G باعث می شود نمودار حاصل به دو قسمت تبدیل شود. [27] این مسئله با پارامتر ثابت قابل حل است ، بدین معنی که الگوریتمی وجود دارد که زمان اجرای آن را می توان با یک توابع چند جمله ای به اندازه نمودار ضربدر یک تابع بزرگتر k محدود کرد . [28] نام عرضی چرخه فرداز این واقعیت حاصل می شود که یک نمودار دو بخشی است اگر و فقط در صورت عدم وجود چرخه های عجیب و غریب . از این رو ، برای حذف رئوس از یک نمودار برای به دست آوردن یک نمودار دوتایی ، باید "تمام چرخه فرد" را بزنید ، یا یک مجموعه عرضی به اصطلاح عجیب پیدا کنید . در تصویر ، هر چرخه فرد در نمودار حاوی رئوس آبی (پایین ترین) است ، بنابراین حذف این رئوس تمام چرخه های فرد را از بین می برد و یک نمودار دو بخشی را به جا می گذارد.

لبه bipartization مشکل مشکل الگوریتم حذف عنوان چند لبه که ممکن است برای یک دوبخشی نمودار می باشد و همچنین از مسائل مهم در algorithmics اصلاح نمودار است. این مشکل با پارامتر ثابت نیز قابل حل است و به موقع قابل حل است ${\ textstyle O \ چپ (2 ^ {k} m ^ {2} \ راست)}$ ، [29] که k تعداد لبه های حذف شده و m تعداد لبه های نمودار ورودی است.

تطبیق [ ویرایش ]

مقاله اصلی: تطبیق (تئوری نمودار)

تطبیق در یک گراف یک زیر مجموعه از لبه های آن، بدون که دو به اشتراک گذاشتن یک نقطه پایانی است. الگوریتم های زمان چند جمله ای برای بسیاری از مشکلات الگوریتمی در تطابق شناخته شده است ، از جمله حداکثر تطبیق (پیدا کردن تطبیق که از لبه های بیشتری استفاده می کند) ، حداکثر تطبیق وزن و ازدواج پایدار . [30] در بسیاری از موارد، مطابق با مشکلات ساده به حل در گراف دو بخشی از در نمودار غیر دوبخشی، [31] و بسیاری مطابق با الگوریتم های مانند الگوریتم هاپکرافت-کارپ برای حداکثر تطبیق کاردینالیتی [32] کار به درستی تنها در ورودی دوبخشی .

به عنوان یک مثال ساده ، فرض کنید یک مجموعه $پ$ مردم همه از بین مجموعه ای به دنبال کار هستند $ج$ شغل ، نه همه افراد مناسب برای همه مشاغل. این وضعیت می تواند به عنوان یک نمودار دو بخشی مدل شود $(P ، J ، E)$ جایی که یک لبه هر کاریابی را با هر کار مناسب متصل می کند. [33] یک تطبیق کامل روشی را برای جلب رضایت همزمان تمام افراد جویای کار و پر کردن همه مشاغل توصیف می کند. قضیه ازدواج هال توصیف نمودارهای دو بخشی را فراهم می کند که امکان تطابق کامل را فراهم می کند. تطبیق رزیدنت برنامه ملی روش تطبیق نمودار مربوط به حل این مشکل برای دانشجوی پزشکی آمریکا از جویندگان کار و اقامت بیمارستان شغل. [34]

تجزیه Dulmage-مندلسون تجزیه ساختاری گرافهای دوبخشی است که در پیدا کردن حداکثر تطابق مفید است. [35]

برنامه های اضافی [ ویرایش ]

نمودارهای دو طرفه به ویژه برای رمزگشایی رمزهای عبور دریافت شده از کانال ، به طور گسترده در تئوری کدگذاری مدرن استفاده می شود . نمودارهای فاکتور و نمودارهای Tanner نمونه هایی از این موارد هستند. نمودار Tanner یک نمودار دو قسمتی است که در آن رأس های یک طرف دو قسمت نشان دهنده ارقام کلمه رمز است و رئوس سمت دیگر نشان دهنده ترکیبی از ارقام است که انتظار می رود در یک رمز ورود بدون خطا به صفر برسد. [36] نمودار عامل یک شبکه اعتقادی نزدیک است که برای رمزگشایی احتمالی کدهای LDPC و توربو استفاده می شود . [37]

در علوم کامپیوتر ، شبکه Petri ابزاری برای مدل سازی ریاضی است که در تحلیل و شبیه سازی سیستم های همزمان به کار می رود. یک سیستم به عنوان یک نمودار دو طرفه جهت دار با دو مجموعه گره مدل سازی می شود: مجموعه ای از گره های "مکان" که دارای منابع هستند و مجموعه ای از گره های "رویداد" که منابع را تولید و یا مصرف می کنند. محدودیت های اضافی در گره ها و لبه ها وجود دارد که رفتار سیستم را محدود می کند. شبکه های پتری با استفاده از خصوصیات نمودارهای دو طرفه جهت هدایت اثبات ریاضی رفتار سیستم ها ، امکان اجرای آسان شبیه سازی های سیستم را نیز فراهم می کنند. [38]

در هندسه تصویری ، نمودارهای Levi نوعی نمودار دو بخشی است که برای مدلسازی موارد بین نقاط و خطوط در یک پیکربندی استفاده می شود . مربوط به ویژگی هندسی نقاط و خطوط که هر دو خط در حداکثر یک نقطه ملاقات و هر دو نقطه می شود با یک خط متصل است، لوی نمودارهای لزوما شامل هیچ دورهای به طول چهار، به طوری که آنها دور باید شش یا بیشتر باشد . [39]

همچنین به [ ویرایش ] مراجعه کنید

بعد دو طرفه ، حداقل تعداد نمودارهای کامل دو بخشی که نمودار واحد داده شده آنها است
پوشش دو طرفه دو طرفه ، روشی برای تبدیل هر نمودار به نمودار دو بخشی با دو برابر شدن رئوس آن
هایپرگراف دو طرفه ، تعمیم دو طرفه بودن به هایپراگراف ها .
Bipartite matroid ، دسته ای از matroids که شامل matroids های گرافیکی نمودارهای دو بخشی است
پیش بینی شبکه دو طرفه ، یک روش وزن دهی برای فشرده سازی اطلاعات در مورد شبکه های دو بخشی است
نمودار دو بخشی محدب ، نمودار دو بخشی که می توان رئوس آن را ترتیب داد تا محله های راس به هم پیوسته باشند
نمودار چند بخشی ، تعمیم نمودارهای دو بخشی به بیش از دو زیر مجموعه رئوس
نمودار برابری ، تعمیم نمودارهای دو بخشی که در آن هر دو مسیر القایی بین دو نقطه یکسان ، برابری یکسانی دارند
نمودار شبه دو بخشی ، نوعی از نمونه مسئله درخت اشتاینر است که در آن ترمینال ها یک مجموعه مستقل را تشکیل می دهند ، اجازه الگوریتم های تقریب را می دهد که برای نمودارهای دو بخشی را تعمیم می دهد
نمودار تقسیم شده ، گرافیکی که در آن رئوس را می توان به دو زیر مجموعه تقسیم کرد ، یکی از آنها مستقل و دیگری دسته است
مشکل Zarankiewicz در حداکثر تعداد لبه ها در یک نمودار دو بخشی با زیرنویس های ممنوع

منابع

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

+ نوشته شده در سه شنبه هجدهم خرداد ۱۴۰۰ ساعت 6:13 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی