Хиперграф

У математици, хиперграф представља генерализацију графа, где гране графа могу да повезују било који број чворова. Формално, хиперграф је пар $(X,E)$ где је $X$ скуп елемената, чворова, а $E$ је скуп подскупова од $X$, који се називају хипергране. Гране графа су представљене паровима чворова које оне спајају, док су хипергране произвољни скупови чворова, који стога могу да садрже произвољан број чворова.

Пример хиперграфа са $X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$ и $E=\{e_{1},e_{2},e_{3},e_{4}\}=$ $\{\{v_{1},v_{2},v_{3}\},$ $\{v_{2},v_{3}\},$ $\{v_{3},v_{5},v_{6}\},$ $\{v_{4}\}\}$. Овде гране не повезују само два чвора већ више њих, и представљене су бојама.

Хиперграф се такође назива системом скупа или фамилијом скупова извучених из универзалног скупа X. Хиперграфови се могу посматрати као инцидентне структуре, и обратно.

Многе теореме које се тичу графова су примењиве и на хиперграфове. Ремзијева теорема је типичан пример. Неке методе за проучавање симетрија графова се могу проширити на хиперграфове. На пример, хомоморфизам хиперграфова је пресликавање из скупа чворова једног хиперграфа у други, такво да се свака грана пресликава у другу грану. Изоморфизам хиперграфова је инверзибилни хомоморфизам. Аутоморфизам хиперграфова је изоморфизам једног скупа чворова у самог себе, то јест, преименовање чворова.

За разлику од графова, хиперграфове је тешко нацртати на папиру, тако да се они обично изучавају помоћу номенклатуре теорије скупова пре него коришћењем визуелних приказа (попут 'дрвета', 'шума' или 'циклова') из теорије графова.