انواع گراف
=============
در این قسمت یسری گراف های معروف و شناخته شده رو براتون لیست کردیم.
قبل از اینکه با آن ها آشنا شویم به این نکته توجه کنید که در این قسمت هرجا صحبت از
n
شده منظور تعداد راس های گراف بوده است.
آشنایی با این گراف ها به شما کمک می کند تا با گراف ها بیشتر انس بگیرید و هم چنین
در ادامه بعضا در تمارین و درس نامه و
یا حتی متون دیگر گراف به این گراف ها اشاره می شود و از توضیحشان
صرف نظر می شود. هر گاه که تعریف یکی از این گراف ها یادتان رفت می توانید
به این صفحه برگردید و آن را مرور کنید.

گراف کامل
-----------
به گراف G که به ازای هر دو راس u و v یک یال بینشون وجود داشته باشه گراف کامل می گوییم که آن را با 
:math:`K_n` نشان می دهند.

.. figure:: /_static/complete_graph.jpg
   :width: 90%
   :align: center
   :alt: complete graph

گراف تهی
----------
به گراف G که در آن هیچ یالی وجود ندارد گویند. در واقع گراف تهی مکمل گراف کامل است که آن را با 
:math:`\overline{K_n}` نشان می دهند.

.. figure:: /_static/empty_graph.png
   :width: 100%
   :align: center
   :alt: empty graph

گراف مسیر
----------
به گراف G که در آن تعداد یال ها n - 1 و درجه راس ها حداکثر ۲ باشد گویند.
گراف مسیر را با 
:math:`P_n` نشان می دهند.

.. figure:: /_static/path_graph.png
   :width: 70%
   :align: center
   :alt: path graph

گراف دور
----------
به گراف G که در آن درجه تمامی راس ها ۲ است و می توان با پیمودن چند یال از هر راسی به راس دیگری رفت.
گراف دور را با 
:math:`C_n` نشان می دهند.

.. figure:: /_static/cycle_graph.png
   :width: 100%
   :align: center
   :alt: cycle graph


گراف منتظم
------------
به گرافی که درجه تمامی رئوسش برابر باشد، گراف متنظم می گوییم. اگر درجه تمامی رئوس برابر و برابر با k باشد به آن گراف k-منتظم می گوییم.

.. figure:: /_static/regular_graphs.png
   :width: 100%
   :align: center
   :alt: regular graph

گراف پیترسن ( Petersen )
--------------------------
در این بخش بر خلاف بخش های دیگر که گراف های زیادی رو شامل میشدن، فقط یک گراف را شامل می شود.
نحوه ساخت گراف :


یک مجموعه ۵ عضوی در نظر بگیرید و به ازای هر زیرمجموعه ۳ عضوی آن یک راس در گراف قرار می دهیم.
بین دو راس یال قرار می دهیم اگر و تنها اگر دو مجموعه متناظر آنها دقیقا در یک عضو مشترک باشند.


گراف پیترسن ۱۰ راس و ۱۵ یال دارد که درجه هر راس آن ۳ است.

.. figure:: /_static/petersen_graph.png
   :width: 80%
   :align: center
   :alt: Petersen graph

گراف k بخشی
-------------
به گرافی که بتوان راس های آن را به k بخش تقسیم کرد به طوری که به ازای هر دو راس u و v در یک بخش، به هم یال نداشته باشند.

.. figure:: /_static/dot/K_2_2_2.svg
   :width: 50%
   :align: center
   :alt: complete multipartite graph

به کوچک ترین
k
ای که گراف
k بخشی
باشد، عدد رنگی آن گراف می گویند و آن را با حرف یونانی خی به صورت
:math:`\chi`
یا
:math:`\chi (G)`
نمایش می دهند.

گراف k بخشی کامل
------------------
همانند گراف k بخشی که در بخش قبل تعریف شد می باشد با این تفاوت کرد که بین هر دو راس
u و v
که در یک بخش نیستند، یال وجود دارد. گراف های
k بخشی کامل را به صورت
:math:`K_{a_1,a_2,...,a_k}`
نمایش می دهند. برای مثال گراف
:math:`K_{a,b,c}`
یک گراف سه بخشی کامل است که بخش های آن
a و b و c
راس و در کل
:math:`a+b+c`
راس دارد.

گراف
:math:`K_{3,5}`

.. figure:: /_static/dot/K_3_5.svg
   :width: 60%
   :align: center
   :alt: complete multipartite graph

گراف
:math:`K_{2,2,2}`

.. figure:: /_static/dot/K_2_2_2.svg
   :width: 60%
   :align: center
   :alt: complete multipartite graph

گراف ستاره ( Star )
---------------------
به گراف G که یک راس u به تمامی راس های دیگر یال دارد و راس های دیگر فقط به
u
یال دارند، استار گویند.
گراف استار چون حالت خاصی از گراف دو بخشی کامل است، به شکل
:math:`K_{1,n}`
نمایش داده می شود که
:math:`n`
یال و
:math:`n+1`
راس دارد.

.. figure:: /_static/star_graph.png
   :width: 100%
   :align: center
   :alt: star graph

گراف مکعب k بعدی (Cube)
-------------------------
تمام رشته باینری های به اندازه k را در نظر بگیرید. هر راس گراف را متناظر با یکی از این رشته ها می کنیم به طوری که هر رشته دقیقا یک بار متناظر شده باشد.
حال بین دو راس یال می گذاریم اگر و تنها اگر در رشته های متناظرشون دقیقا در یک رقم تفاوت داشته باشند.
برای مثال اگر k = 3 باشد گراف به شکل زیر می شود.

.. figure:: /_static/dot/Q_3.svg
   :width: 50%
   :align: center
   :alt: hypercube

این گراف ها را به صورت 
:math:`Q_k` نشان می دهند.
:math:`Q_1`
شبیه یک خط و
:math:`Q_2`
شبیه یک مربع و
:math:`Q_3`
شبیه یک مکعب است. گراف
:math:`Q_k`
را می توان با دو کپی از
:math:`Q_{k-1}`
و قرار دادن یال بین رئوس متناظر این دو، ایجاد کرد. این خاصیت می تواند
به اثبات خاصیت های این گراف کمک کند. اگر کد باینری را به عنوان مختصات
k بعدی
در نظر بگیرید، گراف
:math:`Q_k`
تشکیل یک مکعب
k بعدی
به حجم (به معنای تعمیم یافته آن) واحد می دهد که کنج آن منطبق
با محور های مختصات است.