زنگ‌تفریح تصادفی

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 نظريه‌ي گراف‌ها – قسمت اول (زنگ تفريح شماره‌ي 35)
نظريه‌ي گراف‌ها – قسمت اول (زنگ تفريح شماره‌ي 35)زنگ تفريح كامپيوتر
دو گراف يك‌ريخت

نظريه‌ي گراف‌ها – قسمت اول







شكل 1.

 

 

اشاره

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



چكيده

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





شكل 2.



مقدمه

«نظريه‌ي گراف‌ها» (Graph Theory) مطالعه‌ي نقاط و خطوط است؛ به‌خصوص وقتي كه مجموعه‌اي از نقاط به‌نام «رأس» (Vertice) بتوانند با خطوط يا كمان‌هايي به يكديگر متصل شوند. اين خطوط يا كمان‌ها اصطلاحاً «يال» (Edge) ناميده مي‌شوند.

«گراف‌‌ها» براساس متغيرهايي نظير ذيل طبقه‌بندي مي‌شوند:
    
- پيچيدگي
    
- تعداد يال‌هاي بين دو رأس 
    
- جهت يال‌هاي‌اشان
    
- و ...

مجموعه‌هاي متنوع از قواعد به‌دست آمده از ويژگي‌هاي خاص كه مي‌تواند در مورد «گراف‌ها» برقرار باشد «قضيه‌هاي گراف‌ها» ناميده مي‌شود.

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




شكل 3. 

شكل 4 - «لئونارد اويلر»
(Leonard Euler).


تاريخچه

به‌نظر مي‌رسد نخستين مقاله درباره‌ي «نظريه‌ي گراف»‌ در سال 1115 (1736 ميلادي) توسط رياضيدان سوييسي «لئورنارد اويلر» (Leonard Euler) با عنوان ذيل ارائه شده باشد: «اويلر، لئونارد؛ حل مسائلي از هندسه؛ صفحه‌ي 128 تا 140».

Leonhard Euler, "Solution problematis ad geometriam situs pertinentis"; pp 128-140.




شکل 5 - نمايي از شهر
«كونيكسرگ» (Konigsberg).


شهر «كونيكسرگ» (Konigsberg) – كه قبلاً جزو كشور آلمان و در حال حاضر در محدوده‌ي كشور روسيه است و بعداً «كالينينگراد» (Kaliningrad) ناميده شد – از دو جزيره و دو ساحل در دو طرف رودخانه‌ي «پريگر» (Preger) تشكيل شده هم‌چنين پل‌هاي زيبايي – كه بعداً «پريگوليا» (Pregolya) نام گرفت – بين اين چهار منطقه در جريان است.


شكل 6. 



گفته مي‌شود يكي از موضوع‌هايي كه ذهن مردم شهر «كونيكسرگ» (Konigsberg) را مشغول كرده بود پيدا كردن راهي بود كه بتوانند از منزل‌شان شروع به حركت كنند و تمام هفت پل را تنها يك‌بار طي نموده در نهايت به منزل برگردند.

«اويلر» امكان يا عدم امكان قدم زدن در اطراف پل «كونيكسرگ» (Konigsberg) را از روي پل‌ها، آن‌هم تنها با يك‌بار عبور از هر پل بررسي كرد. بدين‌ترتيب «نظريه‌ي گراف» (Graph Theory) براي مطالعه‌ي چنين مسائلي متولد شد!

مسأله‌ي پل «كونيكسرگ» (Konigsberg) به‌دنبال روش عبور از 7 پل شهر «كونيكسرگ» (Konigsberg) بر روي رودخانه‌ي «پريگر» (Preger) است به‌گونه‌اي از هر پل يك‌بار گذر انجام شده و بر روي هيچ پلي دو بار عبور انجام نگيرد. علاوه بر آن بايد پايان حركت همان شروع حركت باشد (اين مسأله معادل گرافي است با 4 گره و 7 يال).

براي مطالعه‌‌ي داستان خواندني اين تحقيق مي‌توانيد به وب‌سايت به‌نشاني ذيل مراجعه فرماييد:

http://www.ams.org/bull/2006-43-04/S0273-0979-06-01130-X/
S0273-0979-06-01130-X.pdf

 




شکل 7.

شكل 8.

«اويلر» (Euler) فهميد كه همه‌ي مسائلي از اين دست را مي‌توان با جايگزيني‌هاي ذيل بيان كرد:
    
