ابرگراف

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

Hypergraph-wikipedia

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

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

تعریف

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

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

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

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

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

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

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

نمایش

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

برای نمایش ابرگراف‌ها از ماتریس تداخل استفاده می‌شود به این صورت که سطرها مشخص‌کننده رأس‌ها و ستون‌ها مشخص‌کننده ابریال‌های ابرگراف هستند، هر درایه $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.