دوشنبه ۳۱ ارديبهشت ۱۴۰۳   |  كاربر مهمان  |    
 رباتیک - شبیه‌سازی
 نظريه‌ي گراف‌ها – قسمت دوم (زنگ تفريح شماره‌ي 36)
نظريه‌ي گراف‌ها – قسمت دوم (زنگ تفريح شماره‌ي 36)زنگ تفريح كامپيوتر
زيرگراف‌ها

نظريه‌ي گراف‌ها

قسمت دوم









اشاره
در قسمت اول، درباره‌ي تاريخچه‌ي «نظريه‌ي گراف»، علايم و تعاريف ابتدايي صحبت كرده و در پايان «گراف‌هاي يك‌‌ريخت» ‌را تعريف نموديم.

در اين بخش، موارد ذيل را از مبحث گراف‌ها بيان خواهيم كرد:

- موارد كاربردي از گراف‌هاي ساده و گراف‌هاي «معادل» و گراف‌هاي «يك‌ريخت» (Isomorphism)
- ماتريس‌هاي «وقوع» (Incidence) و «مجاورت» (Adjacency)
- موارد كاربرد ماتريس‌هاي «وقوع» (Incidence) و «مجاورت» (Adjacency)

- زيرگراف‌ها (Subgraphs)

- مواردي كاربردي از زيرگراف‌ها (Subgraphs)

- درجه‌هاي رؤوس (Degree)

- قضيه‌اي درباره‌ي درجه‌هاي رؤوس (Degree)

- موارد كاربردي از «درجه‌هاي رؤوس» (Degree)

- مسيرها و همبندي (Paths and Connection)

- گشت (Walk)

- معكوس گشت (Reverse Walk)

- بخشي از گشت (Section)

- گذر (Trail) و «مسير» (Path)

- همبند (Connected)

- كاربردهايي از مفاهيم مسيرها و همبندي (Paths and Connection).




چكيده
اهداف آموزشي
 اهداف آموزشي در حوزه‌ي شناختي - دانش
    - «دانش امور جزوي» > «دانش اصطلاح‌ها»
    - «دانش امور جزوي» > «دانش واقعيت‌هاي مشخص»
    - «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش امور قراردادي»
    - «دانش راه‌ها و وسايل برخورد با امور جزوي» > «دانش طبقه‌بندي‌ها و طبقه‌ها»
    - «دانش امور كلي و مسائل انتزاعي» > «دانش اصل‌ها و تعميم‌ها»
 اهداف آموزشي در حوزه‌ي شناختي - توانايي‌ها و مهارت‌هاي ذهني
    - «فهميدن» > «درون‌يابي»
    - «فهميدن» > «ارزشيابي» < «داوري براساس شواهد دروني»
 نتايج مورد نظر
    - آشنايي دانش‌اموزان تعاريف و مفاهيم «نظريه‌ي اعداد»
    - آشنايي با قضاياي اصلي و برخي الگوريتم‌ها، توانايي بيان مثال‌هاي مورد نياز و پرسش از مسائلي كه طبيعتاً بعد از آن قابل‌طرح است
    - يافتن مهارت در اثبات قضايا به‌صورت كتبي با استفاده از روش‌هاي اثبات در «نظريه‌ي اعداد» نظير: يك‌به‌يك، «حداقل شمارشگر» (Minimal Counterexample) و «استقراي قوي» (Loaded Induction)
    - آشنايي با چشم‌انداز كلي و اهداف «نظريه‌ي گراف» نظير: طبقه‌بندي، برون‌يابي (Extermality)، بهينه‌سازي و هوشياري و الگوريتم‌ها و دوگانگي (Duality)
    - توانايي به‌كار بردن دانش «نظريه‌ي اعداد» در حل مسائل در حوزه‌هاي ديگر و احتمالاً با اجراي پروژه‌اي كلاسي
 محتواي آموزشي (سرفصل‌هاي المپياد)
    - گراف‌ها < كليات




 

موارد كاربردي از گراف‌هاي ساده و گراف‌هاي «معادل» و گراف‌هاي «يك‌ريخت» (Isomorphism)

موارد ذيل را مي‌توان نشان داد:

اگر گراف  «ساده» (Simple) باشد خواهيم داشت:





(رابطه‌ي 1)

 

 اگر گراف‌هاي  و «يك‌ريخت» (Isomorphism) باشند يعني داشته باشيم:





(رابطه‌ي 2)

در اين صورت خواهيم داشت:





(رابطه‌ي 3)





(رابطه‌ي 4)