- «سطوح زمين» با «نقاطي» كه وي «رأس» ناميد 
    
- جايگزيني «پل‌ها» با «كمان»‌ها 
    
- و ...

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

براي اين‌ منظور از نقطه‌ي شروع حركت آغاز مي‌كنيم؛ وارد آن شده آن را ترك مي‌نماييم. توجه كنيد نمي‌توانيم مسيري را برگرديم. بدين‌ترتيب هر «رأس» با تعداد «فردي» از كمان‌هاي متصل به آن مي‌تواند شروع شود يا پايان مسير مدادمان باشد. بنابراين تنها دو رأس «فرد» مي‌توانيد داشته باشيد.

در مثال شهر «كنيگزبورگ» (Konigsberg) مشاهده مي‌كنيد بدون تكرار مسير نمي‌توانيد تمام مسيرها را طي كنيد (شكل 8).

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

همان‌طور كه ملاحظه مي‌كنيم تعداد پل‌ها در شهر «كونيكسرگ» (Konigsberg) «فرد» است.

يكي از موضوع‌هاي مهم در «نظريه‌ي گراف»، «مدارهاي اويلري» (Eulerian Circuit) است كه از اين مسأله گرفته شده است زيرا «اويلر» (Euler) با تعميم چنين تفكري، تعاريفي نظير ذيل را ارائه داد:

- شبكه (Network)
يك «شبكه» شكلي از نقاط به‌نام «رأس» است كه با خطوط غيرمتقاطع (كمان) به يكديگر وصل شده‌اند.

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

- مسير اويلري (Eulerian Path)
يك «مسير اويلري» مسيري پيوسته است كه از هر «كمان» آن تنها و تنها يك‌بار گذر انجام مي‌شود.

«اويلر» (Euler) هم‌چنين دو قضيه‌ي ذيل را نيز ثابت كرد:

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

اويلر عكس اين قضيه را نيز ثابت كرد:

قضيه‌ي 2
«اگر شبكه‌اي داراي دو رأس يا كم‌تر باشد داراي حداقل يك مسير اويلري است».


بنابراين گراف الف از شكل 9 مثالي از «گراف اويلري» و گراف ب از آن شكل مثالي از «گراف غيراويلري» است.

الف

ب

شكل 9.

 

كاربرد «گراف‌هاي اويلري» فراوان است. از مثال‌هاي ساده‌ي آن، مي‌توان به مواردي نظير: ارسال پستي، برف‌روبي و جارو كردن خيابان‌ها و ... اشاره كرد. در همه‌ي اين مثال‌ها، گذر بيش از يك‌بار باعث اتلاف وقت (يا به‌طور كلي: اتلاف منابع) مي‌شود. بنابراين «گراف‌هاي اويلري» بيان‌كننده‌ي راه‌حل‌هاي بهينه‌ي براي جلوگيري از اتلاف وقت (يا به‌طور كلي: اتلاف منابع) است.


شكل 10.

شكل 11.


در سال 1137 (1758 ميلادي) بعد از گذشت دو دهه از حل مسأله‌ي پل «كنيگزبورگ» (Konigsberg)، «اويلر» براي دومين بار با ارائه‌ي فرمولش براي «گراف‌هاي مسطح (صفحه‌اي)» (Planar Graph) سهم بزرگي در «نظريه‌ي اعداد» ايفا كرد. «گراف‌هاي مسطح (صفحه‌اي)» (Planar Graph) گراف‌هايي هستند كه مي‌توانند در يك صفحه رسم شوند بدون آن‌كه دو يال آن تقاطع پيدا كنند. عمل رسم چنين گراف‌هايي اصطلاحاً «رسم مسطح (صفحه‌اي)» آن گراف‌ها ناميده مي‌شود. به‌عنوان مثال، گراف شكل 11 «رسم مسطح» گراف شكل 10 محسوب مي‌شود.

رياضيداني آلماني به‌نام «كارل هايرهولزر» (Carl Hierholzer) كامل‌ترين ويژگي‌هاي «گراف‌هاي اويلري» را در سال 1252 (1873 ميلادي) با اثبات موضوع ذيل منتشر كرد: «گراف‌هاي اويلري» دقيقاً گراف‌هايي هستند همبند كه هر «رأس» آن داراي درجه‌ي «زوج» است».


شكل 12 - «سر ويليام روان هاميلتن»
(Sir William Rowan Hamilton)


