همبندی، یال برشی و راس برشی¶

همبندی¶

گراف G همبند است اگر به ازای هر دو راس u و v یک مسیر از u به v وجود داشته باشد. در غیر این صورت ناهمبند است. هر گراف ناهمبند اجتماعی از چند گراف همبند است که به هر کدام از آن ها مولفه نیز میگویند. واضح است که یک گراف همبند دارای یک مولفه است.

اگر راس ها را مثل یک توپ و یال ها را مثل یک نخ در نظر بگیرید، مولفه های گراف را می توان با دست از هم جدا کرد اما راس های هر مولفه با نخ به هم متصل هستند.

راس برشی¶

در گراف G به راس v برشی گفته می شود اگر با حذف آن به تعداد مولفه های همبندی اضافه شود.

یال برشی¶

در گراف G به یال e برشی گفته می شود اگر با حذف آن به تعداد مولفه های همبندی اضافه شود.

گراف k همبند¶

به گراف k Gهمبند میگویند اگر بیش از k راس داشته باشد و با حذف x (x<k) راس نتوان آن را ناهمبند کرد. به این ترتیب \(\kappa (G)\) تعریف می شود ماکسیمم k که G را k همبند می کند، به عبارت دیگر کمترین تعداد راسی که نیاز است تا با حذف آن ها گراف ناهمبند و یا راس تنها شود.

بلوک¶

به یک زیرگراف ماکسیمال از G که راس برشی نداشته باشد گویند.