Расширения модели

Модель графа при описании конкретных объектов, процессов или явлений может быть расширена. Для этого используют следующие способы:

- Взвешивание дуг (ребер). Каждому ребру (дуге) графа приписывается число – вес дуги (ребра). Вес может определять, например, расстояние между городами, если вершинам приписаны имена городов, а ребра – дороги между ними. Для описания взвешенного графа используется матрица смежности, в ячейках которой записаны веса.

- Взвешивание вершин. Аналогично дугам веса приписываются вершинам. Например, вершинами представлены магазины и склады, а вес вершины определяет количество некоторого товара на складе или в магазине.

- Взвешивание дуг и/или вершин векторами. Взвешивание производится не числом, а набором чисел. Например, для дороги могут быть указаны расстояние, стоимость проезда, время в пути и т.д.

- В графе допускается между двумя вершинами несколько «параллельных» дуг (или рёбер). В этом случае говорят о кратных дугах (рёбрах), а такие графы называют мультиграфами. Для описания мультиграфов используются такие же таблицы, как и для простых графов, но в клетках записаны не 0 и 1, а кратность дуги.

- В графе используется не бинарное, а r -арное отношение, где r > 2. Такие графы называются гиперграфами. Для представления этих графов на плоскости вершины, которые относятся к одному ребру, объединяются замкнутыми линиями, как на рис. 2.3. Здесь граф имеет три ребра: (1, 2, 3), (1, 2, 4), (4, 5, 6). К таким графам приходят при описании логических сетей, когда элементы находятся в отношении, если они имеют полюса, связанные общей цепью.

Рис. 2.3.

Дата добавления: 2014-01-07