ولي عكس اين رابطه برقرار نيست به‌عبارت ديگر نمي‌توان از رابطه‌‌‌هاي 3 و 4 رابطه‌ي 2 را به‌دست آورد.

 دو گراف  و «ساده‌ي» و «يك‌ريخت» (Isomorphism) هستند اگر و فقط اگر يك تابع «يك به يك» نظير:  وجود داشته باشد به‌گونه‌اي كه  اگر و فقط اگر داشته باشيم:

 

 

 فرض كنيد  گرافي «ساده» باشد؛ در اين صورت رابطه‌ي ذيل برقرار است:





(رابطه‌ي 5)

اگر و فقط اگر  «كامل» باشد.

 

 تعداد يال‌هاي گراف «دوبخشي كامل» (Complete Bipartite Graph)  از رابطه‌ي ذيل به‌دست مي‌آيد:





(رابطه‌ي 6)

 اگر  گرافي «ساده» (Simple) و «دوبخشي» (Bipartite) باشد در اين صورت خواهيم داشت:





(رابطه‌ي 7)

 

 تعاريف ذيل را به‌دقت توجه كنيد:

 يك گراف « بخشي» (k-Partite) گرافي است كه مجموعه رؤوس آن مي‌تواند به زيرمجموعه به‌گونه‌اي تقسيم شود كه دو انتهاي هيچ يالي در يك زيرمجموعه وجود نداشته باشد.
 يك گراف « بخشي كامل» (Complete k-Partite) گرافي است كه «ساده» بوده و در آن هر رأسي كه رأس ديگر متصل شده است در زيرمجموعه‌ي يكساني نباشد.
 يك گراف « بخشي كامل» (Complete m-Partite) با  رأس كه در آن هر بخش داراي يا  رأس باشد با نشان داده مي‌شود.

مي‌توان نشان داد رابطه‌ي ذيل درباره‌ي يك گراف « بخشي كامل» (Complete k-Partite) همواره برقرار است:





(رابطه‌ي 8)

كه در آن داريم:





(رابطه‌ي 9)

هم‌چنين مي‌توان نشان داد:

اگر  يك گراف « بخشي كامل» (Complete m-Partite) با رأس باشد در اين صورت داريم:





(رابطه‌ي 10)


ياداوري – تساوي در رابطه‌ي 10 يعني:  زماني برقرار است كه گراف‌هاي  و  «يك‌ريخت» باشند به‌عبارت ديگر داشته باشيم:





(رابطه‌ي 11)


 

 تعريف ذيل را درنظر بگيريد:

يك گراف « مكعب» (k-Cube) گرافي است كه رؤوس آن تايي از «صفر» و «يك» هستند كه دو رأس آن به يكديگر متصل هستند اگر و فقط اگر دو رأس‌شان دقيقاً در يك مؤلفه با يكديگر تفاوت داشته باشند.

به‌عبارت ديگر اگر عددي طبيعي باشد منظور از « مكعب» گرافي است كه رأس‌هاي آن همه‌ي دنباله‌هاي رقمي از «صفر» و «يك» هستند و دو رأس در اين گراف مجاور بوده هرگاه دنباله‌هاي متناظرشان دقيقاً در يك مؤلفه اختلاف داشته باشند (شكل 1).


شكل 1 – گراف « مكعب» به‌ترتيب از سمت چپ:
«يك مكعب»، +«دو مكعب» و «سه مكعب».



ياداوري - توجه داشته باشيد كه شكل 26 در زنگ تفريح شماره‌ي 35 تنها يك گراف «3 مكعب» است.

مي‌توان نشان داد كه يك گراف « مكعب» (k-Cube) داراي ويژگي‌‌هايي نظير ذيل است:

- تعداد رؤوس =

- تعداد يال‌ها =

- گرافي «دوبخشي» (Bipartite) است.


 

 «مكمل» گراف (Complement)
«مكمل» (Complement) يك گراف «ساده» – كه معمولاً با نشان مي‌دهند - يك گراف «ساده» با مجموعه رؤوس  و دو رأس «مجاور» در  است اگر و فقط اگر رؤوس در گراف  «مجاور» نباشند.



 

 گراف «خود مكمل» (Self-Complement)
يك گراف «ساده» نظير:  «خود مكمل» (Self-Complement) است اگر داشته باشيم:





(رابطه‌ي 12)

مي‌توان نشان داد كه اگر گرافي «خود مكمل» (Self-Complement) باشد در اين صورت خواهيم داشت:





(رابطه‌ي 13)


 

 «هم‌ريختي» (Automorphism)
بنابر تعريف «هم‌ريختي» (Automorphism) يك گراف عبارت است از: يك‌ريختي آن گراف بر روي خودش (شكل 2).

به‌عنوان مثال:

قرينه‌هاي آينه‌اي يك گراف نسبت به محورهاي عمودي و افقي مي‌تواند به‌عنوان «هم‌ريخت‌هاي» يك گراف محسوب شوند.


شكل 2 – نمونه‌اي از گراف‌هاي
«هم‌ريختي» (Automorphism).

