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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 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> --- [[Иерархия фрагментов|''иерархия фрагментов'']] ([[Hierarchy of nested fragments|''hierarchy of nested fragments'']]) графа <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>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> --- [[прямой подфрагмент|''прямой подфрагмент'']] ([[immediate subfragment|''immediate subfragment'']]) <math>C_2</math> (или, что то же самое, фрагмент, [[Непосредственно вложенный фрагмент|непосредственно вложенный]] (immediately included) в <math>C_2</math>),если <math>C_1</math> --- подфрагмент <math>C_2</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> называется [[Дерево вложенности|''деревом вложенности'']] ([[Inclusion tree|''inclusion tree'']]), а <math>G</math> --- [[Основной граф|''основным графом'']] (''[[underlying graph]]'') иерархического графа
непосредственной вложенности. <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> называется [[Иерархический подграф|''иерархическим подграфом'']] (''[[hierarchical subgraph]]'') графа
Иерархический граф <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>. Такие графы будем называть ''[[Простой иерархический граф|простыми]]'' (''[[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> и  
Строка 55: Строка 55:
непосредственную вложенность соответствующих подмножеств.
непосредственную вложенность соответствующих подмножеств.
Такое представление иерархического графа будем называть  
Такое представление иерархического графа будем называть  
''[[Вершинный иерархический граф|вершинным]]'' (''[[Apex hierarchical graph|apex]]'').  
''[[Вершинный иерархический граф|вершинным]]''.  


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


== Литература ==
== Литература ==

Текущая версия от 20:42, 4 ноября 2024

Пусть [math]\displaystyle{ G }[/math] обозначает граф произвольного вида, элементы (вершины и ребра) которого отличаются один от другого какими-либо пометками, называемыми их именами, например: [math]\displaystyle{ G }[/math] может быть обыкновенным графом, орграфом (ориентированным графом), мультиграфом или гиперграфом.

Граф [math]\displaystyle{ C }[/math] называется фрагментом (fragment) графа [math]\displaystyle{ G }[/math], обозначаем [math]\displaystyle{ C\subseteq G }[/math], если [math]\displaystyle{ C }[/math] --- часть графа [math]\displaystyle{ G }[/math], т. е. [math]\displaystyle{ C }[/math] образован подмножеством элементов графа [math]\displaystyle{ G }[/math].

[math]\displaystyle{ F }[/math] --- иерархия фрагментов (или иерархия вложенных фрагментов) графа [math]\displaystyle{ G }[/math], если [math]\displaystyle{ F }[/math] --- такое множество фрагментов графа [math]\displaystyle{ C }[/math], что [math]\displaystyle{ G\in F }[/math] и для любых двух фрагментов [math]\displaystyle{ C_1 }[/math] и [math]\displaystyle{ C_2 }[/math] из [math]\displaystyle{ F }[/math] либо фрагменты [math]\displaystyle{ C_1 }[/math] и [math]\displaystyle{ C_2 }[/math] не пересекаются, либо один из них является частью ( подфрагментом) ( subfragment) другого. Фрагмент [math]\displaystyle{ G }[/math] --- основной фрагмент иерархии [math]\displaystyle{ F }[/math]. Фрагмент [math]\displaystyle{ C \in F }[/math] --- элементарный, если в [math]\displaystyle{ F }[/math] нет фрагментов [math]\displaystyle{ G }[/math], являющихся подфрагментами фрагмента [math]\displaystyle{ C }[/math].

Пусть задана некоторая иерархия фрагментов [math]\displaystyle{ F }[/math] графа [math]\displaystyle{ G }[/math]. Для любых [math]\displaystyle{ C_1, C_2 \in F }[/math] фрагмент [math]\displaystyle{ C_1 }[/math] --- прямой подфрагмент [math]\displaystyle{ C_2 }[/math] (или, что то же самое, фрагмент, непосредственно вложенный в [math]\displaystyle{ C_2 }[/math]),если [math]\displaystyle{ C_1 }[/math] --- подфрагмент [math]\displaystyle{ C_2 }[/math] и не существует такого [math]\displaystyle{ C_3 \in F }[/math], отличного от [math]\displaystyle{ C_1 }[/math] и [math]\displaystyle{ C_2 }[/math],что [math]\displaystyle{ C_1\subseteq C_3\subseteq C_2 }[/math].

Иерархический граф (hierarchical graph) [math]\displaystyle{ H = (G,T) }[/math] состоит из графа [math]\displaystyle{ G }[/math] и корневого дерева [math]\displaystyle{ T }[/math], вершины которого соответствуют элементам некоторой иерархии в [math]\displaystyle{ G }[/math], а дуги отражают отношение их непосредственной вложенности. [math]\displaystyle{ T }[/math] называется деревом вложенности, а [math]\displaystyle{ G }[/math] --- основным графом иерархического графа [math]\displaystyle{ H }[/math].

Для любой вершины [math]\displaystyle{ p }[/math] дерева [math]\displaystyle{ T }[/math] через [math]\displaystyle{ T(p) }[/math] обозначается максимальное поддерево дерева [math]\displaystyle{ T }[/math] с корнем [math]\displaystyle{ p }[/math], а через [math]\displaystyle{ G(p) }[/math] --- фрагмент основного графа [math]\displaystyle{ G }[/math], соответствующий [math]\displaystyle{ p }[/math]. Иерархический граф [math]\displaystyle{ H (p) = (G(p), T(p)) }[/math] называется иерархическим подграфом графа [math]\displaystyle{ H }[/math], ассоциированным с вершиной [math]\displaystyle{ p }[/math].

Граф [math]\displaystyle{ H= (G,T) }[/math] называется связным, если для любой вершины [math]\displaystyle{ p }[/math] дерева [math]\displaystyle{ T }[/math] фрагмент [math]\displaystyle{ G(p) }[/math] основного графа [math]\displaystyle{ G }[/math], соответствующий [math]\displaystyle{ p }[/math], является связным.

Пусть [math]\displaystyle{ H_1=(G_1,T_1) }[/math] и [math]\displaystyle{ H_2=(G_2,T_2) }[/math] --- два иерархических графа. [math]\displaystyle{ H_1 }[/math] называется подграфом [math]\displaystyle{ H_2 }[/math], если [math]\displaystyle{ T_1 }[/math] --- поддерево дерева [math]\displaystyle{ T_2 }[/math] и для любой вершины [math]\displaystyle{ p }[/math] из [math]\displaystyle{ T_1 }[/math] граф [math]\displaystyle{ G_1(p) }[/math] --- часть графа [math]\displaystyle{ G_2(p) }[/math].

Важный частный случай иерархических графов образуют такие [math]\displaystyle{ H = (G,T) }[/math], что каждая вершина дерева вложенности [math]\displaystyle{ T }[/math] соответствует некоторому порожденному подграфу (induced subgraph) основного графа [math]\displaystyle{ G }[/math]. Такие графы будем называть простыми иерархическими графами. Поскольку порожденные подграфы однозначно определяются множествами своих вершин, есть возможность определять простой иерархический граф [math]\displaystyle{ H }[/math] как пару [math]\displaystyle{ (G,T) }[/math], состоящую из основного графа [math]\displaystyle{ G }[/math] и вершинного дерева вложенности [math]\displaystyle{ T }[/math], удовлетворяющего следующим условиям. Вершины дерева [math]\displaystyle{ T }[/math] соответствуют некоторым подмножествам вершин основного графа [math]\displaystyle{ G }[/math] таким образом, что подмножества вершин, соответствующие листьям [math]\displaystyle{ T }[/math], образуют разбиение множества всех вершин графа [math]\displaystyle{ G }[/math] на одноэлементные подмножества. Дуги дерева [math]\displaystyle{ T }[/math] отражают непосредственную вложенность соответствующих подмножеств. Такое представление иерархического графа будем называть вершинным.

Кластерный граф --- это простой вершинный иерархический граф с неориентированным основным графом.

Литература

  • Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ-Петербург, 2003. – 1104 c.
  • Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей // Научная визуализация. – 2014. – Том. 6, N 1. – С. 31 – 50.
  • Касьянов В.Н., Касьянова Е.В. Визуализация информации на основе графовых моделей. – Новосибирск: НГУ, 2014. – 149 с.