ابرگراف

e1 = {v1, v4} e2 = {v5, v6, v7} e3 = {v3, v6} e4 = {v3, v4, v8, v9}

Hypergraph-wikipedia

در ریاضیات اَبَرگراف تعمیمی از گراف است که برخلاف گراف‌های عادی هر یال در آن، که به آن اَبریال می‌گویند، می‌تواند شامل تعداد دلخواهی از رأس‌ها باشد و چندین رأس را به هم وصل کند. اَبرگراف ${\displaystyle H}$ را به صورت ${\displaystyle H=(X,E)}$ نشان می‌دهند که ${\displaystyle X}$ مجموعه‌ای از رأس‌ها و ${\displaystyle E}$ مجموعه‌ای از زیرمجموعه‌های غیر تهی رأس‌ها یا همان یال‌ها می‌باشد.

از نیم قرن گذشته، نظریه گراف دارای اهمیت بسیاری در زمینه‌های مختلف از جمله هندسه، نظریه اعداد، بهینه‌سازی، توپولوژی، جبرهای میانی و نظیر آن‌ها بوده‌است. برای حل مسایل ترکیبیاتی جدید، لازم بود که مفهوم گراف توسعه داده شود. حدود سال١٩۶٠مفهوم ابرگراف پدیدار شد و یکی از اهداف ابتدایی آن، تعمیم برخی از نتایج کلاسیک نظریه گراف بود. نظریه ابرگراف، ابزاری مفید برای مسایل بهینه‌سازی گسسته است.

تعریف

اگر${\displaystyle X=\lbrace x_{1},x_{2},...,x_{n}\rbrace }$ یک مجموعه متناهی و ${\displaystyle X=\lbrace c_{i}\rbrace }$ (به قسمی که i Є I) یک خانواده از زیرمجموعه‌های X باشند ، ${\displaystyle H=(X,E)}$ را یک ابرگراف می‌نامند اگر اجتماع تمامی ${\displaystyle c_{i}}$های ناتهی برابر X شود.

${\displaystyle x_{1}}$ و ${\displaystyle x_{2}}$ و ... و ${\displaystyle x_{n}}$ را رأسها و ${\displaystyle c_{1}}$ و ${\displaystyle c_{2}}$ و ... و ${\displaystyle c_{m}}$را اَبریالهای اَبرگراف است.

${\displaystyle |X|=n}$ را مرتبه‌ی ابرگراف و مجموع ${\displaystyle c_{i}}$ها اندازه‌ی ابرگراف می نامند.

تعداد ابریال‌هایی که رأس ${\displaystyle x_{i}}$ در آن قرار دارد درجه رأس ${\displaystyle x_{i}}$ گویند و با ${\displaystyle deg(v_{i})}$ نمایش می‌دهند.

اندازه بزرگترین ابریال در هر ابرگراف را رتبه ابرگراف گویند و با ${\displaystyle Rank(H)}$ نمایش می‌دهند.

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

دو ابریال را مجزا گویند هرگاه اشتراکشان تهی باشد.

نمایش

در حالت خاص اگر فرض کنیم در مجموعه ${\displaystyle c_{i}}$ها رابطهٔ ترتیبی وجود داشته باشد ${\displaystyle |c_{i}|=1}$ را یک گره ${\displaystyle |c_{i}|=2}$ را یک یال بین دو رأس و ${\displaystyle |c_{i}|>2}$ را به وسیلهٔ منحنی بسته‌ای که تمام رأس‌های ${\displaystyle c_{i}}$ را دربر دارد نشان می دهند.

برای نمایش ابرگراف‌ها از ماتریس تداخل استفاده می‌شود به این صورت که سطرها مشخص‌کننده رأس‌ها و ستون‌ها مشخص‌کننده ابریال‌های ابرگراف هستند، هر درایه ${\displaystyle aij}$ از ماتریس برابر یک هست اگر راس i در ابریال j وجود داشته باشد.

ابرگراف k-یکنواخت

ابرگراف H را k-یکنواخت گویند هرگاه همه ابریالهای آن دقیقاً دارای K عضو باشد.

منابع

• "Results in Extremal Graph and Hypergraph Theory" (به انگلیسی).
• Hypergraphes. Combinatoires des ensembles finis (Hypergraphs. Combinatorial finite sets), Gauthier-Villars, 1987, trans. English
• Graphes et Hypergraphes, in 1969 and 1970, trans. in English, Japanese. English translation: Graphs and Hypergraphs, North-Holland Publishing Company, 1973.