گراف

 

در ریاضیات و علوم کامپیوتر، همبندی یک گراف،یکی از مفاهیم اساسی نظریه گراف است و ارتباط نزدیکی با مفهوم مسیر دارد.

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

فرض کنید G یک گراف باشد. دو راس v و w از گراف G را همبند گویند، اگر و فقط اگر یک گردش از V به W وجود داشته باشد. گراف G همبند است، اگر و فقط اگر برای هر دو راس دلخواه V و W در گراف G یک گردش از V به W وجود داشته باشد.


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

مثال

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

img/daneshnameh_up/b/b4/hamband.gif



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

مولفه همبند

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

/ 3 نظر / 48 بازدید
فرشاد

سلام خيلی ممنون . وبلاگ زيبا و علی بود . محتوای خوب و مفيد . اما از شما می‌خواهم که قسمت‌های رياضيات دبيرستان رو گسترش بديد من تابستان شروع به خوندن دروس پيش دانشگاهی کردم اما چون معلم يا کلاسی نيست بعضی مشکلات برام پيش مياد می تونم از شما بخام که اگه مي تونی کمک کنی اگه ممکنه دور گراف رو بيش‌تر توضيح بدی با سپاس خداحافظ

کیا

سلام به خاطر اینکه وقت میگذارید و مطالب ریاضی می نویسید، خسته نباشید به عنوان یک علاقمند و مدرس ریاضی اگر در مورد مطلبی در ریاضیات کمک خواستید حاضر به همکاری میباشم.

مهدی

من از تعریف مولفه همبندی شما برای پایان نامه خودم استفاده کردم البته اسم سایت شما رو در پایان رساله ام می نویسم لطفا راضی باشید