شكل 3 – گراف «ستاره» (Star)
و گراف‌هاي «هم‌ريخت» آن.



مثالي ديگر:

يك گراف «ستاره» (Star) داراي شش گراف «هم‌ريخت» است (شكل 3).

موارد ذيل را مي‌توان درباره‌ي «هم‌ريختي» (Automorphism) اثبات كرد:

 «هم‌ريختي» (Automorphism)
«هم‌ريختي» (Automorphism) يك گراف  «ساده‌ي»  مي‌تواند به‌عنوان جايگشتي بر روي  درنظر گرفته شود كه «مجاورت» را حفظ مي‌كند و اين‌كه چنين جايگشت‌هايي، يك گروه  (با عنوان: گروه «هم‌ريخت» گراف ) تحت عمليات غيرمعمول تركيب تشكيل مي‌دهند.

 براي هر گراف «ساده‌ي»  رابطه‌ي ذيل برقرار است:





(رابطه‌ي 14)

شكل 4 – نمونه‌هايي از گراف‌هاي
«رأس متقارن» (Vertex Transitive).

شكل 5 – سمت چپ و راست به‌ترتيب
گراف «يگانه»(Singleton)  و گراف «دو مسيره» (2-Path Graph).

شكل 6 – سمت چپ و راست به‌ترتيب
گراف «پيترسون» (Peterson) و گراف «كوگزتر» (Coxeter).

شكل 7 – سمت چپ و راست به‌ترتيب گراف «مكعب متقارن»
(Cubic Transitive Graph 66) و گراف «كوگزتر مثلث جايگزين»
(Triangle Replaced Coexeter Graph).




 

گراف «رأس متقارن» (Vertex Transitive)
يك گراف «ساده»، «رأس متقارن» (Vertex Transitive) است اگر براي هر دو رأس  و ، يك «عنصر» (Element) نظير: در ‌وجود دارد به‌گونه‌اي كه داشته باشيم:





(رابطه‌ي 15)

به‌عبارت ديگر، يك گراف «رأس متقارن» (Vertex Transitive) است اگر گروه «هم‌ريختي» (Automorphism) آن براي رؤؤسش، متقارن عمل كند.

به بياني ديگر، شرط لازم و كافي براي آن‌كه يك گراف «رأس متقارن» (Vertex Transitive) باشد آن است كه با «مكملش» (Complement) هم‌ارز باشد.


شكل 8 – نمونه‌هايي از گراف‌هاي «يال متقارن» (Edge Transitive).

شكل 9 – نمونه‌هايي از گراف‌هاي «يال متقارن» (Edge Transitive).



 

گراف «يال متقارن» (Edge Transitive)
گراف  «يال متقارن» (Edge Transitive) است اگر براي هر دو يال  و ، يك «عنصر» (Element) نظير: در وجود داشته باشد به‌گونه‌اي كه داشته باشيم:





(رابطه‌ي 16)

به‌عبارت ديگر، يك گراف «يال متقارن» (Edge Transitive) است اگر گروه «هم‌ريختي» (Automorphism) آن براي يال‌هايش، متقارن عمل كند.

يك «يال هم‌ريختي» (Edge Automorphism) يك گراف عبارت است از جايگشت يال‌هايي كه رابطه‌ي «يال مجاورتي» (Edge- Adjacency) را حفظ كند.





 گراف «نيمه‌متقارن» (Semisymmetric) . «متقارن» (Symmetric)
يك گراف «منتظم» (Regular) كه «يال متقارن» (Edge Transitive) باشد ولي «رأس متقارن» (Vertex Transitive) نباشد گراف «نيمه‌متقارن» (Semisymmetric) ناميده مي‌شود.

در عوض گرافي كه هم «يال متقارن» (Edge Transitive) و هم «رأس متقارن» (Vertex Transitive) باشد «گراف متقارن» (Symmetric) ناميده مي‌شود.


شكل 10 – گراف «صفر معمولي»
(صفر - Regular).

شكل 11 – گراف «يك معمولي»
(1 - Regular).

شكل 12 – گراف «دو معمولي»
(2 - Regular).

شكل 13 – گراف «سه معمولي»
(3 - Regular).

 


 

 گراف «منتظم» (Regular)
ياداوري – يك گراف «منتظم» (Regular) گرافي است كه هر رأس آن داراي تعداد همسايه‌هاي يكساني باشد.

به‌عنوان مثال:
هر رأس گراف «منتظم» داراي «درجه‌ي» يكساني است.

يك گراف «منتظم» كه هر رأس آن داراي درجه‌ي  است گراف « منتظم» (k-Regular) ناميده مي‌شود.

بنابراين گراف‌هاي «منتظم» با حداكثر درجه‌ي 2 خيلي راحت طبقه‌بندي مي‌شوند:

