ابرگراف

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
e1 = {v1, v4} e2 = {v5, v6, v7} e3 = {v3, v6} e4 = {v3, v4, v8, v9}
Hypergraph-wikipedia

در ریاضیات اَبَر‌گراف تعمیمی از گراف است که برخلاف گراف‌های عادی هر یال در آن، که به آن اَبریال می‌گویند، می‌تواند شامل تعداد دلخواهی از رأس‌ها باشد و چندین رأس را به هم وصل کند. اَبر‌گراف را به صورت نشان می‌دهند که مجموعه‌ای از رأس‌ها و مجموعه‌ای از زیرمجموعه‌های غیر تهی رأس‌ها یا همان یال‌ها می باشد.

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

تعریف[ویرایش]

اگر یک مجموعه متناهی و (به قسمی که i Є I) یک خانواده از زیرمجموعه‌های X باشند ، را یک ابر‌گراف می‌نامند اگر اجتماع تمامی های ناتهی برابر X شود.

و و ... و را رأسها و و و ... و را اَبریالهای اَبرگراف است.

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

تعداد ابریال هایی که رأس در آن قرار دارد درجه رأس گویند و با نمایش می‌دهند.

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

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

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

نمایش[ویرایش]

در حالت خاص اگر فرض کنیم در مجموعه ها رابطه‌ی ترتیبی وجود داشته باشد را یک گره را یک یال بین دو رأس و را به وسیله ی منحنی بسته ای که تمام رأس های را دربر دارد نشان می دهند.

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