999
правок
Иерархический граф: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 8: | Строка 8: | ||
Граф <math>C</math> называется ''[[Фрагмент|фрагментом]]'' ([[Fragment|''fragment'')]] графа <math>G</math>, обозначаем <math>C\subseteq G</math>, если <math>C</math> --- [[Часть графа|часть]] графа <math>G</math>, т. е. <math>C</math> образован подмножеством элементов графа <math>G</math>. | Граф <math>C</math> называется ''[[Фрагмент|фрагментом]]'' ([[Fragment|''fragment'')]] графа <math>G</math>, обозначаем <math>C\subseteq G</math>, если <math>C</math> --- [[Часть графа|часть]] графа <math>G</math>, т. е. <math>C</math> образован подмножеством элементов графа <math>G</math>. | ||
<math>F</math> --- [[Иерархия фрагментов|''иерархия фрагментов'']] ( | <math>F</math> --- [[Иерархия фрагментов|''иерархия фрагментов'']] (или ''иерархия вложенных фрагментов'') графа <math>G</math>, если <math>F</math> --- такое множество фрагментов графа <math>C</math>, что <math>G\in F</math> и для любых двух фрагментов <math>C_1</math> и <math>C_2</math> из <math>F</math> | ||
либо фрагменты <math>C_1</math> и <math>C_2</math> не пересекаются, либо один из | либо фрагменты <math>C_1</math> и <math>C_2</math> не пересекаются, либо один из | ||
них является частью ( ''подфрагментом'') ( ''subfragment'') другого. Фрагмент | них является частью ( ''подфрагментом'') ( ''subfragment'') другого. Фрагмент | ||
<math>G</math> --- [[Основной фрагмент|''основной'']] | <math>G</math> --- [[Основной фрагмент|''основной'']] фрагмент иерархии | ||
<math>F</math>. Фрагмент <math>C \in F</math> --- [[Элементарный фрагмент|''элементарный'']] | <math>F</math>. Фрагмент <math>C \in F</math> --- [[Элементарный фрагмент|''элементарный'']], если в <math>F</math> | ||
нет фрагментов <math>G</math>, являющихся подфрагментами фрагмента <math>C</math>. | нет фрагментов <math>G</math>, являющихся подфрагментами фрагмента <math>C</math>. | ||
Пусть задана некоторая иерархия фрагментов <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> --- [[прямой подфрагмент|''прямой подфрагмент'']] <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>. | ||
| Строка 23: | Строка 23: | ||
корневого дерева <math>T</math>, вершины которого соответствуют элементам | корневого дерева <math>T</math>, вершины которого соответствуют элементам | ||
некоторой иерархии в <math>G</math>, а дуги отражают отношение их | некоторой иерархии в <math>G</math>, а дуги отражают отношение их | ||
непосредственной вложенности. <math>T</math> называется [[Дерево вложенности|''деревом вложенности'']] | непосредственной вложенности. <math>T</math> называется [[Дерево вложенности|''деревом вложенности'']], а <math>G</math> --- [[Основной граф|''основным графом'']] иерархического графа | ||
<math>H</math>. | <math>H</math>. | ||
| Строка 29: | Строка 29: | ||
максимальное поддерево дерева <math>T</math> с корнем <math>p</math>, а через <math>G(p)</math> | максимальное поддерево дерева <math>T</math> с корнем <math>p</math>, а через <math>G(p)</math> | ||
--- фрагмент основного графа <math>G</math>, соответствующий <math>p</math>. | --- фрагмент основного графа <math>G</math>, соответствующий <math>p</math>. | ||
Иерархический граф <math>H (p) = (G(p), T(p))</math> называется [[Иерархический подграф|''иерархическим подграфом'']] | Иерархический граф <math>H (p) = (G(p), T(p))</math> называется [[Иерархический подграф|''иерархическим подграфом'']] графа | ||
<math>H</math>, ассоциированным с вершиной | <math>H</math>, ассоциированным с вершиной | ||
<math>p</math>. | <math>p</math>. | ||
| Строка 44: | Строка 44: | ||
образуют такие <math>H = (G,T)</math>, | образуют такие <math>H = (G,T)</math>, | ||
что каждая вершина дерева вложенности <math>T</math> соответствует | что каждая вершина дерева вложенности <math>T</math> соответствует | ||
некоторому порожденному подграфу (induced subgraph) основного графа <math>G</math>. Такие графы будем называть ''[[Простой иерархический граф|простыми]]'' | некоторому порожденному подграфу (induced subgraph) основного графа <math>G</math>. Такие графы будем называть ''[[Простой иерархический граф|простыми]]'' иерархическими графами. Поскольку порожденные подграфы однозначно определяются множествами своих вершин, | ||
есть возможность определять простой иерархический граф <math>H</math> | есть возможность определять простой иерархический граф <math>H</math> | ||
как пару <math>(G,T)</math>, состоящую из основного графа <math>G</math> и | как пару <math>(G,T)</math>, состоящую из основного графа <math>G</math> и | ||
| Строка 55: | Строка 55: | ||
непосредственную вложенность соответствующих подмножеств. | непосредственную вложенность соответствующих подмножеств. | ||
Такое представление иерархического графа будем называть | Такое представление иерархического графа будем называть | ||
''[[Вершинный иерархический граф|вершинным]]'' | ''[[Вершинный иерархический граф|вершинным]]''. | ||
''[[Кластерный граф]]'' | ''[[Кластерный граф]]'' --- это простой вершинный иерархический граф с неориентированным основным графом. | ||
== Литература == | == Литература == | ||