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

شكل 2.

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

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

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

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

شكل 3.

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

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

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

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

شكل 6.

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

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

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

شکل 7.

شكل 8.

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

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

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

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

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

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

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

«اويلر» (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) از دو مسأله‌ي سرگرم‌كننده به‌نام‌هاي ذيل نشأت گرفت:

شكل 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 براي گراف  رسم كرد.

ممكن است دو يال در يك گراف با يكديگر در غير از «رأس» تلاقي داشته باشند (به‌عنوان مثال: در شكل 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).

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

(رابطه‌ي 7)

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

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

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

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

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

(رابطه‌ي 8)

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

(رابطه‌ي 9)

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

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

(رابطه‌ي 10)

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

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

(رابطه‌ي 11)

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

(رابطه‌ي 12)

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

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

(رابطه‌ي 13)

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

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