تعاریف و ویژگی‌های گراف

برای رسم شکل یک گراف روش یکتایی مدنظر نیست. آنچه مهم است این است که باید مشخص باشد که گراف مورد نظر چند رأس و چند یال دارد و کدام یال به کدام رئوس متصل است. برای مثال دو گراف رسم شده در واقع یک گراف هستند.

تعاریف

مرتبه گراف: تعداد رأس‌های گراف \(G\) یعنی \(\left|V(G)\right| \) که با \(p(G)\) یا \(p\) نمایش داده می‌شود.

اندازه گراف: تعداد یال‌های گراف یعنی\(\left|E(G)\right|\) که با \(q(G)\) یا \(q\) نمایش داده می‌شود.

درجه یک رأس: تعداد یال‌هایی که به رأس v متصل است که آن را با \(degG(v)\) یا \(deg(v)\) یا \(d(v) \) نمایش می‌دهیم.

رأس فرد: رأسی که درجه فرد دارد.

رأس زوج: رأسی که درجه زوج دارد.

گراف \(k\) منتظم: گرافی که درجه تمام رئوس آن با هم مشاوی و برابر با k باشند.

رأس تنها یا ایزوله: رأسی که درجه آن صفر باشد یعنی یالی به آن متصل نباشد.

گراف تهی: گرافی که تمام رئوس آن تنها هستند.

طوقه: یالی که رأسی را به خودش وصل کند.

در یک گراف می‌توان بین دو  رأس بیش از \(۱\) یال رسم کرد.

گراف ساده: گرافی که  جهت دار نباشد، دارای طوقه نباشد و بین دو رأس آن بیش از 1 یال نباشد.

دو رأس مجاور یا همسایه: دو رأس هنگامی با هم مجاور اند که با یالی به هم متصل شده باشند.

هیچ یالی نباید خودش را قطع کند و یا از روی رأسی که مربوط به دو سر آن یال نیست عبور کند.

همسایگی باز رأس \(v\): مجموعه ای شامل رئوسی که با رأس \(v\) همسایه هستند. همسایگی باز را با \(N_G(v) \) نمایش می‌دهیم.

همسایگی بسته رأس \(v\): مجموعه ای شامل رئوسی که با رأس \(v\) همسایه هستند و خود رأس \(v\). همسایگی بسته را با \(N_G\left[v\right]\) نمایش می‌دهیم.

دو یال مجاور: دو یال را مجاور گوییم هرگاه رأسی وجود داشته باشد که هر دوی آن‌ها به آن متصل باشند.