گراف «صفر منتظم» (صفر - Regular)
يك گراف «صفر منتظم» داراي رؤوس غيرمتصل (غيرهمبند) است.

 گراف «يك منتظم» (1 - Regular)
يك گراف «يك منتظم» داراي يال‌هاي غيرمتصل (غيرهمبند) است.

 گراف «دو منتظم» (2 - Regular)
يك گراف «دو منتظم» داراي حلقه‌هاي غيرمتصل (غيرهمبند) است.

 يك گراف «سه منتظم» (3 - Regular) به گراف «مكعبي» (Cubic) شهرت دارد.

 يك گراف «اكيداً منتظم» (Strongly Regular) گرافي منتظمي است كه در آن هر زوج رأس مجاور داراي تعداد همسايه‌هاي يكسان بوده و هر زوج رأس‌هاي غيرمجاور داراي تعداد  همسايه‌ي يكسان هستند.

به‌عنوان مثال:
از ساده‌ترين گراف‌هايي كه «منتظم» (Regular) بوده ولي «اكيداً منتظم» (Strongly Regular) نباشند مي‌توان به گراف‌هاي ذيل اشاره كرد:

- گراف «حلقه‌اي» (Cycle)
- گراف «دوري» (Circulant).

براين اساس، يك گراف «كامل» (Complete) ، گرافي «اكيداً منتظم» (Strongly Regular) براي هر  است.



ماتريس‌هاي «وقوع» (Incidence) و «مجاورت» (Adjacency)

به هر گراف  يك ماتريس  نسبت داده مي‌شود كه ماتريس «وقوع»  ناميده مي‌شود. رؤوس ماتريس  را با  و يال‌هاي آن را با  نشان مي‌دهيم:

- ماتريس «وقوع» (Incidence)
در اين صورت ماتريس «وقوع»  عبارت است از:  كه در آن تعداد دفعه‌هاي (0، 1 يا 2) است كه در آن  و  واقع مي‌شوند (يعني رأس  بر يال  قرار داشته باشد). ماتريس «وقوع» يك گراف، روشي متفاوت براي مشخص كردن گراف است.

- ماتريس «مجاورت» (Adjacency)
نوع ديگر ماتريس‌ها – كه همراه با ماتريس «وقوع» مطرح مي‌شود – عبارت است از: ماتريس «مجاورت». ماتريس «مجاورت» از يك گراف راهي متفاوت براي مشخص كردن گراف است؛ اين ماتريس  با عبارت  نشان داده مي‌شود كه در آن   تعداد يال‌هاي مرتبط‌كننده‌ي رؤوس و  است (شكل 1، 2 و 3).


شكل 14 – گراف .

شكل 15 - ماتريس‌ «وقوع» گراف .

شكل 16 - ماتريس‌ «مجاورت» گراف .


ماتريس «مجاورت» (Adjacency) يك گراف معمولاً كوچك‌تر از ماتريس‌هاي «وقوع» (Incidence) آن گراف بوده و گراف‌ها در اين شكل هستند كه عموماً در كامپيوترها ذخيره مي‌شوند.





موارد كاربرد ماتريس‌هاي «وقوع» (Incidence) و «مجاورت» (Adjacency)

موارد ذيل را مي‌توان نشان داد:

 اگر  و به‌ترتيب ماتريس‌هاي «وقوع» و «مجاورت» باشند:

 جمع ارقام هر ستون از ماتريس «وقوع»  برابر عدد 2 است در حالي كه جمع هر رديف از ماتريس مذكور برابر با «درجه‌ي» آن رأس (تعداد يال‌هاي آن رأس) (Degree) است.
 جمع ارقام هر ستون از ماتريس «مجاورت»  برابر عدد 2 است.

 

 اگر  و به‌ترتيب ماتريس‌هاي «وقوع» و «مجاورت» باشند:

فرض كنيد گراف  «دوبخشي» (Bipartite) باشد. مي‌توان نشان داد كه رؤوس گراف  مي‌تواند به‌گونه‌اي باشد كه ماتريس «مجاورت»  داراي شكل ذيل باشد:





(رابطه‌ي 17)

كه در آن  «برگردان» (Transpose)  است.

  اگر  گراف «ساده‌اي» باشد و مقادير ويژه‌ي (Aigenvalue) مربوط به  مجزا باشد گروه «هم‌ريخت» «آبلي» (Abelian) خواهد بود.



زيرگراف‌ها (Subgraphs)

 زيرگراف (Subgraph)
يك گراف  زيرگراف  ناميده و به‌صورت: نوشته مي‌شود اگر داشته باشيم:

-
-

- حد  تا مجموعه يال‌هاي گراف  يا  باشد.




 زيرگراف ويژه (Proper Subgraph)
زماني كه داشته باشيم:

-
- اما  باشد، مي‌نويسيم:



و چنين مي‌خوانيم:

« يك زيرگراف ويژه از  است».

اگر  يك زيرگراف از  باشد  يك «سوپرگراف» از  يا «مافوق گراف»  است.




 «زيرگراف» يا «سوپرگراف» پوششي (Spanning Subgraph) (Spanning Supergraph)
زيرگراف يا سوپرگراف پوششي (Spanning Subgraph) (Spanning Supergraph) از ، يك زيرگراف (يا سوپرگراف يا مافوق گراف) از است كه در آن داريم:





(رابطه‌ي 18)




 گراف ساده‌ي ضمني (Underlying Simple Graph)
با حذف همه‌ي حلقه‌هاي گراف  براي هر زوج رؤوس مجاور - به‌گونه‌اي كه يك اتصال بين رؤوس موجود باشد – يك گراف «ساده‌ي ضمني» (Underlying Simple Graph) به‌دست خواهد آمد (شكل 4).


شكل 17 – يك گراف و گراف
«ساده‌ي ضمني» (Underlying Simple Graph).

شكل 18 – گراف .

شكل 19 – يك زيرگراف پوششي از .

شكل 20 - .

شكل 21 - .

شكل 22 – يك زيرگراف القايي
(Induced Subgraph).

شكل 23 – زيرگراف القايي لبه‌دار
(The Edge-Induced Subgraph)
.



 زيرگراف القايي (Induced Subgraph)
فرض كنيد  يك زيرمجموعه‌ي غيرتهي از  باشد. زيرگراف  كه مجموعه‌ي رؤوسش  بوده و مجموعه يال‌هايش مجموعه‌ي يال‌هاي گراف  باشد به‌گونه‌اي كه يال‌هايش داراي دو سر در مجموعه رؤوس  باشد اصطلاحاً زيرگرافي از  ناميده مي‌شود كه با  القا شده است و اين‌گونه نشان داده مي‌شود:




زيرگراف القايي  به‌صورت ذيل نشان داده مي‌شود:




زيرگراف القايي عبارت است از زيرگرافي كه با حذف رؤوس در  همراه با يال‌هاي وقوع آن از گراف  به‌دست مي‌آيد.

اگر  براي  مي‌نويسيم:



اكنون فرض كنيد يك زيرمجموعه‌ي ناتهي از  باشد. زيرگراف كه مجموعه‌ي رؤوس آن ‌مجموعه‌ي انتهاي يال‌ها در باشد اصطلاحاً زيرگراف  ناميده مي‌شود كه با  القا شده و به‌صورت ذيل نوشته مي‌شود:



زيرگراف پوششي از گراف  با مجموعه يال‌هاي  به‌صورت ساده‌ي ذيل نوشته مي‌شود:




زيرگراف پوششي از گراف  زيرگرافي است كه با حذف يال‌ها در  از گراف  به‌دست مي‌آيد.

به‌طور مشابه، گراف به‌دست آمده از با اضافه كردن يك مجموعه يال  به‌صورت ذيل نوشته مي‌شود:




اگر داشته باشيم: ، به‌جاي به‌ترتيب  و  مي‌نويسيم:  و .

در شكل‌هاي 5، 6، 7، 8، 9 و 10 چند نوع زيرگراف نشان داده شده است.





 زيرگراف «منفصل» (Disjoint Subgraph)
فرض كنيد و  زيرگراف‌هاي  باشند. مي‌گوييم:

- گراف‌هاي  و  «منفصل» (Disjoint) هستند زماني كه هيچ رأس مشتركي نداشته باشند.

- گراف‌هاي و  از «يال منفصل» (Edge Disjoint) هستند اگر داراي هيچ يال مشتركي نباشند.





 اجتماع زيرگراف‌ها (Union)
اجتماع زيرگراف‌هاي  و  - كه به‌صورت ذيل نوشته مي‌شود:  - زيرگرافي است با:

- مجموعه رؤوس:
- و مجموعه يال‌هاي: .

اگر  و  «منفصل» باشند گاهي اوقات اجتماع آن‌ها را به‌صورت:  نشان مي‌دهند.





 فصل مشترك زيرگراف‌ها (Intersection)
فصل مشترك زيرگراف‌هاي  و  - كه به‌صورت ذيل نوشته مي‌شود:  - زيرگرافي است با:


- مجموعه رؤوس:

- و مجموعه يال‌هاي: .

اما در اين حالت زيرگراف‌هاي  و  بايد داراي حداقل يك رأس مشترك باشند.





مواردي كاربردي از زيرگراف‌ها (Subgraphs)

مي‌توان موارد ذيل را در مورد زيرگراف‌ها اثبات كرد:

- هر گراف «ساده» (Simple) با رأس نسبت به زيرگراف «يك‌ريخت» است.
- هر زيرگراف «القايي» (Induced) از يك گراف «كامل» (Complete)، گرافي «كامل» است.
- هر زيرگرافي از يك گراف «دوبخشي» (Bipartite) خود گرافي «دوبخشي» است.

- فرض كنيم گراف  گرافي «ساده» بوده و  عددي صحيح باشد به‌طوري كه داشته باشيم:





(رابطه‌ي 19)

در اين صورت اگر  باشد و همه‌ي زيرگراف‌هاي القايي گراف بر روي رأس تعدادي مساوي يال داشته باشند در اين صورت يكي از گزاره‌هاي ذيل صحيح است:





(رابطه‌ي ‌20)





(رابطه‌ي 21)

 


درجه‌هاي رؤوس (Degree)

درجه‌ي  (يا ) يك رأس در گراف برابر تعداد يال‌هاي «وقوع»  با  است كه در آن هر «حلقه» شمارشگر دو رأس است. علايم  و  به‌ترتيب بيانگر «مينيمم درجه‌» و «ماكسيمم درجه‌ي» رؤوس گراف  هستند.

تعداد رؤوس گراف  را با نشان داده و «مرتبه‌ي گراف»  مي‌ناميم.

به‌عنوان مثال:

در شكل 10 «مرتبه‌ي» گراف عدد 5 است.

تعداد يال‌هاي گراف  را با نشان داده و «اندازه‌ي گراف» مي‌ناميم.

به‌عنوان مثال:

در شكل 10 «اندازه‌ي» گراف عدد 4 است.





قضيه‌اي درباره‌ي درجه‌هاي رؤوس (Degree)

مي‌توان قضيه‌ي ذيل را براي هر گراف نظير: ثابت كرد:

جمع درجه‌هاي همه‌ي رؤوس يك گراف با دو برابر تعداد يال‌ها آن برابر است.





(رابطه‌ي 22)


از اين قضيه مي‌توان عبارت ذيل را نتيجه گرفت:

در هر گراف، تعداد رؤوس با درجه‌ي «فرد» عددي «زوج» است.

بر اين اساس مي‌توان تعريف‌هاي ذيل را ارائه داد:

 گراف « منتظم» (k-Regular)
يك گراف « منتظم» (k-Regular) است اگر براي هر  داشته باشيم:





(رابطه‌ي 23)



 گراف «منتظم» (Regular)
يك گراف «منتظم» (Regular) براي بعضي از مقدار  گرافي « منتظم» (k-Regular) است.

به‌عنوان مثال:

گراف‌هاي «كامل» (Complete) و «دوبخشي كامل» (Complete Bipartite) ‌نمونه‌اي از گراف‌هاي «منتظم» (Regular) بوده و در نتيجه « مكعب» (k Cubes) هستند.






موارد كاربردي از «درجه‌هاي رؤوس» (Degree)

مي‌توان موارد ذيل را نشان داد:

 رابطه‌ي ذيل بيانگر رابطه‌ي «تعداد يال‌ها» ، «مينيمم درجه‌» و «ماكسيمم درجه‌ي»  و  رؤوس گراف  است:





(رابطه‌ي 24)


 اگر  گرافي «ساده» باشد درايه‌هاي واقع بر قطر ماتريس‌هاي  و  درجه‌هاي رؤوس گراف ‌خواهند بود كه در آن  و به‌ترتيب ماتريس‌هاي «وقوع» و «مجاورت» گراف  محسوب مي‌شوند.


 اگر با فرض ، گراف «دو بخشي» « منتظم» (k-Regular) داراي «دو بخش» (Bipartition) باشد رابطه‌ي ذيل برقرار خواهد بود:





(رابطه‌ي 25)



 اگر گراف  داراي رؤوس باشد دنباله‌ي «دنباله‌ي درجه‌ي» (Degree Sequence) گراف ‌ناميده مي‌شود.

شرط لازم و كافي براي آن‌كه دنباله‌ي از اعداد ناصحيح يك «دنباله درجه» (Degree Sequence) از گراف ‌باشد آن است كه جمع درجه‌هاي رؤوس آن يعني  عددي «زوج» باشد.


 دنباله‌ي را «گرافيك» (Graphic) مي‌ناميم اگر يك گراف «ساده» (Simple) با «دنباله درجه‌ي»  (Degree Sequence) وجود داشته باشد.


شكل 24 – دنباله‌ي گرافيك.

شكل 25 – دنباله‌ي غيرگرافيك.




 اگر دنباله‌ي «گرافيك» (Graphic) باشد در اين صورت داريم:

- رابطه‌ي بين درجه‌هاي رؤوس به‌صورت ذيل است:





(رابطه‌ي 26)

-  عددي «زوج» است.

- براي داريم:







(رابطه‌ي 27)



شكل 26 - «پائول اردوش»
(Paul Erdos).

