تاریخچه ی:
گراف همبند و ناهمبند
تفاوت با نگارش: 2
| - | س
یک راف را همبند گوییم، اگ بتوان در امتداد یک دنباله از یالهای مجاور گراف، از هر راس دلخواه آن به هر راس دیگر رسید. تعریف همبندی برحسب گردشها به صورت زیر بیان می شود.
تعریف
فرض کنید یک گراف باشد. دو راس و از گراف را همبند گویند، اگر و فقط اگر یک گردش از به وجود داشته باشد. گراف همبند است، اگر و فقط اگر برای هر دو راس دلخواه و در گراف یک گردش از به وجود داشته باشد.
اگر از تعریف بالا نقیض بگیرید. در می یابید که گراف همبد نیست؛ اگر و فقط اگر دو راس در وجود داشته باشد که به وسیله هیچ گردشی به هم متصل نشده باشند.
مثال: گرافهای همبند و ناهمبند
کدام یک از گرافهای زیر همبند است؟
حل:
گراف نشان داده شده در (الف) همبند است در حالی که گرافهای (ب) و () همبند نستند. برای این که علت ناهمبند بودن گراف (ج) را بیان کنیم، یادآوری می کنیم که در نمودار این گراف و ال یکدیگر را در نقطه ای قطع می کنند که راس گراف نیست. به این ترتیب گراف (ج) را به صورت زیر نیز می توان رسم کرد.
نظریه گراف
چند موضوع مقید و قابل توجه با دورها و همبندی گرافها در زیر آمده است. اثبات آنها را به عنوان تمرین به خواننده واگذار می کنیم.
فرض کنید یک گراف باشد.
الف. اگر همبند باشد، آن گاه هر دو راس متمایز و دلخواه را می توان ه وسیله یک مسیر ساده به هم وصل کرد.
ب. اگر راسها و بخشی از یک دور در گراف باشند و یک یال از این دور حذف شود، آن گاه همنان یک مسیر از به ر وجود دارد.
ج. اگر همبند و شامل یک دور باشد، آن گاه یک یال دور را می توان بدون ناهمبند شدن، حذف کرد.
با مراجعه به مثال آخر، گرافها (ب) و (ج) از سه بخش تشکیل شده است، که هر یک از بخشها به تنهایی یک گراف همبند است. مولفه همبند یک گراف، یک زیر گراف همبند با بزرگترین اندازه ممکن است.
تعریف:
گراف یک مولفه همبند گراف است اگر و فقط اگر
1. یک زیر گراف باشد
2. همبند باشد
3. هیچ زیر گراف همبندی از را به عنوان زیر گراف در برنگیرد و راسها یا یالهایی را شامل می شود که در نیستند.
در واقع هر گراف به یک نوع عبارت از اجتماع مولفه های همبند خود است.
مثال: مولفه های همبند
همه مولفه های همبند گراف نشان داده شده در زیر را پیدا کنید.
حل:
دارای سه مولفه است: با مجموعه راسهای و مجموعه یالهای است که در آن:
دورهای اویلری
کنون به بررسی مسایل عمومی تری برمی ردیم که مشابه مساله پلهای کونیگسبرگ است. تعریف زیر به افتخار اویلر، دورهای اویلری نامیده شده است.
|
+ | در ((ریایات)) و ((علوم کامیوتر))، __همبندی__ یک گراف،یکی از مفاهیم اساسی ((نریه گراف)) است و ارتباط نزدیکی با مفهوم مسیر دارد. |
| | + | یک گراف را __همبند__ گوییم. اگر بتوان در امتداد یک ((مفهوم دنباله|دنباله)) از یالهای مجاور گراف، از هر راس دلخواه آن به هر راس دیگر رسید. تعریف همبندی برحسب گردشها به صورت زیر بیان می شود. |
| | + | ^فرض کنید G یک گراف باشد. دو راس v و w از گراف G را همبند گویند، اگر و فقط اگر یک گردش از V به W وجود داشته باشد. گراف G همبند است، اگر و فقط اگر برای هر دو راس دلخواه V و W در گراف G یک گردش از V به W وجود داشته باشد.^ |
| | + | اگر از تعریف بالا نقیض بگیرید. در می یابید که گراف G همبند نیست؛ اگر و فقط اگر دو راس در G وجود داشته باشد که به وسیله هیچ گردشی به هم متصل نشده باشند. |
| | + | !مثال |
| | + | در شکل نمونه ای از گرافهای همبند و ناهمبند را می بینید. |
| | + | در گراف سمت راست چون گراف دو قسمت است در نتیجه بین همه راسها یک مسیر وجود ندارد.در نتیجه گراف ناهمبند است. |
| | + |
| | + | | |
| | + | | |
| | + | {picture=hamband.gif} |
| | + | |
| | + | |
| | + | | |
| | + | چند موضوع مقید و قابل توجه با ((دور ««گراف»»|دور))ها و همبندی گرافها در زیر بیان میکنیم. |
| | + | فرض کنید G یک گراف باشد. |
| | + | __الف.__ اگر G همبند باشد، آن گاه هر دو راس متمایز و دلخواه G را می توان به وسیله یک مسیر ساده به هم وصل کرد. |
| | + | __ب.__ اگر راسهای v و w بخشی از یک دور در گراف G باشند و یک یال از این دور حذف شود، آن گاه همچنان یک مسیر از v به w در G وجود دارد. |
| | + | __ج.__ اگر G همبند و شامل یک دور باشد، آن گاه یک یال دور را می توان بدون ناهمبند شدن G، حذف کرد. |
| | + | !مولفه همبند |
| | + | گراف H یک __مولفه همبند__ گراف G است اگر و فقط اگر |
| | + | 1.H یک زیر گراف G باشد |
| | + | 2.H همبند باشد |
| | + | 3.هیچ زیر گراف همبندی از H ، G را به عنوان زیر گراف در برنگیرد و راسها یا یالهایی را شامل می شود که در H نیستند. |
| | + | به عبارت دیگر مولفه همبند یک گراف، یک زیر گراف همبند با بزرگترین اندازه ممکن است.در واقع هر گراف به یک نوع عبارت از اجتماع مولفه های همبند خود است. |
| | + | !همچنین ببینید: |
| | + | ((نظریه گراف)) |
| | + | ((درخت ««گراف»»|درخت)) |
| | + | ((دور اویلری)) |
| | + | ((نظریه گراف کامل|گراف کامل)) |
| | + | |
