Топологический анализ связей и отношений

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

 

 

Петлей называется дуга, соединяющая вход и выход одной вершины графа и не содержащая других вершин.

 

 

Если несколько вершин ориентированного графа G соединены дугами таким образом, что, двигаясь в направлении ориентации этих дуг, можно перейти непрерывным образом из некоторой вершины i в некоторую другую вершину j, то говорят, что в графе G существует путь (пути), ведущий из вершины i в вершину j. Говорят также, что вершина j достижима из вершины i.

Понятие пути может быть распространено и на неориентированные графы. Частным случаем пути является дуга, соединяющая соседние вершины.

При топологическом описании структуры иногда вводится понятие об индексе пути. Индекс пути равен числу дуг, входящих в его состав, без учета петель. При метрическом описании структуры используется понятие длины пути. Длина пути равна сумме (произведению) весов (мер) составляющих его дуг без учета петель.

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

 

 

Окрестностью элемента ра­диуса 1 в структуре, описываемой некоторым графом G, называется множество соседних вершин, соответствующих данному элементу вершин.

Если граф G является ориентированным, то различают входную и выходную окрестности (окрестности входов и выходов).

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

Помимо радиуса, окрестность элемента может быть охарактеризована и ее объемом, т.е. числом входящих в нее вершин или суммой (произведением) весов последних.

Существуют также и дифференциальные характеристики окрестности элемента, дающие представление о составе и количестве вершин (элементов), индексы или длины путей до которых принадлежат определенному интервалу. Недаром же в житейской практике иногда говорят «ближний круг», «дальний круг» и т.д.

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

 

 

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

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

Сильносвязный подграф формально можно определить так:

Пусть – множество всех вершин графа, достижимый из вершины , а – множество всех вершин, из которых достижима вершина . Тогда подграф

(2.1.44)

будет сильносвязным, содержащим вершину .

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

 

Если каждый сильносвязный подграф графа заменить эквивалентной ему в смысле внешних связей его вершин вершиной, то полученный в результате выполнения этой процедуры эквивалентный (в смысле оставшихся связей) граф называется конденсатом исходного графа.

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

 

?

Вопросы и упражнения

1. Дайте определение понятия морфология.

2. Дайте определение понятия структура.

3. Охарактеризуйте основные способы описания структур экономических и социально-политических систем. Приведите примеры.

4. Охарактеризуйте основные типы структуры дискретных систем.

5. Объясните смысл топологического элементного анализа.

6. Для приведенных матриц инциденций определите висячие, внутренние, тупиковые и изолированные вершины:

; ;

7. Для приведенных матриц смежности постройте соответствующие им графы структур:

; ;

Охарактеризуйте основные морфологические особенности связей и отношений.

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

 

 

 

9. Оцените связности графов, заданных приведенными ниже матрицами смежности, нарисуйте графы, соответствующие указанным матрицам:

;

2.2