شكل 27 - «تيبور گالايي»
(Tibor Gallai).

«اردوش» (Erdos) و «تيبور گالايي» (Tibor Gallai) نشان دادند كه رابطه‌ي 27 شرط كافي براي آن است كه دنباله‌ي  «گرافيك» (Graphic) باشد.



شكل 28 - «اس. لوييس حكيمي»
(S. Louise Hakimi)

 الگوريتم «هاول، حكيمي» (V. Havel, S. Louise Hakimi)
فرض كنيد دنباله‌ي دنباله‌اي «غيرافزايشي» (Nonincreasing) از اعداد «غيرصحيح» باشد. دنباله‌ي ذيل را در نظر بگيريد:





مي‌توان گزاره‌ي ذيل را ثابت كرد:

دنباله‌ي «گرافيك» است اگر و فقط اگر  «گرافيك» باشد.




 يك گراف «بدون حلقه‌ي»  شامل يك «زيرگراف» يا «سوپرگراف» «پوششي دوبخشي» (Bipartite Spanning Subgraph)
يك گراف «بدون حلقه‌ي» شامل يك «زيرگراف» يا «سوپرگراف» «پوششي دوبخشي» (Bipartite Spanning Subgraph) نظير: ‌است به‌گونه‌اي كه براي هر ‌داشته باشيم:





(رابطه‌ي 28)


 فرض كنيد ‌مجموعه‌اي از نقاط در صفحه باشد به‌گونه‌اي كه فاصله‌ي بين هر دو نقطه حداقل «يك» باشد. در اين صورت حداكثر ‌زوج نقطه در فاصله‌ي دقيقاً «يك» وجود خواهد داشت.


 «يال گراف» (Edge Graph) يك گراف
شرط لازم و كافي براي آن‌كه «يال گراف» (Edge Graph) يك گراف ، گرافي با مجموعه رؤوس  باشد كه در آن دو رأس به هم متصل باشند آن است كه آن‌ها يال‌هاي «وقوع» در گراف ‌باشند.

با توجه به تعريف «يال گراف» (Edge Graph) يك گراف مي‌توان موارد ذيل را نشان داد:

- «گراف يال» (Edge Graph) گراف ‌به‌ترتيب داراي رأس  و  يال است.


- «يال گراف» » (Edge Graph) گراف با «مكمل» گراف‌هاي اشكال 29 و 30 «يك‌ريخت» است:



شكل 29.

شكل 30.



 


مسيرها و همبندي (Paths and Connection)


گشت (Walk)

يك «گشت» (Walk) در گراف يك دنباله‌ي محدود و غيرتهي است كه عبارت‌هايش متناوباً يال و رأس باشد به‌گونه‌اي كه داشته باشيم:

-
-  و  انتهاي .

بدين‌ترتيب گفته مي‌شود:

- «گشت»  از  تا
- يا «گشت» .

هم‌چنين مي‌توان اصطلاح‌هاي ذيل را در ارتباط با «گشت» به‌كار برد:

- رؤوس و به‌طور نسبي با عنوان «ابتدا» و «انتهاي»
-  با عنوان «رؤوس دروني» (Internal Vertices)
- عدد صحيح  با عنوان «طول گشت».




معكوس گشت (Reverse Walk)

اگر ‌و  «گشت‌هايي» باشند «گشت»  با معكوس كردن به‌دست آمده و با  مشخص مي‌شود.

«گشت»  با الحاق ‌و  در به‌دست آمده و با ‌نشان داده مي‌شود.




بخشي از گشت (Section)

«بخشي» از «گشت» ‌عبارت است از «گشتي» كه زيردنباله‌اي از  شامل عبارت‌هاي پي‌درپي از «گشت»  است. اصطلاحاً به آن بخش  از «گشت» ‌اطلاق مي‌شود.

در يك گراف «ساده»، يك «گشت»  با دنباله‌ي  از رؤوسش مشخص مي‌شود. علاوه بر آن حتي در گراف‌هايي كه «ساده» محسوب نمي‌شوند گاهي اوقات بايد به دنباله‌اي از رؤوس استناد كنيم كه عبارت‌هاي پي‌درپي آن به‌عنوان يك «گشت» مجاور هستند. در چنين حالت‌هايي فهميده مي‌شود كه بحث براي هر «گشتي» با رؤوس پي‌درپي صادق است.


شكل 31 - «گشت» (uavfyfvgyhwbv)،
«گذر» (wcxdyhwbvgy)
«مسير» (xcwhyeuav).






گذر (Trail) و «مسير» (Path)

اگر يال‌هاي  از يك «گشت»  ‌«مجزا» باشند اصطلاحاً گفته مي‌شود «گشت» ‌يك «گذر» (Trail) است. در اين حالت، طول «گشت» ‌دقيقاً  است.