«توماس پنينگتون كيركمن» (Thomas Pennyngton Kirkman)
در سال 1235 (1856 ميلادي) و «سر ويليام روان هاميلتن» (Sir William Rowan Hamilton) در سال 1235 (1856 ميلادي) روش‌هاي گذر آن‌هم تنها يك‌بار از مكان‌هايي نظير: پل «كونيكسرگ» (Konigsberg) را مطالعه كردند.

آنان با مطالعه بر روي حلقه‌هاي (Cycle) چندوجهي‌ها، مفهوم «گراف هاميلتون» (Hamiltonian Graph) را ارائه كردند.

در سال 1231 (1852 ميلادي) محققي به‌نام «فرانسيس گوتري» (Fancis Guthrie) مسأله‌ي مشهور «چهار رنگ» را بدين‌شكل مطرح كرد:

«آيا ممكن است با استفاده از «چهار رنگ» هر نقشه‌اي از كشورها را به‌گونه‌اي رنگ كرد كه هيچ دو كشور هم‌مرزي داراي رنگ يكسان نباشند؟»

در سال 1258 (1879 ميلادي) «آلفرد ب. كمپ» (Alfred B. Kempe) اثباتي ناصحيح و در عين حال مشهوري براي اين مسأله ارائه كرد. اين مسأله تا سال 1351 (1976 ميلادي) حل‌نشده باقي ماند تا اين‌كه نهايتاً توسط «كنت اپل» (Kenneth Appel) و «ولفگانگ هيكن» (Wolfgang Haken) با استفاده از يك كامپيوتر حل شد. بدين‌ترتيب خيلي از اصطلاح‌ها و مفاهيم «نظريه‌ي گراف» امروزي در جهت تلاش براي حل مسأله‌ي «چهار رنگ» شكل گرفت.

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

اگرچه بيش‌تر رياضيدانان روش اثبات آن انگاره را پذيرفتند ولي در سال 1380 (2001 ميلادي) «نيل رابرترون» (Neil Roberton)، «دانيل ساندرز» (Daniel Sanders)، «پائول سيمور» (Paul Seymour) و «رابين توماس» (Robin Thomas) اثباتي ساده و منظم‌تر براي اين مسأله ارائه كردند.

مفهوم «درخت» (Tree) يعني يك گراف متصل بدون «حلقه» در پژوهش‌هاي «گوستاو كيرشهوف» (Gustav Kirchhoff) ظاهر شد. وي عقايد نظري گراف را در محاسبه‌ي جريان الكتريكي در شبكه‌هاي الكتريكي به‌كار برد.

بعدها «آرتور كيلي» (Arthur Cayley)، «جيمز ج. سيلوستر» (James J. Sylvester)، «جورج پوليا» (George Polya) و محققان ديگر از «درخت» (Tree) براي محاسبه‌هاي مولكول‌هاي شيميايي استفاده كردند.

مطالعه بر روي «گراف‌هاي مسطح (صفحه‌اي)» (Planar Graph) از دو مسأله‌ي سرگرم‌كننده به‌نام‌هاي ذيل نشأت گرفت:

- گراف كامل K5

- گراف دو قسمتي K3,3


شكل 13 - «كازيميرز كوراتوفسكي»
(Kazimierz Kuratowski)

شكل 14 - «آگوست فرديناند موبيوس»
(August Ferdinand Möbius)

شكل 15 - گراف كامل K5

 

همان‌طور كه نهايتاً «كازيميرز كوراتوفسكي» (Kazimierz Kuratowski) ثابت كرد اين گراف‌ها مسطح نيستند.

اولين مسأله‌ي تاريخي از «گراف كامل K5» توسط «آگوست فرديناند موبيوس» (August Ferdinand Möbius) در سال 1219 (1840 ميلادي) به‌صورت ذيل مطرح شد:

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

مسأله‌ي تاريخي ذيل مربوط به بررسي توانايي يك فرد در رسم پنج منطقه‌ با مرزهاي مشترك در صفحه است:

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


شكل 16 - گراف دو قسمتي K3,3

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

شكل 18 - «آلفرد رني»
(Alfred Renyi)

مبدأ مسأله‌ي ذيل به‌عنوان مثالي از: «گراف دو قسمتي K3,3» نامعلوم است اما مي‌دانيم اولين بار در سال 1292 (1913 ميلادي) توسط «هنري ارنست دودني» (Henry Ernest Dudeney) بدين‌شكل مطرح شد:

