| موارد كاربردي از گراف‌هاي ساده و گراف‌هاي «معادل» و گراف‌هاي «يكريخت» (Isomorphism) |
موارد ذيل را مي‌توان نشان داد: |  اگر گراف  «ساده» (Simple) باشد خواهيم داشت:
(رابطه‌ي 1) | | اگر گراف‌هاي و .gif) «يكريخت» (Isomorphism) باشند يعني داشته باشيم:
(رابطه‌ي 2) در اين صورت خواهيم داشت:
(رابطه‌ي 3)
(رابطه‌ي 4) ولي عكس اين رابطه برقرار نيست به‌عبارت ديگر نمي‌توان از رابطه‌‌‌هاي 3 و 4 رابطه‌ي 2 را به‌دست آورد.
| | دو گراف و «ساده‌ي» و «يكريخت» (Isomorphism) هستند اگر و فقط اگر يك تابع «يك به يك» نظير: .gif) وجود داشته باشد به‌گونه‌اي كه .gif) اگر و فقط اگر داشته باشيم:
| | فرض كنيد گرافي «ساده» باشد؛ در اين صورت رابطه‌ي ذيل برقرار است:
(رابطه‌ي 5) اگر و فقط اگر «كامل» باشد. | | تعداد يال‌هاي گراف «دوبخشي كامل» (Complete Bipartite Graph) .gif) از رابطه‌ي ذيل به‌دست مي‌آيد:
(رابطه‌ي 6)
| | اگر گرافي «ساده» (Simple) و «دوبخشي» (Bipartite) باشد در اين صورت خواهيم داشت:
(رابطه‌ي 7) | | تعاريف ذيل را به‌دقت توجه كنيد:
|  يك گراف «.gif) بخشي» (k-Partite) گرافي است كه مجموعه رؤوس آن مي‌تواند به زيرمجموعه به‌گونه‌اي تقسيم شود كه دو انتهاي هيچ يالي در يك زيرمجموعه وجود نداشته باشد.
| | يك گراف « بخشي كامل» (Complete k-Partite) گرافي است كه «ساده» بوده و در آن هر رأسي كه رأس ديگر متصل شده است در زيرمجموعه‌ي يكساني نباشد. | | يك گراف «.gif) بخشي كامل» (Complete m-Partite) با .gif) رأس كه در آن هر بخش داراي .gif) يا .gif) رأس باشد با .gif) نشان داده مي‌شود. |
مي‌توان نشان داد رابطه‌ي ذيل درباره‌ي يك گراف « بخشي كامل» (Complete k-Partite) همواره برقرار است:
(رابطه‌ي 8) كه در آن داريم:
(رابطه‌ي 9) هم‌چنين مي‌توان نشان داد: اگر يك گراف « بخشي كامل» (Complete m-Partite) با رأس باشد در اين صورت داريم:
(رابطه‌ي 10)
| | ياداوري – تساوي در رابطه‌ي 10 يعني: .gif) زماني برقرار است كه گراف‌هاي و «يكريخت» باشند به‌عبارت ديگر داشته باشيم:
(رابطه‌ي 11)
| | تعريف ذيل را درنظر بگيريد: يك گراف « مكعب» (k-Cube) گرافي است كه رؤوس آن تايي از «صفر» و «يك» هستند كه دو رأس آن به يكديگر متصل هستند اگر و فقط اگر دو رأس‌شان دقيقاً در يك مؤلفه با يكديگر تفاوت داشته باشند. به‌عبارت ديگر اگر عددي طبيعي باشد منظور از « مكعب» گرافي است كه رأس‌هاي آن همه‌ي دنباله‌هاي رقمي از «صفر» و «يك» هستند و دو رأس در اين گراف مجاور بوده هرگاه دنباله‌هاي متناظرشان دقيقاً در يك مؤلفه اختلاف داشته باشند (شكل 1).
| شكل 1 – گراف « مكعب» به‌ترتيب از سمت چپ:
«يك مكعب»، +«دو مكعب» و «سه مكعب». |
ياداوري - توجه داشته باشيد كه شكل 26 در زنگ تفريح شماره‌ي 35 تنها يك گراف «3 مكعب» است.
مي‌توان نشان داد كه يك گراف « مكعب» (k-Cube) داراي ويژگي‌‌هايي نظير ذيل است:
| - تعداد رؤوس = .gif) | | - تعداد يال‌ها = .gif) | | - گرافي «دوبخشي» (Bipartite) است. |
| | «مكمل» گراف (Complement)
«مكمل» (Complement) يك گراف «ساده» – كه معمولاً با .gif) نشان مي‌دهند - يك گراف «ساده» با مجموعه رؤوس .gif) و دو رأس «مجاور» در است اگر و فقط اگر رؤوس در گراف «مجاور» نباشند.
| | گراف «خود مكمل» (Self-Complement)
يك گراف «ساده» نظير: «خود مكمل» (Self-Complement) است اگر داشته باشيم:
(رابطه‌ي 12) مي‌توان نشان داد كه اگر گرافي «خود مكمل» (Self-Complement) باشد در اين صورت خواهيم داشت:
(رابطه‌ي 13)
| | «هم‌ريختي» (Automorphism)
بنابر تعريف «هم‌ريختي» (Automorphism) يك گراف عبارت است از: يك‌ريختي آن گراف بر روي خودش (شكل 2). به‌عنوان مثال: قرينه‌هاي آينه‌اي يك گراف نسبت به محورهاي عمودي و افقي مي‌تواند به‌عنوان «هم‌ريخت‌هاي» يك گراف محسوب شوند.
.gif)
| شكل 2 – نمونه‌اي از گراف‌هاي
«هم‌ريختي» (Automorphism).
| | .gif)
| شكل 3 – گراف «ستاره» (Star)
و گراف‌هاي «هم‌ريخت» آن. |
| | مثالي ديگر: يك گراف «ستاره» (Star) داراي شش گراف «هم‌ريخت» است (شكل 3). موارد ذيل را مي‌توان درباره‌ي «هم‌ريختي» (Automorphism) اثبات كرد:
|  «هم‌ريختي» (Automorphism)
«هم‌ريختي» (Automorphism) يك گراف «ساده‌ي» مي‌تواند به‌عنوان جايگشتي بر روي درنظر گرفته شود كه «مجاورت» را حفظ مي‌كند و اين‌كه چنين جايگشت‌هايي، يك گروه .gif) (با عنوان: گروه «هم‌ريخت» گراف ) تحت عمليات غيرمعمول تركيب تشكيل مي‌دهند. براي هر گراف «ساده‌ي» رابطه‌ي ذيل برقرار است:
(رابطه‌ي 14) 
| شكل 4 – نمونه‌هايي از گراف‌هاي
«رأس متقارن» (Vertex Transitive). | | .gif)
| شكل 5 – سمت چپ و راست به‌ترتيب
گراف «يگانه»(Singleton) و گراف «دو مسيره» (2-Path Graph). | | 
| شكل 6 – سمت چپ و راست به‌ترتيب
گراف «پيترسون» (Peterson) و گراف «كوگزتر» (Coxeter). | | .gif)
| شكل 7 – سمت چپ و راست به‌ترتيب گراف «مكعب متقارن»
(Cubic Transitive Graph 66) و گراف «كوگزتر مثلث جايگزين»
(Triangle Replaced Coexeter Graph). |
| | گراف «رأس متقارن» (Vertex Transitive)
يك گراف «ساده»، «رأس متقارن» (Vertex Transitive) است اگر براي هر دو رأس .gif) و .gif) ، يك «عنصر» (Element) نظير: .gif) در وجود دارد به‌گونه‌اي كه داشته باشيم:
(رابطه‌ي 15) به‌عبارت ديگر، يك گراف «رأس متقارن» (Vertex Transitive) است اگر گروه «هم‌ريختي» (Automorphism) آن براي رؤؤسش، متقارن عمل كند. به بياني ديگر، شرط لازم و كافي براي آن‌كه يك گراف «رأس متقارن» (Vertex Transitive) باشد آن است كه با «مكملش» (Complement) هم‌ارز باشد.
.gif)
| شكل 8 – نمونه‌هايي از گراف‌هاي «يال متقارن» (Edge Transitive). | | 
| شكل 9 – نمونه‌هايي از گراف‌هاي «يال متقارن» (Edge Transitive). |
| | گراف «يال متقارن» (Edge Transitive)
گراف «يال متقارن» (Edge Transitive) است اگر براي هر دو يال .gif) و .gif) ، يك «عنصر» (Element) نظير: .gif) در وجود داشته باشد به‌گونه‌اي كه داشته باشيم:
(رابطه‌ي 16) به‌عبارت ديگر، يك گراف «يال متقارن» (Edge Transitive) است اگر گروه «هم‌ريختي» (Automorphism) آن براي يال‌هايش، متقارن عمل كند. يك «يال هم‌ريختي» (Edge Automorphism) يك گراف عبارت است از جايگشت يال‌هايي كه رابطه‌ي «يال مجاورتي» (Edge- Adjacency) را حفظ كند.
گراف «نيمه‌متقارن» (Semisymmetric) . «متقارن» (Symmetric)
يك گراف «منتظم» (Regular) كه «يال متقارن» (Edge Transitive) باشد ولي «رأس متقارن» (Vertex Transitive) نباشد گراف «نيمه‌متقارن» (Semisymmetric) ناميده مي‌شود.
در عوض گرافي كه هم «يال متقارن» (Edge Transitive) و هم «رأس متقارن» (Vertex Transitive) باشد «گراف متقارن» (Symmetric) ناميده مي‌شود.
.gif)
| شكل 10 – گراف «صفر معمولي»
(صفر - Regular). | | .gif)
| شكل 11 – گراف «يك معمولي»
(1 - Regular). | | .gif)
| شكل 12 – گراف «دو معمولي»
(2 - Regular). | | .gif)
| شكل 13 – گراف «سه معمولي»
(3 - Regular). |
| | گراف «منتظم» (Regular)
ياداوري – يك گراف «منتظم» (Regular) گرافي است كه هر رأس آن داراي تعداد همسايه‌هاي يكساني باشد. به‌عنوان مثال:
هر رأس گراف «منتظم» داراي «درجه‌ي» يكساني است. يك گراف «منتظم» كه هر رأس آن داراي درجه‌ي است گراف « منتظم» (k-Regular) ناميده مي‌شود. بنابراين گراف‌هاي «منتظم» با حداكثر درجه‌ي 2 خيلي راحت طبقه‌بندي مي‌شوند:
|  گراف «صفر منتظم» (صفر - Regular)
يك گراف «صفر منتظم» داراي رؤوس غيرمتصل (غيرهمبند) است.
| | گراف «يك منتظم» (1 - Regular)
يك گراف «يك منتظم» داراي يال‌هاي غيرمتصل (غيرهمبند) است.
| | گراف «دو منتظم» (2 - Regular)
يك گراف «دو منتظم» داراي حلقه‌هاي غيرمتصل (غيرهمبند) است.
| | يك گراف «سه منتظم» (3 - Regular) به گراف «مكعبي» (Cubic) شهرت دارد.
| | يك گراف «اكيداً منتظم» (Strongly Regular) گرافي منتظمي است كه در آن هر زوج رأس مجاور داراي تعداد همسايه‌هاي يكسان بوده و هر زوج رأس‌هاي غيرمجاور داراي تعداد .gif) همسايه‌ي يكسان هستند. به‌عنوان مثال:
از ساده‌ترين گراف‌هايي كه «منتظم» (Regular) بوده ولي «اكيداً منتظم» (Strongly Regular) نباشند مي‌توان به گراف‌هاي ذيل اشاره كرد:
براين اساس، يك گراف «كامل» (Complete) .gif) ، گرافي «اكيداً منتظم» (Strongly Regular) براي هر .gif) است. |
|
|
| ماتريس‌هاي «وقوع» (Incidence) و «مجاورت» (Adjacency) |
به هر گراف يك ماتريس .gif) نسبت داده مي‌شود كه ماتريس «وقوع» ناميده مي‌شود. رؤوس ماتريس را با .gif) و يال‌هاي آن را با .gif) نشان مي‌دهيم:
 | شكل 14 – گراف . | | 
