گراف: رأس، یال و درجه

گراف یعنی چند نقطه و چند خط (یا منحنی) که بعضی از نقطه‌ها را به هم وصل می‌کنند. به هر نقطه «رأس» و به هر خط «یال» می‌گوییم. گراف مدلی است برای چیزهایی که به هم مربوط‌اند، مثل آدم‌ها و دوستی‌هایشان یا شهرها و جاده‌هایشان.

«درجهٔ» یک رأس تعداد یال‌هایی است که به آن وصل‌اند. اگر درجه فرد باشد، آن را «رأس فرد» و اگر زوج باشد «رأس زوج» می‌نامیم. تعداد رأس‌ها «مرتبه» و تعداد یال‌ها «اندازهٔ» گراف است.

در این کارگاه گراف‌ها «ساده»‌اند: بین هر دو رأس حداکثر یک یال هست و هیچ یالی رأسی را به خودش وصل نمی‌کند. رأس‌ها مثل کتاب درسی با حرف‌های لاتین نام‌گذاری شده‌اند. روی رأس‌ها بزن تا انتخاب شوند؛ برای برداشتن انتخاب، دوباره روی رأس بزن.