«مسأله‌ي گيج‌كننده عبارت است از: استقرار تجهيزات آب، گاز و برق بدون آن‌كه هيچ لوله يا خطي با ديگري تقاطع داشته باشد».

در سال 1338 (1959 ميلادي) محققاني به‌نام‌هاي «پائول اردوش» (Paul Erdos) و «آلفرد رني» (Alfred Renyi)، «گراف‌هاي تصادفي» (Random Graph) را تعريف كردند:‌ «گره كه هر دو گره آن با احتمال  به يكديگر مرتبط شده‌اند».

بيش‌تر مطالعه‌ها بر روي «شبكه‌هاي تصادفي» (Random Networks) بر اين مطلب متمركز شده است كه چه نوع احتمال ارتباط  ويژگي مخصوص يك گراف بوده بيش‌تر اتفاق مي‌افتد. لازم به‌ذكر است كه مفهوم «گراف تصادفي» توصيف شبكه‌هاي بزرگ‌تر را ممكن مي‌كند.




علايم

موقعيت‌هاي بسياري در جهان وجود دارد كه به‌راحتي مي‌توان از يك نمودار - با مجموعه‌اي از «نقاط» همراه با «خطوطي» كه برخي دو نقطه از مجموعه‌ي نقاط را به‌هم وصل مي‌كند - براي توصيف آن استفاده كرد.

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

- «نقاط» مي‌توانند بيان‌كننده‌ي افراد بوده و «خطوط» بين افرادي كه با هم دوست هستند رسم شود.

 

- «نقاط» ممكن است بيانگر مراكز ارتباطي بوده و «خطوط» بيانگر ارتباط‌هاي اجتماعي باشد.

توجه كنيم كه در چنين نمودارهايي آن‌چه عمدتاً بر روي آن تمركز مي شود آن است كه آيا دو نقطه‌ي داده شده با يك خط به‌هم مرتبط شده‌اند يا خير. از طرف ديگر «چگونگي ارتباط» اهميتي ندارد. توصيف رياضي وجود چنين ارتباطي، منجر به مفهوم «گراف» مي‌شود.

يك گراف با عبارت سه‌گانه‌ي  نوشته مي‌شود كه عبارت‌هاي آن عبارت است از:

 = مجموعه‌ي رؤوس
 = مجموعه‌ي يال‌ها

 = «تابع وابسته» (Incident Function)
«تابع وابسته» (Incident Function) ترتيبي از «رؤوس» گراف  را با هر «يال» گراف مذكور مرتبط مي‌كند.

ياداوري 1 - «رؤوس» مرتبط شده توسط «تابع وابسته» (Incident Function) لزوماً نبايد مجزا باشند.

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

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




(رابطه‌ي 1)


شكل 19 - نمودار گراف .

شكل 20 – نمودارهاي گراف‌هاي .

 

 

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

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



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






(رابطه‌ي 2)

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





(رابطه‌ي 3)

مثالي ديگر:

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





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








(رابطه‌ي 4)

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







(رابطه‌ي 5)

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


 

 

شكل 21 – شكلي ديگري
از نمودار گراف
  در اين گراف
هيچ خطي باديگري متقاطع نيست
به‌جز در «رأس‌هاي» گراف.


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

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


شكل 22.




تعاريف

شكل 23.

شكل 24.

گراف‌هايي كه داراي نموداري هستند كه يال‌هاي‌شان تنها در انتها با يكديگر تلاقي دارند «گراف مسطح» (صفحه‌اي) ناميده مي‌شوند به‌خاطر آن‌كه چنين گراف‌هايي در يك صفحه مي‌توانند به‌شكلي ساده رسم شوند. شكل 23 نمونه‌اي از «گراف مسطح» (صفحه‌اي) است؛ اگرچه در نگاه اول ممكن است مطابق تعريف آن به‌وضح تطابق با تعريف را نتوان مشاهده كرد.

به‌عكس اگر گرافي «مسطح» (صفحه‌اي) نباشد «غيرمسطح» (غيرصفحه‌اي) است. شكل 24 نمونه‌اي از «گراف غيرمسطح» (غيرصفحه‌اي) است.

بسياري از تعريف‌ها و مفاهيم در «نظريه‌ي گراف» به‌صورت گرافيكي بيان مي‌شود:

اصطلاحاً مي‌گويند: انتهاي يك يال به آن يال وابسته است و برعكس.
 رؤوس مجاور
دو رأسي كه وابسته به يك يال مشترك باشند «مجاور» (Adjacent) ناميده مي‌شوند.

 يال‌هاي مجاور
دو يال «مجاور» يال‌هايي هستند كه وابسته به يك رأس مشترك مي‌باشند.

 حلقه و لينك
يك يال كه داراي دو انتهاي كاملاً يكسان باشند يك «حلقه» و يك يال با دو انتهاي مجزا يك «لينك» ناميده مي‌شود.

به‌عنوان مثال:
يال  از گراف  (شكل 21) يك «حلقه» و همه‌ي يال‌هاي ديگر آن «لينك» هستند.

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

 گراف «ابتدايي» (Trivial) و «غيرابتدايي» (Nontrivial)
يك گراف با تنها يك «رأس» گراف «ابتدايي» (Trivial) و همه‌ي گراف هاي ديگر «غيرابتدايي» (Nontrivial) ناميده مي‌شوند.

 گراف «ساده» (Simple) و «غيرساده»
گرافي «ساده» (Simple) ناميده مي‌شود كه هيچ «حلقه‌اي» نداشته و هيچ دو «لينكش» در دو رأس به يكديگر متصل نشده باشند (شكل‌هاي 23 و 24‌). شكل‌هاي 19 و 20نمونه‌اي از گراف‌هاي «غيرساده» هستند.

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





(رابطه‌ي 6)


كه در آن  تعداد يال‌ها و  تعداد رأس‌هاي گراف مذكور است.



شكل 25.


گراف «كامل» (Complete)
يك گراف «ساده» كه در آن هر زوج رأس مجزا با يك يال مرتبط شوند يك «گراف كامل» (Complete) ناميده مي‌شود. تنها يك گراف «كامل»  با رأس وجود دارد كه با  نشان داده مي‌شود. نمونه‌اي از گراف  در شكل 25 نشان داده شده است.

 گراف «تهي» (Empty)
يك گراف «تهي» (Empty) گرافي است كه فاقد هرگونه يالي است.

 گراف «دو بخشي» (Bipartite)
يك گراف «دو بخشي» (Bipartite) گرافي است كه مجموعه‌ي رأس‌هايش مي‌تواند به دو زيرمجموعه‌ي و به‌گونه‌اي تقسيم شود كه هر يال يك انتها در  و انتهايي ديگر در داشته باشد. به چنين بخشي از  «دو بخش» (Bipartioton) گراف مي‌گويند.

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

اگر  باشد چنين گرافي با  نشان داده مي‌شود.


شكل 26.

شكل 27.

به‌عنوان مثال: گرافي كه با رؤوس و يال‌هاي يك مكعب تعريف مي‌شود (شكل 27) گراف «دوبخشي» است. در حالي كه گراف شكل 27 گراف «كامل دوبخشي» محسوب مي‌شود.

اكنون در گراف‌هاي متعدد ذيل، انواع را مشخص كنيد.

شكل 28 - .

شكل 29.

شكل 30.

شكل 31.

شكل 32 - گراف گرومبائوم
(Grunbaum).

شكل 33 - گراف گرين وود، گليسون
(Greenwood - Gleason).

شكل 34 - گراف
چواتال (Chevatal)

شكل 35.

شكل 36.

شكل 37.

شكل 38.

شكل 39 - مكعب.

شكل 40 - گراف توته كوگزتر
(Tutte - Coexeter).

شكل 41 - گراف رابرتسون
(Robertson).

شكل 42 - گراد هيوود
(Heawood).

شكل 43 - گراف مك گي
(McGee Graph).

شكل 44 - گراف فولكمن
(Folkman Graph).

شكل 45‌ - گراف پيترسون
(Petersen Graph).

شكل 46 - گراف
بيست وجهي (Icosahedron).

شكل 47 - گراف
دوازده وجهي (Dodecahedron)    .

شكل 48 - گراف
هشت‌وجهي (Octahedron).

شكل 49 - گراف
چهاروجهي (Tetrahedron).

شكل 50.

شكل 51.

شكل 52.

شكل 53.

شكل 54 - گراف فرانكلين
(Franklin).

شكل 55 - كوچك‌ترين گراف سه‌وجهي
منظم (The Smallest 3-Regular)

شكل 56 - گراف هورتون
(Horton).

