ابرگراف

در ریاضیات اَبَرگراف تعمیمی از گراف است که برخلاف گراف های عادی هر یال در آن، که به آن اَبریال می گویند، می تواند شامل تعداد دلخواهی از رأس ها باشد و چندین رأس را به هم وصل کند. اَبرگراف H را به صورت H = ( X , E ) نشان می دهند که X مجموعه ای از رأس ها و E مجموعه ای از زیرمجموعه های غیر تهی رأس ها یا همان یال ها می باشد.
از نیم قرن گذشته، نظریه گراف دارای اهمیت بسیاری در زمینه های مختلف از جمله هندسه، نظریه اعداد، بهینه سازی، توپولوژی، جبرهای میانی و نظیر آن ها بوده است. برای حل مسایل ترکیبیاتی جدید، لازم بود که مفهوم گراف توسعه داده شود. حدود سال١٩۶٠مفهوم ابرگراف پدیدار شد و یکی از اهداف ابتدایی آن، تعمیم برخی از نتایج کلاسیک نظریه گراف بود. نظریه ابرگراف، ابزاری مفید برای مسایل بهینه سازی گسسته است.
اگر X = { x 1 , x 2 , . . . , x n } یک مجموعه متناهی و X = { c i } ( به قسمی که 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 گویند و با d e g ( v i ) نمایش می دهند.
اندازه بزرگترین ابریال در هر ابرگراف را رتبه ابرگراف گویند و با R a n k ( H ) نمایش می دهند.
دو رأس را مجاور گویند هرگاه ابریالی موجود باشد که شامل هر دو رأس باشد.
دو ابریال را مجزا گویند هرگاه اشتراکشان تهی باشد.
در حالت خاص اگر فرض کنیم در مجموعه c i ها رابطهٔ ترتیبی وجود داشته باشد | c i | = 1 را یک گره | c i | = 2 را یک یال بین دو رأس و | c i | > 2 را به وسیلهٔ منحنی بسته ای که تمام رأس های c i را دربر دارد نشان می دهند.
برای نمایش ابرگراف ها از ماتریس تداخل استفاده می شود به این صورت که سطرها مشخص کننده رأس ها و ستون ها مشخص کننده ابریال های ابرگراف هستند، هر درایه a i j از ماتریس برابر یک هست اگر راس i در ابریال j وجود داشته باشد.
ابرگراف H را k - یکنواخت گویند هرگاه همه ابریالهای آن دقیقاً دارای K عضو باشد.