Page 76 - Сборник трудов научно-исследовательских работ студентов МАИ

вершинами графа, элементы множества X — его ребрами
[3].
Гиперграф — обобщение (чаще всего
неориентированного) графа, когда ребрами могут служить
произвольные, а не только двухвершинные и
одновершинные, подмножества заданного множества
вершин [4].
Гиперграфом Н называется пара = ( , ), где X —
множество элементов, называемых узлами или вершинами,
а E — множество непустых подмножеств X, называемых
гиперребрами или просто ребрами гиперграфа [5].
Говорят, что ребро = { , , … , } инцидентно
2

1
каждой из вершин гиперграфа , , … , , а каждая из этих

2
1
вершин гиперграфа инцидентна ребру е.
Матрица инцидентности. Пусть G – граф, вершины
которого пронумерованы числами от 1 до n, а ребра —
числами от 1 до m. В матрице инцидентности строки
соответствуют вершинам, а столбцы — ребрам. На
пересечении строки с номером i и столбца с номером j стоит
1, если вершина с номерами i инцидентна ребру с номером
j, и 0 в противном случае [3]. Представление графа
матрицей инцидентности упрощает работу с ним с
вычислительной точки зрения.
Например: для графа изображенного на рисунке 1
матрицей инцидентности будет матрица, изображенная на
рисунке 2.

76