انواع گراف¶

گراف کامل¶

به گراف G که به ازای هر دو راس u و v یک یال بینشون وجود داشته باشه گراف کامل می گوییم که آن را با \(K_n\) نشان می دهند.

گراف تهی¶

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

گراف مسیر¶

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

گراف دور¶

به گراف G که در آن درجه تمامی راس ها ۲ است و می توان با پیمودن چند یال از هر راسی به راس دیگری رفت. گراف دور را با \(C_n\) نشان می دهند.

گراف منتظم¶

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

گراف پیترسن ( Petersen )¶

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

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

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

گراف k بخشی¶

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

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

گراف k بخشی کامل¶

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

گراف \(K_{3,5}\)

گراف \(K_{2,2,2}\)

گراف ستاره ( Star )¶

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

گراف مکعب k بعدی (Cube)¶

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

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