گراف همبند

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 04 شهریور 1400
دسته‌بندی: گراف
امتیاز:
بازدید: 25 مرتبه

تعریف گراف همبند

گراف همبند گرافی است که بین هر دو راس آن لااقل یک مسیر وجود داشته باشد، در غیر این صورت گراف ناهمبند است.

گراف‌های زیر همگی همبند هستند زیرا بین هر دو راس، مسیری وجود دارد:

گراف همبند - پیمان گردلو

گراف‎های زیر همگی ناهمبند هستند زیرا بین بعضی از رئوس گراف‌های زیر مسیر وجود ندارد:

گراف همبند - پیمان گردلو

دریافت مثال

قضایا گراف همبند

قضیه

اگر گراف G از مرتبه p ناهمبند باشد آن‌گاه:

qmax=p1    2

اثبات

اگر رئوس گراف G را به دودسته A و B افراز کنیم که در بخش A به تعداد k راس و دربخش B به تعداد p-k راس داشته باشیم به‌طوری‌که بین رئوس بخش A و رئوس B هیچ یالی وجود نداشته باشد، آن‌گاه حداکثر تعداد یال‌ها k2+pk    2 می‌شود که این مقدار از p1   2 کم‌تر یا مساوی است.

قضیه

هر گراف ساده همبند از مرتبه p حداقل p-1 یال دارد. 

اثبات

با استقرای ریاضی روی p داریم:

فرض می‌کنیم p=2 یعنی گراف همبندی با دو راس داریم، لذا این گراف حداقل یک یال دارد. (بنابراین مرحله مبنایی استقرا درست است)

اکنون فرض می‌کنیم (فرض استقرا) که گراف همبندی از مرتبه k حداقل k-1 یال دارد، نشان می‌دهیم گراف همبندی از مرتبه k+1 حداقل k یال دارد. (حکم استقرا)

می‌دانیم که اگر به گراف همبندی که k راس و حداقل k-1 یال دارد، یک راس اضافه کنیم، تعداد راس‌ها k+1 خواهد شد، برای این‌که گراف حاصل همبند باشد باید راس اضافه شده، حداقل توسط یک یال به یکی از راس‌های گراف همبند موجود وصل شود تا گراف حاصل که حداقل k یال دارد همبند باشد، لذا حکم ثابت است.

تذکر

عکس قضیه فوق صحیح نیست:

یعنی هر گراف از مرتبه p با p-1 یال، همواره همبند نیست. 

به‌عنوان نمونه، در گراف زیر p=7q=6است، و لی همبند نیست:

گراف همبند - پیمان گردلو 

دریافت مثال

قضیه

اگر در گراف G از مرتبه p و مینیمم درجه δ داشته باشیم:  

δp12

آن‌گاه G همبند است.

اثبات

 فرض می‌کنیم گراف G ناهمبند است (برهان خلف):

پس مجموعه راسی را می‌توان به دو مجموعه A و B تقسیم کرد، بدون آن‌که بر کلیت اثبات خللی وارد شود، فرض می‌کنیم راسی مانند V1 در مجموعه A  وجود دارد که حداقل درجه آن p-12 است (راسی با مینیمم درجه)، در نتیجه اگر راسی مانند W1 در مجموعه B در نظر بگیریم، حداقل درجه این راس p-12-1 خواهد بود.   

بنابراین درجه راس W1 برابر p-32 می باشد که:  

p32<p12

لذا مینیمم درجه راس W1 برابر p-32 است که با فرض δ>p12 تناقض دارد، لذا G همبند است.   

دریافت مثال

قضیه

در یک گراف ساده و همبند از مرتبه p>2 حداقل درجه دو راس با هم برابر است.

اثبات

فرض می‌کنیم p=n>2 با توجه به تعریف گراف ساده، حداکثر تعداد یال‌های گذرنده از هر راس دل‌خواه V1 در گراف G به تعداد n-1 می‌باشد، بنابراین طبق تعریف داریم:

deg(V1)n1

از طرفی چون گراف G همبند است و در گراف همبند راسی با درجه صفر موجود نیست بنابراین حداقل تعداد یال‌های گذرنده از هر راس دل‌خواه مانند V1 یک می‌باشد، لذا:  

deg(V1)1

به این ترتیب برای هر راس دل‌خواه مانند V1 داریم:  

1deg(V1)n1deg(V1){1,2,...,n1}

طبق اصل لانه کبوتری:

حال اگر n راس را به‌عنوان n کبوتر و n-1 درجه ممکن هر راس را به‌عنوان لانه کبوتر در نظر بگیریم. 

چون n>n-1 پس حداقل دو راس مانند V2 و V3 در G وجود دارند که هم درجه‌اند، یعنی: 

deg(V2)=deg(V3)

دریافت مثال

قضیه

در گراف همبند G:  

u  ,  wV(G)    ;    d(u,w)=d(w,u)u  ,  v  ,  wV(G)    ;    d(u,w)d(u,v)+d(v,w)

اثبات

فرض می‌کنیم p1 مسیری بین u و v با فاصله du,v و p2 مسیری بین v و w با فاصله dv,w باشد، از به‌هم پیوستن p1 و p2 یک مسیر از u به w به‌دست می‌آید.    

طول این مسیر به‌وجود آمده برابر است با:

d(u,v)+d(v,w)

از طرفی چون du,w کوتاه‌ترین فاصله بین u و w است، پس خواهیم داشت:    

d(u,w)d(u,v)+d(v,w)

نکته

1- اگر گراف G همبند باشد، آن‌گاه هر دو راس متمایز و دل‌خواه G را می‌توان به‌وسیله یک مسیر ساده به‌هم وصل کرد.

2- اگر G همبند و شامل یک دور باشد، آن‌گاه یک یال از دور را می‌توان بدون ناهمبند شدن G حذف کرد. 