| شكل 15 - ماتريس «وقوع» گراف . | | 
| شكل 16 - ماتريس «مجاورت» گراف . |
ماتريس «مجاورت» (Adjacency) يك گراف معمولاً كوچك‌تر از ماتريس‌هاي «وقوع» (Incidence) آن گراف بوده و گراف‌ها در اين شكل هستند كه عموماً در كامپيوترها ذخيره مي‌شوند.
| موارد كاربرد ماتريس‌هاي «وقوع» (Incidence) و «مجاورت» (Adjacency) |
موارد ذيل را مي‌توان نشان داد:
 زيرگراف (Subgraph)
يك گراف زيرگراف ناميده و به‌صورت: .gif) نوشته مي‌شود اگر داشته باشيم:
زيرگراف ويژه (Proper Subgraph)
زماني كه داشته باشيم:
| - | | - اما .gif) باشد، مي‌نويسيم: |
و چنين مي‌خوانيم:
| « يك زيرگراف ويژه از است». |
اگر يك زيرگراف از باشد يك «سوپرگراف» از يا «مافوق گراف» است.
«زيرگراف» يا «سوپرگراف» پوششي (Spanning Subgraph) (Spanning Supergraph)
زيرگراف يا سوپرگراف پوششي (Spanning Subgraph) (Spanning Supergraph) از ، يك زيرگراف (يا سوپرگراف يا مافوق گراف) از است كه در آن داريم:
(رابطه‌ي 18)
گراف ساده‌ي ضمني (Underlying Simple Graph)
با حذف همه‌ي حلقه‌هاي گراف براي هر زوج رؤوس مجاور - به‌گونه‌اي كه يك اتصال بين رؤوس موجود باشد – يك گراف «ساده‌ي ضمني» (Underlying Simple Graph) به‌دست خواهد آمد (شكل 4).
| شكل 17 – يك گراف و گراف
«ساده‌ي ضمني» (Underlying Simple Graph).
| 
| شكل 18 – گراف . | | 
| شكل 19 – يك زيرگراف پوششي از . | | 
| شكل 20 - .gif) . | | 
| شكل 21 - .gif) . | | .gif)
| شكل 22 – يك زيرگراف القايي
(Induced Subgraph). | | .gif) | شكل 23 – زيرگراف القايي لبه‌دار
(The Edge-Induced Subgraph)
.gif) . |
زيرگراف القايي (Induced Subgraph)
فرض كنيد .gif) يك زيرمجموعه‌ي غيرتهي از باشد. زيرگراف كه مجموعه‌ي رؤوسش بوده و مجموعه يال‌هايش مجموعه‌ي يال‌هاي گراف باشد به‌گونه‌اي كه يال‌هايش داراي دو سر در مجموعه رؤوس باشد اصطلاحاً زيرگرافي از ناميده مي‌شود كه با القا شده است و اين‌گونه نشان داده مي‌شود:
زيرگراف القايي .gif) به‌صورت ذيل نشان داده مي‌شود:
زيرگراف القايي عبارت است از زيرگرافي كه با حذف رؤوس در همراه با يال‌هاي وقوع آن از گراف به‌دست مي‌آيد.
اگر .gif) براي .gif) مي‌نويسيم:
اكنون فرض كنيد .gif) يك زيرمجموعه‌ي ناتهي از .gif) باشد. زيرگراف كه مجموعه‌ي رؤوس آن مجموعه‌ي انتهاي يال‌ها در باشد اصطلاحاً زيرگراف ناميده مي‌شود كه با القا شده و به‌صورت ذيل نوشته مي‌شود:
زيرگراف پوششي از گراف با مجموعه يال‌هاي .gif) به‌صورت ساده‌ي ذيل نوشته مي‌شود:
زيرگراف پوششي از گراف زيرگرافي است كه با حذف يال‌ها در از گراف به‌دست مي‌آيد. به‌طور مشابه، گراف به‌دست آمده از با اضافه كردن يك مجموعه يال به‌صورت ذيل نوشته مي‌شود:
اگر داشته باشيم: .gif) ، به‌جاي به‌ترتيب .gif) و .gif) مي‌نويسيم: .gif) و .gif) . در شكل‌هاي 5، 6، 7، 8، 9 و 10 چند نوع زيرگراف نشان داده شده است.
زيرگراف «منفصل» (Disjoint Subgraph)
فرض كنيد .gif) و .gif) زيرگراف‌هاي باشند. مي‌گوييم:
اجتماع زيرگراف‌ها (Union)
اجتماع زيرگراف‌هاي و - كه به‌صورت ذيل نوشته مي‌شود: .gif) - زيرگرافي است با:
| - مجموعه رؤوس: .gif)
| | - و مجموعه يال‌هاي: .gif) . |
اگر و «منفصل» باشند گاهي اوقات اجتماع آن‌ها را به‌صورت: .gif) نشان مي‌دهند.
فصل مشترك زيرگراف‌ها (Intersection)
فصل مشترك زيرگراف‌هاي و - كه به‌صورت ذيل نوشته مي‌شود: .gif) - زيرگرافي است با:
| - مجموعه رؤوس: .gif)
| | - و مجموعه يال‌هاي: .gif) . |
اما در اين حالت زيرگراف‌هاي و بايد داراي حداقل يك رأس مشترك باشند.
| مواردي كاربردي از زيرگراف‌ها (Subgraphs) |
مي‌توان موارد ذيل را در مورد زيرگراف‌ها اثبات كرد: | - هر گراف «ساده» (Simple) با رأس نسبت به زيرگراف .gif) «يكريخت» است.
| | - هر زيرگراف «القايي» (Induced) از يك گراف «كامل» (Complete)، گرافي «كامل» است.
| | - هر زيرگرافي از يك گراف «دوبخشي» (Bipartite) خود گرافي «دوبخشي» است.
| | - فرض كنيم گراف گرافي «ساده» بوده و عددي صحيح باشد به‌طوري كه داشته باشيم:
(رابطه‌ي 19) در اين صورت اگر .gif) باشد و همه‌ي زيرگراف‌هاي القايي گراف بر روي رأس تعدادي مساوي يال داشته باشند در اين صورت يكي از گزاره‌هاي ذيل صحيح است:
(رابطه‌ي 20)
(رابطه‌ي 21)
|
درجه‌ي .gif) (يا .gif) ) يك رأس در گراف برابر تعداد يال‌هاي «وقوع» با است كه در آن هر «حلقه» شمارشگر دو رأس است. علايم .gif) و .gif) به‌ترتيب بيانگر «مينيمم درجه» و «ماكسيمم درجه‌ي» رؤوس گراف هستند. تعداد رؤوس گراف را با نشان داده و «مرتبه‌ي گراف» مي‌ناميم. به‌عنوان مثال: در شكل 10 «مرتبه‌ي» گراف عدد 5 است. تعداد يال‌هاي گراف را با نشان داده و «اندازه‌ي گراف» مي‌ناميم. به‌عنوان مثال: در شكل 10 «اندازه‌ي» گراف عدد 4 است.
| قضيه‌اي درباره‌ي درجه‌هاي رؤوس (Degree) |
مي‌توان قضيه‌ي ذيل را براي هر گراف نظير: ثابت كرد: | جمع درجه‌هاي همه‌ي رؤوس يك گراف با دو برابر تعداد يال‌ها آن برابر است.
(رابطه‌ي 22) |
از اين قضيه مي‌توان عبارت ذيل را نتيجه گرفت:
| در هر گراف، تعداد رؤوس با درجه‌ي «فرد» عددي «زوج» است. |
بر اين اساس مي‌توان تعريف‌هاي ذيل را ارائه داد:
| موارد كاربردي از «درجه‌هاي رؤوس» (Degree) |
مي‌توان موارد ذيل را نشان داد:
| مسيرها و همبندي (Paths and Connection) |
يك «گشت» (Walk) در گراف يك دنباله‌ي محدود و غيرتهي .gif) است كه عبارت‌هايش متناوباً يال و رأس باشد به‌گونه‌اي كه داشته باشيم:
بدين‌ترتيب گفته مي‌شود:
| - «گشت» .gif) از .gif) تا .gif) | | - يا «گشت» .gif) . |
هم‌چنين مي‌توان اصطلاح‌هاي ذيل را در ارتباط با «گشت» به‌كار برد:
| - رؤوس و به‌طور نسبي با عنوان «ابتدا» و «انتهاي» | | - .gif) با عنوان «رؤوس دروني» (Internal Vertices) | | - عدد صحيح .gif) با عنوان «طول گشت». |
اگر .gif) و .gif) «گشت‌هايي» باشند «گشت» .gif) با معكوس كردن به‌دست آمده و با .gif) مشخص مي‌شود.
«گشت» .gif) با الحاق و .gif) در .gif) به‌دست آمده و با .gif) نشان داده مي‌شود.
«بخشي» از «گشت» عبارت است از «گشتي» كه زيردنباله‌اي از .gif) شامل عبارت‌هاي پي‌درپي از «گشت» است. اصطلاحاً به آن بخش .gif) از «گشت» اطلاق مي‌شود. در يك گراف «ساده»، يك «گشت» .gif) با دنباله‌ي .gif) از رؤوسش مشخص مي‌شود. علاوه بر آن حتي در گراف‌هايي كه «ساده» محسوب نمي‌شوند گاهي اوقات بايد به دنباله‌اي از رؤوس استناد كنيم كه عبارت‌هاي پي‌درپي آن به‌عنوان يك «گشت» مجاور هستند. در چنين حالت‌هايي فهميده مي‌شود كه بحث براي هر «گشتي» با رؤوس پي‌درپي صادق است.
.gif)
| شكل 31 - «گشت» (uavfyfvgyhwbv)،
«گذر» (wcxdyhwbvgy)
«مسير» (xcwhyeuav). |
اگر علاوه بر آن، رؤوس .gif) «مجزا» باشند «مسير» (Path) ناميده مي‌شود (شكل 16). ياداوري – از اصطلاح «مسير» (Path) هم‌چنين براي گراف يا زيرگرافي استفاده مي‌شود كه يال‌ها و رؤوسش برحسب يك «مسير» هستند.
.gif)
| شكل 32 – يك گراف همبند. | | .gif)
| شكل 33 – يك گراف غيرهمبند با سه جزو. | | .gif)
| شكل 34 - يك گراف غيرهمبند با سه جزو. |
دو رأس و از گراف «همبند» (Connected) گفته مي‌شود اگر يك مسير .gif) در گراف وجود داشته باشد. همبندي رابطه‌ي هم‌ارزي در مجموعه رؤوس است. بنابراين شرط لازم و كافي براي آن‌كه بخشي از مجموعه رؤوس به زيرمجموعه‌ي غيرتهي .gif) وجود داشته باشد آن است كه هر دو رأس و به يك مجموعه تعلق داشته باشد. زيرگراف‌هاي .gif) «اجزاي» (Components) گراف ناميده مي‌شوند. اگر گراف داراي دقيقاً يك «جزو» (Component) باشد گراف «همبند» (Connected) است. در غير اين‌صورت، گراف «غيرهمبند» (Disconnected) خواهد بود. تعداد اجزاي گراف با .gif) مشخص مي‌شود (اشكال 31، 32 و 33).
| كاربردهايي از مفاهيم مسيرها و همبندي (Paths and Connection) |
موارد ذيل را مي‌توان درباره‌ي مفاهيم مسيرها و همبندي اثبات كرد: |