Гиперграф

- обобщение понятия графа. Г. задается множеством V, элементы к-рого наз. вершинами, и семейством [img: http://localhost:8080/file/010418-125.jpg] подмножеств множества V, называемых ребрами Г.; Г. обозначается [img: http://localhost:8080/file/010418-126.jpg] Понятие Г. является вариантом давно известных понятий комплекса, блок-схемы, а также понятия сети. Две вершины [img: http://localhost:8080/file/010418-127.jpg] и [img: http://localhost:8080/file/010418-128.jpg] Г. наз. смежными, если существует ребро, содержащее эти вершины. Вершина [img: http://localhost:8080/file/010418-129.jpg] и ребро Е Т. наз. инцидентными, если [img: http://localhost:8080/file/010418-130.jpg] Г. Нс пвершинами и требрами можно задать матрицей инцидентности, т. е. матрицей [img: http://localhost:8080/file/010418-131.jpg] размера [img: http://localhost:8080/file/010418-132.jpg], в к-рой столбцы соответствуют ребрам, а строки - вершинам Г. и [img: http://localhost:8080/file/010418-133.jpg] Всякой прямоугольной матрице Миз нулей и единиц можно сопоставить Г., для к-рого Мявляется матрицей инцидентности. Г. [img: http://localhost:8080/file/010418-134.jpg] наз. двойственным по отношению к Г. Н, если матрица инцидентности Г. [img: http://localhost:8080/file/010418-135.jpg] получается транспонированием матрицы инцидентности Г. Н. Число ребер Г., инцидентных данной вершине, наз. степенью вершины. [img: http://localhost:8080/file/010418-137.jpg] Степенью ребра наз. число вершин Г., инцидентных этому ребру. Г. [img: http://localhost:8080/file/010418-136.jpg] наз. подгиперграфом Г. [img: http://localhost:8080/file/010418-138.jpg], если [img: http://localhost:8080/file/010418-139.jpg] и вершина [img: http://localhost:8080/file/010418-140.jpg] из [img: http://localhost:8080/file/010418-141.jpg] и ребро [img: http://localhost:8080/file/010418-142.jpg] из [img: http://localhost:8080/file/010418-143.jpg] инцидентны в Г. [img: http://localhost:8080/file/010418-144.jpg] тогда и только тогда, когда они инцидентны в Г. [img: http://localhost:8080/file/010418-145.jpg] Г. можно изобразить на плоскости, сопоставляя вершинам Г. точки плоскости, а ребрам - связные области, охватывающие вершины, инцидентные этим ребрам. Напр., Г. H с множеством вершин [img: http://localhost:8080/file/010418-146.jpg] и семейством ребер [img: http://localhost:8080/file/010418-147.jpg] можно изобразить на плоскости, как показано на рис. Г. Нможно представлять графом двудольным К (Н), в к-ром вершины одной доли [img: http://localhost:8080/file/010418-148.jpg] соответствуют вершинам Г., а вершины другой доли [img: http://localhost:8080/file/010418-149.jpg] - ребрам Г. Н. При этом две вершины [img: http://localhost:8080/file/010418-150.jpg] из [img: http://localhost:8080/file/010418-151.jpg] и [img: http://localhost:8080/file/010418-152.jpg] из [img: http://localhost:8080/file/010418-153.jpg] соединены в графе К(Н).ребром, если вершина Г., соответствующая вершине [img: http://localhost:8080/file/010418-154.jpg], инцидентна ребру Г., соответствующему вершине [img: http://localhost:8080/file/010418-155.jpg]. Г. является графом, если каждое ребро его имеет степень, равную 2. Важным частным случаем понятия "Г." является матроид. Многие понятия теории графов, такие, как связность, планарность, хроматин, число, числа внутренней и внешней устойчивости, переносятся и на Г. На Г. переносятся также многие утверждения, справедливые для графов.