Взвешенный неориентированный граф

ВНГ это граф вида , где E – множество вершин графа, соответствующих множеству элементов схемы; U – множество ребер графа, при этом каждое ребро взвешено некоторым числом , определяющим степень связности элементов e_i и e_j. Другими словами, c_ij – количество общих цепей, связывающих элементы e_i и e_j.

ВНГ для схемы примера (рис. 2.1) показан на рисунке 2.4.

Рис. 2.4

ВНГ описывается с помощью матрицы смежности C.

Для схемы рис. 2.1 матрицы смежности C имеет вид:

Часто вместо матрицы C используют матрицу C', которая отличается от C тем, что каждый диагональный элемент в ней не равен нулю, а равен числу цепей, инцидентных соответствующему элементу.

Недостаток модели ВНГ – она является грубой и, чаще всего, используется в задачах размещения разногабаритных модулей.

Поиск по сайту: