گراف همبند

در نظریه گراف، یک گراف را همبند (به انگلیسی: Connected Graph)‏ گوییم اگر بتوان در امتداد یک دنباله از یالهای مجاور گراف، از هر راس دلخواه آن به هر راس دیگر رسید. تعریف همبندی برحسب گردشها به صورت زیر بیان می‌شود.
فرض کنید $G$ یک گراف باشد. دو راس $v$ و $w$ از گراف $G$ را همبند گویند، اگر و فقط اگر یک گردش از $v$ به $w$ وجود داشته باشد (یک گردش عبارت است از طی کردن یک مسیر روی یال‌های گراف به شکلی دلخواه). گراف $G$ همبند است، اگر و فقط اگر برای هر دو راس دلخواه $v$ و $w$ در گراف $G$ یک گردش از $v$ به $w$ وجود داشته باشد.

اگر از تعریف بالا نقیض گرفته شود چنین نتیجه می‌دهد که که گراف $G$ ناهمبند است؛ اگر و فقط اگر دو راس در $G$ وجود داشته باشد که به وسیله هیچ گردشی به هم متصل نشده باشند.

دورها و همبندی گرافها

فرض کنید $G$ یک گراف باشد. الف. اگر $G$ همبند باشد، آن گاه هر دو راس متمایز و دلخواه $G$ را می‌توان به وسیله یک مسیر ساده به هم وصل کرد. ب. اگر راسهای $v$ و $w$ بخشی از یک دور در گراف G باشند و یک یال از این دور حذف شود، آن گاه همچنان یک مسیر از $v$ به $w$ در G وجود دارد. ج. اگر $G$ همبند و شامل یک دور باشد، آن گاه یک یال دور را می‌توان بدون ناهمبند شدن $G$، حذف کرد.

مولفه همبندی

گرافی با سه مولفه همبندی.

گراف $H$ یک مولفه همبندی گراف $G$ است اگر و فقط اگر تمامی شروط زیر برقرار شود:
الف. $H$ یک زیرگراف $G$ باشد.
ب. $H$ همبند باشد.
ج. هیچ زیر گراف همبندی از $H$ ،$G$ را به عنوان زیر گراف در برنگیرد.

به عبارت دیگر مولفه همبند یک گراف، یک زیرگراف همبند است بطوری که اضافه کردن هر رأس یا یال آن را نا همبند بکند. هر گراف به یک نوع عبارت از اجتماع مولفه‌های همبند خود است.