999
правок
Иерархический граф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 16: | Строка 16: | ||
Пусть задана некоторая иерархия фрагментов <math>F</math> графа <math>G</math>. | Пусть задана некоторая иерархия фрагментов <math>F</math> графа <math>G</math>. | ||
Для любых <math>C_1, C_2 \in F</math> фрагмент <math>C_1</math> --- [[ | Для любых <math>C_1, C_2 \in F</math> фрагмент <math>C_1</math> --- [[прямой подфрагмент]] ([[immediate subfragment]]) <math>C_2</math> (или, что то же самое, фрагмент, [[непосредственно вложенный]] (immediately included) в <math>C_2</math>),если <math>C_1</math> --- подфрагмент <math>C_2</math> и не существует такого | ||
подфрагмент]] ([[immediate subfragment]]) <math>C_2</math> (или, что то же самое, фрагмент, непосредственно вложенный в <math>C_2</math>),если <math>C_1</math> --- подфрагмент <math>C_2</math> и не существует такого | |||
<math>C_3 \in F</math>, отличного от <math>C_1</math> и <math>C_2</math>,что | <math>C_3 \in F</math>, отличного от <math>C_1</math> и <math>C_2</math>,что | ||
<math>C_1\subseteq C_3\subseteq C_2</math>. | <math>C_1\subseteq C_3\subseteq C_2</math>. | ||
'''Иерархический граф''' (''[[hierarchical graph]]'') <math>H = (G,T)</math> состоит из графа <math>G</math> и | '''Иерархический граф''' (''[[hierarchical graph]]'') <math>H = (G,T)</math> состоит из графа <math>G</math> и | ||
| Строка 47: | Строка 44: | ||
образуют такие <math>H = (G,T)</math>, | образуют такие <math>H = (G,T)</math>, | ||
что каждая вершина дерева вложенности <math>T</math> соответствует | что каждая вершина дерева вложенности <math>T</math> соответствует | ||
некоторому порожденному подграфу (induced subgraph) основного графа <math>G</math>. Такие графы будем называть ''[[Простой иерархический граф|простыми]]'' (''[[Simple hierarchical graph|simple]]'') иерархическими графами. Поскольку | некоторому порожденному подграфу (induced subgraph) основного графа <math>G</math>. Такие графы будем называть ''[[Простой иерархический граф|простыми]]'' (''[[Simple hierarchical graph|simple]]'') иерархическими графами. Поскольку подграфы однозначно определяются множествами своих вершин, | ||
подграфы однозначно определяются множествами своих вершин, | |||
есть возможность определять простой иерархический граф <math>H</math> | есть возможность определять простой иерархический граф <math>H</math> | ||
как пару <math>(G,T)</math>, состоящую из основного графа <math>G</math> и | как пару <math>(G,T)</math>, состоящую из основного графа <math>G</math> и | ||
| Строка 59: | Строка 55: | ||
непосредственную вложенность соответствующих подмножеств. | непосредственную вложенность соответствующих подмножеств. | ||
Такое представление иерархического графа будем называть | Такое представление иерархического графа будем называть | ||
вершинным. | ''[[Вершинный иерархический граф|вершинным]]'' (''[[Apex hierarchical graph|apex]]''). | ||
''[[Кластерный граф]]'' (''[[clustered graph]]'') --- это простой вершинный иерархический граф с неориентированным основным графом. | ''[[Кластерный граф]]'' (''[[clustered graph]]'') --- это простой вершинный иерархический граф с неориентированным основным графом. | ||