شكل 57 - گراف كوگزتر
(Coxeter).

شكل 57.

شكل 58 - گراف تيتزه
(Tietze).





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

دو گراف  و  «معادل» (Identical) هستند و نوشته مي‌شود:  اگر داشته باشيم:








(رابطه‌ي 7)

اگر دو گراف «معادل» باشند به‌وضوح با نمودارهاي يكساني نمايش داده مي‌شوند.

اما ممكن است دو گراف «معادل» ‌نباشند در عين حال اساساً داراي نمودارهاي يكساني باشند. به‌عنوان مثال، نمودار گراف   و به‌ترتيب در شكل‌هاي 20 و 21 كاملاً يكسان به‌نظر مي‌رسند با اين تفاوت كه رؤوس و يال‌هاي‌شان داراي نام‌هاي متفاوتي هستند. بدين‌ترتيب گراف‌هاي   و  معادل نيستند ولي «يك‌ريخت» (Isomorphic) ناميده مي‌شوند.




تعريفي رياضي گراف‌هاي «يك‌ريخت» (Isomorphism)

اگر بخواهيم تعريفي رياضي و البته كمي مشكل از گراف‌هاي «يك‌ريخت» ارائه كنيم مي‌توانيم اين‌گونه بيان كنيم:

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





به‌گونه‌اي كه داشته باشيم:




(رابطه‌ي 8)

اگر و فقط اگر رابطه‌ي ذيل برقرار باشد:




(رابطه‌ي 9)

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

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











(رابطه‌ي 10)

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




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







(رابطه‌ي 11)

در اين‌صورت با رابطه‌هاي ذيل تعريف مي‌شود:






(رابطه‌ي 12)

هم‌چنين گراف را به‌صورت ذيل در نظر مي‌گيريم:




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






(رابطه‌ي 13)

در اين صورت گراف‌هاي   و  داراي ساختاري يكسان بوده و تنها در نام‌گذاري «رؤوس» و «يال‌ها» با هم تفاوت دارند. همان‌طور كه گفته شد ويژگي‌هاي ساختاري از اهميت برخوردارند و در اين مورد از نام‌گذاري رؤوس و يال‌ها صرف‌نظر مي‌شود. يك گراف بدون نام‌گذاري رؤوس و يال‌ها بيانگر طبقه‌اي از گراف‌هاي «معادل» است.

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

1386/11/1لينک مستقيم

فرستنده :
مهرداد اصولی HyperLink HyperLink 1386/11/27
مـتـن : با سلام
مطالب واقا" به درد خورد و موثر بود
ممنون
پاسـخ :ايميل فرستنده: ossuli@gmail.com
صفحه‌ي شخصي: www.mehonline.com
تاريخ ارسال: 1386/11/10

مهرداد جان!
از اظهار لطفت تشكر مي‌كنيم.
راستي نگفتي كدام بخش رضايت شما رو جلب كرده است؟
انشاءالله موفق باشي!

فرستنده :
پرهیزکاری HyperLink HyperLink 1386/11/9
مـتـن : به نام خدا
مطلب فوق بخوصوص شکلها که در تفهیم یک ریختی کمک می کنند بسیار عالی است.ولی در نگارش با ریاضیات گسسته پیش دانشگاهی اندکی تفاوت دارد که باعث استفاده کم توسط دانش آموزان شود (در این مواقع به مخاطب وقراردادهای ذهنی اش توجه بیشتری شود)
پاسـخ :ايميل فرستنده: bp2006kn@yahoo.com
تاريخ ارسال: 1386/11/7

جناب پرهيزكاري
سلام عليكم
از اظهار لطفي كه نسبت به مطلب ارائه شده داشتيد تشكر مي‌كنيم.
ضمن اين‌كه تذكر بسيار به‌جايي به كارشناسان‌مان داديد كه سعي مي‌كنيم اين نكته‌ي ارزشمند رو در قسمت‌هاي بعدي رعايت بكنيم.
خيلي خوشحال مي‌شويم چنان‌چه حضرتعالي ما را در بهبود كيفيت مطالب ارائه شده با نظرهاي اصلاحي خودتان ياري بفرماييد.
ضمناً اگر بفرماييد در چه سمتي مشغول هستيد باعث خوشحالي ما خواهد شد.
با عرض احترام مجدد و آرزوي موفقيت

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 زنگ تفريح‌ها

 
 المپياد كامپيوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  8023
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  8023