Геометрические графы

НЕОРИЕНТИРОВАНЫЕ ГРАФЫ

Комплексный показатель качества

Сравнение различных объектов по некоторой числовой характеристике сводится, как об этом говорилось в (4), к упорядочению множества соответствующих им весов, которые можно рассматривать как некоторый показатель качества. Сложный объект характеризуется несколькими показателями качества (стоимость, надежность и т.п.). Для оценки таких объектов используется комплексный показатель качества, который выражается некоторым числом. Простейший способ определения этого числа основан на соотношении, где a _i - коэффициент весомости показателя. Обычно под понимают относительные показатели по сравнению с соответствующими показателями некоторого объекта, принятого в качестве базисного. Коэффициенты весомости являются численными выражениями значимости показателей, и их определение находится в компетенции специалистов конкретной отрасли.

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

Обозначим n -мерное евклидово пространство через Rⁿ. Евклидово n -мерное пространство есть множество последовательностей из n действительных чисел, в котором расстояние между любыми двумя точками и определено следующим образом:

Простой незамкнутой кривой в пространстве Rⁿ называется непрерывная, самонепересекающаяся кривая, соединяющая две различные точки в Rⁿ (т.е. кривая, получаемая непрерывной деформацией прямолинейного отрезка).

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

Геометрический граф в пространстве Rⁿ есть множество V = { v_i } точек пространства Rⁿ и множество E = { e _i } простых кривых, удовлетворяющих следующим условиям.

1. Каждая замкнутая кривая в E содержит только одну точку v из множества V.

2. Каждая незамкнутая кривая в E содержит ровно две точки множества V, которые являются ее граничными точками.

3. Кривые в E не имеют общих точек, за исключением точек из множества V.

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

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

Обычная форма представления геометрического графа показана на рисунке 6.1. С позиции теории графов элементы v и e называются геометрическими вершинами и геометрическими ребрами соответственно. Хотя многие графы, представляющие реальные объекты (после их идеализации), являются геометрическими графами, с точки зрения теории графов их единственная структурная особенность состоит в том, что с каждым геометрическим ребром связаны две (возможно совпадающие) геометрические вершины. Теория графов построена с учетом именно этой особенности и не учитывает реальной природы вершин и ребер. Таким образом, перечисление вершин и связанных с ними ребер содержит всю информацию, необходимую для описания геометрического графа.

Рис. 6.1 – Пример геометрического графа