ابرگراف: تعمیم گراف‌ها و کاربردهای آن

ابرگراف چیست؟

در دنیای ریاضیات، ابرگراف (Hypergraph) تعمیمی از مفهوم گراف است. تفاوت اصلی در این است که در یک ابرگراف، یک یال (edge یا hyperedge) می‌تواند به هر تعداد رأس (vertex یا node) متصل شود، در حالی که در گراف معمولی، هر یال دقیقاً به دو رأس متصل است.

تعریف رسمی ابرگراف

یک ابرگراف جهت‌دار به صورت زوج مرتب H = (V, E) تعریف می‌شود، که در آن:

• V مجموعه‌ای از عناصر است که به آن‌ها رأس، گره، نقطه یا عنصر گفته می‌شود.
• E مجموعه‌ای از زوج‌ها است که هر زوج، زیرمجموعه‌ای از V است. هر یک از این زوج‌ها e = (V_tail, V_head) یک یال یا ابر یال نامیده می‌شود. V_tail دم یا دامنه و V_head سر یا هم‌دامنه آن است.

مرتبه (Order) یک ابرگراف، تعداد رأس‌های آن است. اندازه (Size) ابرگراف، تعداد یال‌های آن است. مرتبه یک یال e در ابرگراف جهت‌دار به صورت |V_tail| + |V_head| تعریف می‌شود.

ابرگراف‌های یک‌سویه و چندسویه

ابرگراف‌های یک‌سویه (Undirected Hypergraphs) حالتی خاص از ابرگراف‌های جهت‌دار هستند که در آن‌ها مجموعه یال‌ها متقارن است. یعنی اگر یال e رأس‌های V_tail را به V_head متصل کند، یال دیگری وجود دارد که V_head را به V_tail متصل می‌کند.

یک‌نواختی (Uniformity) در ابرگراف‌ها

اغلب، مطالعه ابرگراف‌ها زمانی مفید است که تمام ابر یال‌ها اندازه یکسانی داشته باشند. در این حالت، ابرگراف k-uniform نامیده می‌شود، به این معنی که هر ابر یال دقیقاً شامل k رأس است. به عنوان مثال:

• یک ابرگراف 2-uniform همان گراف معمولی است.
• یک ابرگراف 3-uniform مجموعه‌ای از سه‌تایی‌های مرتب نشده است.

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

ارتباط با ساختارهای دیگر

ابرگراف‌ها را می‌توان به عنوان ساختارهای هم‌رخدادی (Incidence Structures) نیز در نظر گرفت. هر ابرگراف یک گراف هم‌رخدادی (Incidence Graph) یا گراف لوی (Levi Graph) دو بخشی متناظر دارد و بالعکس، هر گراف دو بخشی را می‌توان به عنوان گراف هم‌رخدادی یک ابرگراف در نظر گرفت.

نام‌های دیگر و کاربردها

ابرگراف‌ها در حوزه‌های مختلف با نام‌های گوناگونی شناخته می‌شوند:

• هندسه محاسباتی: فضای بازه (Range Space) نامیده می‌شوند و ابر یال‌ها بازه (Ranges) هستند.
• نظریه بازی‌های مشارکتی: بازی‌های ساده (Simple Games) یا بازی‌های رأی‌دهی (Voting Games) نامیده می‌شوند.
• یادگیری ماشین: به طور گسترده‌ای برای مدل‌سازی داده‌ها و منظم‌سازی طبقه‌بندها (classifiers) استفاده می‌شوند. کاربردها شامل سیستم‌های توصیه‌گر، بازیابی تصویر و بیوانفورماتیک است.
• علوم کامپیوتر: در مدل‌سازی پایگاه‌های داده، مسائل رضایت‌پذیری (Satisfiability Problems) و مسائل درخت اشتاینر (Steiner Tree Problems) کاربرد دارند.
• کاربرد در سیستم‌های مخابراتی، کشف پولشویی، تحقیق در عملیات و برنامه‌ریزی حمل و نقل نیز از دیگر زمینه‌های استفاده از ابرگراف‌های جهت‌دار است.

تعمیم مفاهیم گراف به ابرگراف

بسیاری از قضایا و مفاهیم مرتبط با گراف‌ها، برای ابرگراف‌ها نیز صادق هستند، از جمله:

• تطابق (Matching)
• پوشش رأس (Vertex Cover)
• گراف خطی (Line Graph)
• قضیه رمزی (Ramsey's Theorem)
• قضیه اردوش-کو-رادو (Erdős–Ko–Rado theorem)
• قضیه کروسکال-کاتونا (Kruskal–Katona theorem)
• قضایای نوع هال (Hall-type theorems)

در ابرگراف‌های جهت‌دار، مفاهیمی مانند بستار ترایایی (Transitive Closure) و مسائل کوتاه‌ترین مسیر نیز قابل تعمیم هستند.

ترسیم ابرگراف

ترسیم ابرگراف‌ها پیچیده‌تر از گراف‌های معمولی است. روش‌های مختلفی برای بصری‌سازی آن‌ها وجود دارد:

• روش مبتنی بر درخت: رأس‌ها به صورت نقاط و ابر یال‌ها به صورت درخت‌هایی با رأس‌های برگ نمایش داده می‌شوند.
• روش مبتنی بر تقسیم‌بندی (Subdivision Model): صفحه به نواحی تقسیم می‌شود که هر ناحیه نمایانگر یک رأس است و ابر یال‌ها به صورت زیرمجموعه‌های پیوسته از این نواحی نمایش داده می‌شوند (مثلاً با رنگ‌آمیزی). نمودار ون (Venn Diagram) مثالی از این روش است.

رنگ‌آمیزی ابرگراف

رنگ‌آمیزی کلاسیک ابرگراف شامل تخصیص رنگ به هر رأس به گونه‌ای است که هیچ ابر یالی (با اندازه حداقل 2) تک‌رنگ نباشد. حداقل تعداد رنگ‌های متمایز مورد استفاده، عدد کروماتیک (Chromatic Number) ابرگراف نامیده می‌شود. ابرگراف‌های 2-رنگ‌پذیر دقیقاً همان ابرگراف‌های دو بخشی (Bipartite) هستند.

ویژگی‌های ابرگراف

ابرگراف‌ها می‌توانند ویژگی‌های متنوعی داشته باشند:

• خالی (Empty): بدون یال.
• غیرساده (Non-simple): دارای حلقه‌ها (یال‌هایی با یک رأس) یا یال‌های تکراری.
• ساده (Simple): بدون حلقه و یال تکراری.
• k-یکنواخت (k-uniform): هر یال دقیقاً k رأس دارد.
• k-بخشی (k-partite): رأس‌ها به k بخش تقسیم شده‌اند و هر یال دقیقاً یک رأس از هر بخش دارد.
• بسته نزولی (Downward-closed): هر زیرمجموعه‌ای از یال‌های یک ابرگراف، خود یک ابر یال است (این‌ها مجتمع‌های سیمپلکسی مجرد (Abstract Simplicial Complexes) نامیده می‌شوند).

ابرگراف‌های مرتبط

مفاهیمی مانند زیرابرگراف (Subhypergraph)، ابرگراف جزئی (Partial Hypergraph) و ابرگراف مقطعی (Section Hypergraph) برای ابرگراف‌ها تعریف می‌شوند.

ماتریس هم‌رخدادی (Incidence Matrix)

هر ابرگراف با یک ماتریس هم‌رخدادی |V| × |E| نمایش داده می‌شود که نشان‌دهنده ارتباط بین رأس‌ها و یال‌ها است.

ماتریس مجاورت (Adjacency Matrix)

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

چرخه‌ها (Cycles)

برخلاف گراف‌های معمولی، چندین تعریف معادل برای چرخه‌ها و گراف‌های بدون چرخه در ابرگراف‌ها وجود دارد، از جمله:

• چرخه برژ (Berge-cyclic): بر اساس گراف هم‌رخدادی.
• α-acyclicity: مرتبط با گراف اولیه و الگوریتم GYO.
• β-acyclicity و γ-acyclicity: تعاریف قوی‌تر که خواص مطلوب‌تری را تضمین می‌کنند.

هم‌ریختی، تقارن و برابری

مفاهیمی مانند هم‌ریختی ابرگراف (Hypergraph Homomorphism)، هم‌ریختی (Isomorphism)، هم‌ریختی قوی (Strong Isomorphism)، هم‌ارزی (Equivalence) و برابری (Equality) برای ابرگراف‌ها تعریف می‌شوند. گروه خودریختی (Automorphism Group) نیز برای ابرگراف‌ها تعریف می‌شود.

تقارن

رتبه (Rank) یک ابرگراف، حداکثر اندازه یال‌های آن است. اگر همه یال‌ها اندازه یکسانی داشته باشند، ابرگراف یکنواخت نامیده می‌شود. درجه (Degree) یک رأس، تعداد یال‌هایی است که شامل آن رأس هستند.

تقارن رأس (Vertex-transitive) و تقارن یال (Edge-transitive) مفاهیمی هستند که به وجود خودریختی‌هایی اشاره دارند که رأس‌ها یا یال‌ها را جابجا می‌کنند.

تعمیم‌های بیشتر

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