همه ما با گراف‌ها کمابیش آشناییم، حتی اگر آشنا هم نباشم ساختار‌هایی که گراف نامیده می‌شوند رو دیدیم و شاید اسمشونو نمیدونیم، برای مثال تصویر زیر رو نگاه کنید. گراف زوج مرتبی از دو مجموعه‌ بنام راس‌ها(`vertex`) و یال‌ها(`edge`) هست، بطوری که هر یال معادل اتصال میان دو راس هست توی شکل زیر `{0, 1, 2}` مجموعه راس‌ها و `{a, b}` مجموعه یال‌ها هستند. هر یال نشان‌دهنده اتصال دو راس است. این تعریفی بود که اکثر ما از گراف‌ها توی ذهن خودمون داریم. گراف

یک گراف از مجموعه‌ای غیر خالی از اشیاء به نام رأس تشکیل شده، که آن را با V نشان می‌دهیم، و مجموعه‌ای شامل یال‌ها، که رأس‌ها را به هم وصل می‌کنند و با E نمایش می‌دهیم. یک چنین گرافی را با `G = (V,E) `نشان می‌دهیم. اگر یال y دو رأس v1 و v2 را به هم وصل کند می‌نویسیم `y = { v1,v2 }` "ویکیپدیا"

قراره اینجا مفهوم جدیدی رو باهم ببینیم به اسم ابرگراف‌ها یا `hypergraph`. برخلاف گراف‌های عادی که در اونها هر یال فقط دو راس رو بهم وصل میکنه، توی ابرگراف‌ها هر یال با به بیان بهتر هر ابریال(`hyperedge`) میتونه چند (تعداد دلخواه) راس رو به هم وصل بکنه، شکل زیر نشون دهنده یک ابرگراف است. (هر ابریال میتونه یک، دو، سه و یا بیشتر تعداد راس رو به هم متصل بکنه.) alt="ابرگراف" /> حال فرض کنید که ابرگرافی‌هایی وجود دارند که هر ابریالشون فقط میتونه دو راس رو به هم وصل بکنه، این ابرگراف‌ها همون گراف‌های دوست داشتنی خودمون هستند. یعنی گراف یک حالت خاص از ابرگراف محسوب میشه! برای نمایش ابرگراف‌ها از ماتریس تداخل استفاده میشه به این صورت که سطر‌ها مشخص کننده راس‌ها و ستون‌ها مشخص کننده ابریال‌های ابرگراف هستند، هر درایه `aij` از ماتریس برابر یک هست اگر راس `i` در ابریال `j` وجود داشته باشه. برای مثال اگر مجموعه راس‌ها برابر `{a, b, c}` و مجموعه ابریال‌ها برابر `{‌{a}, {a,b}, {a,c}, {a, b, c}}` باشه، گراف متناظر این ابر گراف به شکل زیر خواهد بود.

A=(100110101111)

ابرگراف‌ها چیز جدایی از گراف‌هایی که ما دیدیم نیستند، مفاهیمی که برای گراف‌ها داشتیم اینجا هم وجود داره، مفاهیمی مثل همبندی، دوبخشی‌بودن، `k-colorable`، منتظم بودن و ... اینجا چند تا از مفاهیم رو باهم میبینیم:

  • `k-uniform`: اگر تمامی ابریال‌های یک ابرگراف دقیقا `k` راس را به من متصل کنند، ابرگراف رو `k-uniform` میگیم
  • `k-regular`: اگر تمامی راس‌های یک ابرگراف دقیقا در `k` ابریال حضور داشته باشند اون ابرگراف رو `k-regular` میگیم.
  • ` Bipartite `: ابرگرافی رو دوبخشی می‌نامیم که بتونیم راس‌های اون رو طوری از در دو گروه قرار بدیم که هر یال حداق یک راس از هر گروه رو درون خودش داشته باشه.
  • `Dual`: اگر جای راس‌ها و ابریال‌های یک ابرگراف رو عوض کنی ابرگراف حاصل رو دوگان ابرگراف نخست می‌نامند.
    اگر به تعریف `k-uniform` و `k-regular` رو در نظر بگیریم متوجه میشیم که دوگان هر ابرگراف `k-uniform` یک ابرگراف `k-regular` خواهد بود و بر عکس.


* برای خود من مفهوم و ساختار ابرگراف‌ها جالب بودند برای همین خواستم معرفی کوتاه و جمع‌و‌جوری توی بلاگ ازشون بنویسم، اگر خواستید درمورد ابرگراف‌ها بیشتر بدونید میتونید به منابعی که در زیر نوشتم سری بزنید.