نمایش مبدأ برای ابرگراف

[[پرونده:اَبرگراف.gif|بندانگشتی|e1 = {v1, v4} e2 = {v5, v6, v7} e3 = {v3, v6} e4 = {v3, v4, v8, v9}]]
[[پرونده:Hypergraph-wikipedia.svg|بندانگشتی|Hypergraph-wikipedia]]

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

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

== تعریف ==
اگر<math>X = \lbrace x_1,x_2,...,x_n \rbrace</math> یک مجموعه متناهی و <math>X = \lbrace  c_i  \rbrace</math> (به قسمی که i Є I)  یک خانواده از زیرمجموعه‌های X باشند ، <math>H = (X,E)</math> را یک ابرگراف می‌نامند اگر اجتماع تمامی <math>c_i</math>های ناتهی  برابر X شود.

<math>x_1</math> و <math>x_2</math> و ... و <math>x_n</math> را '''رأسها''' و <math>c_1</math> و <math>c_2</math> و ... و <math>c_m</math>را '''اَبریالهای''' اَبرگراف است. 

<math>|X| = n</math> را '''مرتبه‌ی''' ابرگراف و مجموع <math>c_i</math>ها '''اندازه‌ی''' ابرگراف می نامند.

تعداد ابریال‌هایی که رأس <math>x_i</math> در آن قرار دارد '''درجه''' رأس <math>x_i</math> گویند و با <math>deg(v_i)</math> نمایش می‌دهند.

اندازه بزرگترین ابریال در هر ابرگراف را '''رتبه''' ابرگراف گویند و با <math>Rank(H)</math> نمایش می‌دهند.

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

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

== نمایش ==
در حالت خاص اگر فرض کنیم در [[مجموعه (ریاضی)|مجموعه]] <math>c_i</math>ها رابطهٔ ترتیبی وجود داشته باشد <math>|c_i| = 1</math> را یک گره  <math>|c_i| = 2</math> را یک یال بین دو رأس و <math>|c_i| > 2</math> را به وسیلهٔ منحنی بسته‌ای که تمام رأس‌های <math>c_i</math> را دربر دارد نشان می دهند.

برای نمایش ابرگراف‌ها از ماتریس تداخل استفاده می‌شود به این صورت که سطرها مشخص‌کننده رأس‌ها و ستون‌ها مشخص‌کننده ابریال‌های ابرگراف هستند، هر درایه <math>aij</math>  از ماتریس برابر یک هست اگر راس i در ابریال j وجود داشته باشد.

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

== منابع ==
{{پانویس}}
* {{یادکرد وب| نشانی = http://repository.cmu.edu/cgi/viewcontent.cgi?article=1052&context=dissertations| عنوان = 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.

{{ویکی‌گفتاورد با عنوان|گراف}}
{{پانویس-نظریه گراف}}
{{ساختارهای وقوع}}
[[رده:خانواده مجموعه‌ها]]
[[رده:نظریه گراف]]