Гиперграф

- обобщение понятия графа. Г. Задается множеством V, элементы к-рого наз. Вершинами, и семейством подмножеств множества V, называемых ребрами Г. Г. Обозначается Понятие Г. Является вариантом давно известных понятий комплекса, блок-схемы, а также понятия сети. Две вершины и Г. Наз. Смежными, если существует ребро, содержащее эти вершины. Вершина и ребро Е Т. Наз. Инцидентными, если Г. Нс пвершинами и требрами можно задать матрицей инцидентности, т. Е. Матрицей размера , в к-рой столбцы соответствуют ребрам, а строки - вершинам Г. И Всякой прямоугольной матрице Миз нулей и единиц можно сопоставить Г., для к-рого Мявляется матрицей инцидентности. Г. наз. Двойственным по отношению к Г. Н, если матрица инцидентности Г.

получается транспонированием матрицы инцидентности Г. Н. Число ребер Г., инцидентных данной вершине, наз. Степенью вершины. Степенью ребра наз. Число вершин Г., инцидентных этому ребру. Г. наз. подгиперграфом Г. , если и вершина из и ребро из инцидентны в Г. Тогда и только тогда, когда они инцидентны в Г. Г. Можно изобразить на плоскости, сопоставляя вершинам Г. Точки плоскости, а ребрам - связные области, охватывающие вершины, инцидентные этим ребрам. Напр., Г. H с множеством вершин и семейством ребер можно изобразить на плоскости, как показано на рис. Г. Нможно представлять графом двудольным К (Н), в к-ром вершины одной доли соответствуют вершинам Г., а вершины другой доли - ребрам Г. Н. При этом две вершины из и из соединены в графе К(Н).ребром, если вершина Г., соответствующая вершине , инцидентна ребру Г., соответствующему вершине .

Г. Является графом, если каждое ребро его имеет степень, равную 2. Важным частным случаем понятия "Г." является матроид. Многие понятия теории графов, такие, как связность, планарность, хроматин, число, числа внутренней и внешней устойчивости, переносятся и на Г. На Г. Переносятся также многие утверждения, справедливые для графов. Лит.:[1] Зыков А. А., "Успехи матем. Наук", 1974, т. 29, в. 6, с. 89-154. [2] Веrge С., Graphes et hypergraphes, р 1970 А. А. Сапоженко.