3- در یک گراف همبند، هیچ راسی با درجه صفر وجود ندارد.

دریافت مثال

نکته

4- با برداشتن q-p+2 یال از گراف همبند می‌توان آن‌را به گراف ناهمبند تبدیل کرد.  

5- اگر دو راس در یک گراف توسط هیچ مسیری به‌هم متصل نباشند، فاصله بین آنها برابر بی‌نهایت در نظر می‌گیریم و این مطلب در گراف‌های ناهمبند مطرح است.

6- برای گراف ناهمبند مرتبه p:

qmin=0qmax=p1    2=(p1)(p2)2

دریافت مثال

نکته

7- در یک گراف همبند برای یافتن حداقل و حداکثر راس‌ها و یال‌ها به‌صورت زیر عمل می‌کنیم: 

qmax=p(p1)2qmin=p1pmax=q+1pmin:qp(p1)2

pmin با توجه به نامساوی به‌دست می‌آید.

دریافت مثال

نکته

8- هر گراف ساده از مرتبه p با حداقل رابطه زیر، یال همواره همبند است: 

q=p1    2+1

نکته

9- هر گراف ناهمبند از قسمت‌های همبند تشکیل شده است که به یک‌دیگر متصل نیستند.

به هر قسمت یک مولفه می‌گوییم، مثلا گراف‌های ناهمبند زیر همگی دو مولفه دارند.

گراف همبند - پیمان گردلو

ماتریس همبند یک گراف ساده

گراف G با p راس را در نظر بگیرید، ماتریس همبند G ماتریس p×p به‌نام C=cijp×p است و به‌صورت زیر تعریف شده است: 

  • اگر i=j باشد، يا يک‌ مسير از Vi به Vj ‌وجود داشته باشد، آن‌گاه cij=1 
  • در غیر این‌صورت cij=0 

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

اگر u و v دو راس دل‌خواه از گراف همبند G باشند، فاصله بین u و v که با نماد du,v نشان داده می‌شود، طول کوتاه‌ترین مسیر از u به v در گراف G است، به‌عبارت دیگر:     

به طول کوتاه‌ترین مسیر بین دو راس در گراف همبند، فاصله دو راس گفته می‌شود.

بدیهی است که اگر در یک گراف، دو راس برهم منطبق باشند، فاصله بین آنها صفر خواهد بود. (مسیری به طول صفر) یعنی:

u,vV(G)  ;  d(u,v)=0u=v

دریافت مثال

قطر گراف همبند

قطر گراف G که به‌صورت diamG نوشته می‌شود، طولانی‌ترین فاصله موجود بین دو راس از راس‌های آن است.

دریافت مثال

نقطه برش گراف همبند 

راس v را برای گراف همبند G نقطه برش می‌گویند اگر G-v ناهمبند باشد.

درحالت کلی v برای هر گراف دل‌خواه G یک نقطه برش است، اگر G-v مولفه‌های همبند بیش‌تری نسبت به G داشته باشد.

یادآوری

G-v زیر گراف G است که از حذف راس v از مجموعه راس‌های VG و حذف تمام یال‌های EG به‌دست می‌آید.

به‌عنوان نمونه، گراف G در شکل زیر را در نظر می‌گیریم:

گراف همبند - پیمان گردلو

موارد زیر را داریم:

گراف همبند - پیمان گردلو

دریافت مثال

پل در گراف همبند

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

درحالت کلی e یک پل برای گراف دل‌خواه G است، اگر G-e نسبت به G مولفه‌های همبند بیشتری داشته باشد.

یادآوری

G-e زیرگراف G است که از حذف e از مجموعه یال‌های G به‌دست می‌آید: 

V(Ge)=V(G)E(Ge)=E(G)\{e}

تمرین

گراف‌های زیر را در نظر می‌گیریم: 

گراف همبند - پیمان گردلو

پل‌های گراف‌های فوق را به‌دست ‌آورید.

در شکل 1 سه پل A,X,A,Z,Y,C دارد، با حذف هر یک از یال‌های بیان شده G ناهمبند می‌شود.


در شکل 2 تنها B,Y گراف G را ناهمبند می‌کند و از این رو B,Y تنها پل G است.


 در شکل 3 گراف G دو مولفه همبند دارد، از حذف D,S,C,S مجموعه VG به سه (یا بیش‌تر از دو) مولفه همبند افراز می‌شود، درنتیجه C,S یا D,S پل هستند.    

دریافت مثال

مولفه همبند

مولفه همبند یک گراف، یک زیرگراف همبند با بزرگ‌ترین اندازه (بیش‌ترین یال‌ها) ممکن است.

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

  • H یک زیرگراف G باشد.
  • H همبند باشد.
  • هیچ زیرگراف همبندی از G به H را به‌عنوان زیرگراف در برنگیرد و راس‌ها یا یال‌هایی را شامل می‌شود که در H نیستند.

تمرین

گراف‌ زیر را در نظر می‌گیریم: 

گراف همبند - پیمان گردلو

مولفه‌های همبند گراف فوق را به‌دست ‌آورید. 

از راس دل‌خواه، مثلا A شروع و تمام راس‌های همبند با A را پیدا می‌کنیم که به این ترتیب مولفه A,B,Y,Z به‌دست می‌آید.


پس از آن، راسی را انتخاب می‌کنیم که در این مولفه نباشد و این فرایند راتکرار کنید این عمل را به‌همین طریق ادامه دهید تا تمام مولفه‌ها مشخص شود.


برای این گراف سه مولفه همبند زیر به‌دست می‌آید:

A,B,Y,Z  C,X,QP,R   

دریافت مثال

مثال‌ها و جواب‌ها

گراف همبند

7,000تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید