Аноним

Иерархический граф: различия между версиями

Материал из WikiGrapp

Иерархический граф (посмотреть исходный код)

Версия от 02:07, 9 ноября 2024

2 байта добавлено ,  9 ноября 2024
нет описания правки
Нет описания правки
Нет описания правки
 
(не показано 5 промежуточных версий этого же участника)
Строка 4: Строка 4:
например: <math>G</math>
например: <math>G</math>
может быть [[Обыкновенный граф|обыкновенным графом]], [[Орграф|орграфом]] (ориентированным графом),
может быть [[Обыкновенный граф|обыкновенным графом]], [[Орграф|орграфом]] (ориентированным графом),
[[Мультиграф|мультиграфом]] (с кратными ребрами) или [[Псевдограф|псевдографом]] (с петлями).
[[Мультиграф|мультиграфом]] или [[Гиперграф|гиперграфом]].


Граф <math>C</math> называется ''[[Фрагмент|фрагментом]]'' ([[Fragment|''fragment'')]] графа <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>C\subseteq G</math>, если <math>C</math> --- [[Часть графа|часть]] графа <math>G</math>, т. е. <math>C</math> образован подмножеством элементов графа <math>G</math>.


<math>F</math> --- [[Иерархия фрагментов|''иерархия фрагментов'']] ([[Hierarchy of nested fragments|''hierarchy of nested fragments'']])
<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>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> --- [[Основной фрагмент|''основной'']] (''[[Main fragment|main]]'') фрагмент иерархии
<math>G</math> --- [[Основной фрагмент|''основной'']] фрагмент иерархии
<math>F</math>. Фрагмент <math>C \in F</math> --- [[Элементарный фрагмент|''элементарный'']] ([[Simple fragment|simple]]), если в <math>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_2</math> (или, что то же самое, фрагмент, [[Непосредственно вложенный фрагмент|непосредственно вложенный]] в <math>C_2</math>),если <math>C_1</math> --- подфрагмент <math>C_2</math> и не существует такого
Для любых <math>C_1, C_2 \in F</math> фрагмент <math>C_1</math> --- [[Прямой подфрагмент|прямой
подфрагмент]] ([[proper 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> и
корневого дерева <math>T</math>, вершины которого соответствуют элементам
корневого дерева <math>T</math>, вершины которого соответствуют элементам
некоторой иерархии в <math>G</math>, а дуги отражают отношение их
некоторой иерархии в <math>G</math>, а дуги отражают отношение их
непосредственной вложенности. <math>T</math> называется [[Дерево вложенности|''деревом вложенности'']] ([[Inclusion tree|''inclusion tree'']]), а <math>G</math> --- [[Основной граф|''основным графом'']] (''[[underlying graph]]'') иерархического графа
непосредственной вложенности. <math>T</math> называется [[Дерево вложенности|''деревом вложенности'']], а <math>G</math> --- [[Основной граф|''основным графом'']] иерархического графа
<math>H</math>.
<math>H</math>.


Строка 36: Строка 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> называется [[Иерархический подграф|иерархическим подграфом]] (''[[hierarchical subgraph]]'') графа
Иерархический граф <math>H (p) = (G(p), T(p))</math> называется [[Иерархический подграф|''иерархическим подграфом'']] графа
<math>H</math>, ассоциированным с вершиной
<math>H</math>, ассоциированным с вершиной
<math>p</math>.
<math>p</math>.
Строка 51: Строка 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>. Такие графы будем называть ''[[Простой иерархический граф|простыми]]'' иерархическими графами. Поскольку порожденные подграфы однозначно определяются множествами своих вершин,
подграфы однозначно определяются множествами своих вершин,
есть возможность определять простой иерархический граф <math>H</math>
есть возможность определять простой иерархический граф <math>H</math>
как пару <math>(G,T)</math>, состоящую из основного графа <math>G</math> и  
как пару <math>(G,T)</math>, состоящую из основного графа <math>G</math> и  
Строка 63: Строка 55:
непосредственную вложенность соответствующих подмножеств.
непосредственную вложенность соответствующих подмножеств.
Такое представление иерархического графа будем называть  
Такое представление иерархического графа будем называть  
вершинным.  
''[[Вершинный иерархический граф|вершинным]]''.  


''[[Кластерный граф]]'' (''[[clustered graph]]'') --- это простой вершинный иерархический граф с неориентированным основным графом.
''[[Кластерный граф]]'' --- это простой вершинный иерархический граф с неориентированным основным графом.


== Литература ==
== Литература ==
Строка 74: Строка 66:


[[Категория:Визуализация графов]]
[[Категория:Визуализация графов]]
[[Категория:Потоковый анализ программ]]
[[Категория:Преобразование программ]]
Источник — http://pco.iis.nsk.su/grapp/index.php/Служебная:Сравнение_версий/11290...11414