منو
 کاربر Online
778 کاربر online
تاریخچه ی: گراف همبند و ناهمبند

تفاوت با نگارش: 4

Lines: 1-38Lines: 1-36
 +در ((ریاضیات)) و ((علوم کامپیوتر))، __همبندی__ یک گراف،یکی از مفاهیم اساسی ((نظریه گراف)) است و ارتباط نزدیکی با مفهوم مسیر دارد.
-در ریاضیات و علوم کامپیوتر،همبندی یک گراف،یکی از مفاهیم اساسی نظریه گراف است و ارتباط نزدیکی با ممفهوم مسیر دارد.

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

تاریخ شماره نسخه کاربر توضیح اقدام
 دوشنبه 03 مرداد 1384 [04:24 ]   6   بابک خسروشاهی      جاری 
 یکشنبه 29 خرداد 1384 [07:04 ]   5   علی هادی      v  c  d  s 
 یکشنبه 29 خرداد 1384 [06:28 ]   4   علی هادی      v  c  d  s 
 یکشنبه 29 خرداد 1384 [05:24 ]   3   علی هادی      v  c  d  s 
 یکشنبه 29 خرداد 1384 [05:02 ]   2   علی هادی      v  c  d  s 
 شنبه 28 خرداد 1384 [11:39 ]   1   علی هادی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..