اگر ‌علاوه بر آن، رؤوس «مجزا» باشند «مسير» (Path) ناميده مي‌شود (شكل 16).

ياداوري – از اصطلاح «مسير» (Path) هم‌چنين براي گراف يا زيرگرافي استفاده مي‌شود كه يال‌ها و رؤوسش برحسب يك «مسير» هستند.


شكل 32 – يك گراف همبند.

شكل 33 – يك گراف غيرهمبند با سه جزو.

شكل 34 - يك گراف غيرهمبند با سه جزو.





همبند (Connected)


 
دو رأس  و از گراف «همبند» (Connected) گفته مي‌شود اگر يك مسير در گراف ‌وجود داشته باشد. همبندي رابطه‌ي هم‌ارزي در مجموعه رؤوس  است.

بنابراين شرط لازم و كافي براي آن‌كه بخشي از مجموعه رؤوس  به زيرمجموعه‌ي غيرتهي ‌وجود داشته باشد آن است كه هر دو رأس و به يك مجموعه تعلق داشته باشد.

زيرگراف‌هاي ‌«اجزاي» (Components) گراف ناميده مي‌شوند. اگر گراف  داراي دقيقاً يك «جزو» (Component) باشد گراف  «همبند» (Connected) است. در غير اين‌صورت، گراف  «غيرهمبند» (Disconnected) خواهد بود.

تعداد اجزاي گراف با  مشخص مي‌شود (اشكال 31، 32 و 33).




كاربردهايي از مفاهيم مسيرها و همبندي (Paths and Connection)



موارد ذيل را مي‌توان درباره‌ي مفاهيم مسيرها و همبندي اثبات كرد:

 اگر يك «گشت»  در گراف وجود داشته باشد آن‌گاه يك «مسير»  هم‌چنين وجود دارد. 
 تعداد «گشت‌هاي»  به‌طول  در گراف ، درايه‌ي ام از  است.
 اگر گراف «ساده» بوده و  در اين صورت مسيري به‌طول  وجود دارد.
 شرط لازم و كافي براي اين‌كه گراف «همبند» باشد آن است كه براي هر بخش از  به مجموعه‌هاي غيرتهي  و  يك يال با يك انتها در  و يك انتها در وجود داشته باشد.
 گراف «همبند» (Connected)
اگر گراف  «ساده» باشد و داشته باشيم:





(رابطه‌ي 29)

در اين صورت گراف  «همبند» خواهد بود.

 گراف «همبند» (Connected)
اگر گراف «ساده» باشد و رابطه‌ي ذيل برقرار باشد:





(رابطه‌ي 30)

در اين صورت گراف  «همبند» خواهد بود.

 اگر گراف  «غيرهمبند» (Disconnected) باشد در اين صورت مكمل آن گراف يعني:  «همبند» (Connected) خواهد بود.
 اگر  باشد در اين صورت داريم:





(رابطه‌ي 31)

اگر در اين صورت معمولاً نمي‌تواند با  در نامساوي فوق (رابطه‌ي 31) جايگزين شود.

 اگر گراف  «همبند» بوده و هر درجه در گراف مذكور عددي «زوج» باشد براي هر رابطه‌ي ذيل برقرار است:






(رابطه‌ي 32)
    

 هر دو طولاني‌ترين مسير در يك گراف «همبند» داراي يك رأس مشترك هستند.
 فاصله‌ي بين رؤوس در يك گراف (Distance)
اگر رؤوس  و در گراف «همبند» باشند «فاصله‌ي» بين رؤوس  و در آن گراف – كه با مشخص مي‌شود – طول كوتاه‌ترين مسير در گراف  است.

اگر مسيري رؤوس  و را به هم مرتبط نكند اصطلاحاً گفته مي‌شود: «نامتناهي» (Infinite) است.

براي هر سه رأس ،  و رابطه‌ي ذيل برقرار است:





(رابطه‌ي 33)

 قطر يك گراف (Diameter)
«قطر» گراف  بيش‌ترين فاصله بين دو رأس از گراف است. اگر گراف  داراي قطري بزرگ‌تر از «سه» باشد گراف  («مكمل» گراف ) داراي قطري كم‌تر از «سه» است.
 اگر گراف  «ساده» بوده داراي «قطر» «دو» باشد و داشته باشيم:





(رابطه‌ي 34)

در اين صورت رابطه‌ي ذيل برقرار خواهد بود:





(رابطه‌ي 35)

 اگر گراف ‌«ساده» و «همبند» باشد اما «كامل» نباشد در اين صورت گراف  داراي سه رأس ،  و است به‌گونه‌اي كه داشته باشيم:





(رابطه‌ي 36)






(رابطه‌ي 37)


1386/12/17لينک مستقيم
نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 فعاليت هاي علمي

سرویس‌های رشد:

فهرست:

وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران (رشد)