ГИПЕРГРАФ это:

ГИПЕРГРАФ

- обобщение понятия графа. Г. задается множеством V, элементы к-рого наз. вершинами, и семейством подмножеств множества V, называемых ребрами Г.; Г. обозначается Понятие Г. является вариантом давно известных понятий комплекса, блок-схемы, а также понятия сети.

Две вершины и Г. наз. смежными, если существует ребро, содержащее эти вершины. Вершина и ребро Е Т. наз. инцидентными, если Г. Нс пвершинами и требрами можно задать матрицей инцидентности, т. е. матрицей размера , в к-рой столбцы соответствуют ребрам, а строки - вершинам Г. и


Всякой прямоугольной матрице Миз нулей и единиц можно сопоставить Г., для к-рого Мявляется матрицей инцидентности. Г. наз. двойственным по отношению к Г. Н, если матрица инцидентности Г. получается транспонированием матрицы инцидентности Г. Н. Число ребер Г., инцидентных данной вершине, наз. степенью вершины.

Степенью ребра наз. число вершин Г., инцидентных этому ребру. Г. наз.

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


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

Многие понятия теории графов, такие, как связность, планарность, хроматин, число, числа внутренней и внешней устойчивости, переносятся и на Г. На Г. переносятся также многие утверждения, справедливые для графов.

Лит.:[1] Зыков А. А., "Успехи матем. наук", 1974, т. 29, в. 6, с. 89-154; [2] Веrge С., Graphes et hypergraphes, р 1970 А. А. Сапоженко.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Синонимы:

Смотреть что такое "ГИПЕРГРАФ" в других словарях:

  • гиперграф — сущ., кол во синонимов: 1 • граф (9) Словарь синонимов ASIS. В.Н. Тришин. 2013 …   Словарь синонимов

  • Гиперграф — Пример гиперграфа: , . Гиперграф  обобщённый вид графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества в …   Википедия

  • МАТРОИД — гиперграф специального вида. М. определяется заданием множества Vэлементов и семейства подмножеств множества У, называемых независимыми множествами, для к рых выполняются следующие аксиомы: 1) пустое множество независимо; 2) каждое подмножество… …   Математическая энциклопедия

  • СЕТЬ — обобщение понятия графа. С. задается парой вида , в к рой V нек рое множество, семейство наборов элементов из V. В наборах элементы могут, вообще говоря, повторяться. Элементы множества Vназ. вершинами С., элементы набора Е 0 полюсами С., наборы… …   Математическая энциклопедия

  • Стек — Простое представление стека У этого термина существуют и другие значения, см. Стек (значения). Стек (англ. stack  стоп …   Википедия

  • Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф  это совокупность непустого множества вершин и множества пар… …   Википедия

  • Очередь (программирование) — У этого термина существуют и другие значения, см. Очередь. Очередь  структура данных с дисциплиной доступа к элементам «первый пришёл  первый вышел» (FIFO, First In  First Out). Добавление элемента (принято обозначать словом… …   Википедия

  • Ассоциативный массив — (словарь)  абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу: INSERT(ключ, значение) FIND(ключ)… …   Википедия

  • Теория графов — Граф с шестью вершинами и семью рёбрами Теория графов  раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строго …   Википедия

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»