999
правок
Иерархический граф: различия между версиями
Материал из WikiGrapp
нет описания правки
KVN (обсуждение | вклад) (Новая страница: «Пусть <math>G</math> обозначает граф произвольного вида, элементы (вершины и ребра) которого отличаются один от другого какими-либо пометками, называемыми их именами, например: <math>G</math> может быть обыкновенным графом, орграфом (ориентированным графом), мульти...») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
какими-либо пометками, называемыми их именами, | какими-либо пометками, называемыми их именами, | ||
например: <math>G</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>C\subseteq G</math>, если <math>C</math> --- [[Часть графа|часть]] графа <math>G</math>, т. е. <math>C</math> образован подмножеством элементов графа <math>G</math>. | ||
<math>F</math> --- иерархия фрагментов (hierarchy of nested fragments) | <math>F</math> --- [[Иерархия фрагментов|''иерархия фрагментов'']] ([[Hierarchy of nested fragments|''hierarchy of nested fragments'']]) | ||
графа <math>G</math>, если <math>F</math> --- такое множество фрагментов графа <math>C</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\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) фрагмент иерархии | <math>G</math> --- [[Основной фрагмент|''основной'']] (''[[Main fragment|main]]'') фрагмент иерархии | ||
<math>F</math>. Фрагмент <math>C \in F</math> --- элементарный (simple), если в <math>F</math> | <math>F</math>. Фрагмент <math>C \in F</math> --- [[Элементарный фрагмент|''элементарный'']] ([[Simple fragment|simple]]), если в <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> --- [[Прямой подфрагмент|прямой | ||
подфрагмент (proper subfragment) <math>C_2</math> (или, что то же самое, фрагмент, непосредственно вложенный в <math>C_2</math>),если <math>C_1</math> --- подфрагмент <math>C_2</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>. | ||
Иерархический граф <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> называется деревом | непосредственной вложенности. <math>T</math> называется [[Дерево вложенности|''деревом вложенности'']] ([[Inclusion tree|''inclusion tree'']]), а <math>G</math> --- [[Основной граф|''основным графом'']] (''[[underlying graph]]'') иерархического графа | ||
вложенности(inclusion tree), а <math>G</math> --- основным графом (underlying graph | |||
<math>H</math>. | <math>H</math>. | ||
| Строка 36: | Строка 36: | ||
максимальное поддерево дерева <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> называется [[Иерархический подграф|иерархическим подграфом]] (''[[hierarchical subgraph]]'') графа | ||
иерархическим подграфом графа | |||
<math>H</math>, ассоциированным с вершиной | <math>H</math>, ассоциированным с вершиной | ||
<math>p</math>. | <math>p</math>. | ||
Граф <math>H= (G,T)</math> называется связным, если для | Граф <math>H= (G,T)</math> называется ''связным'', если для | ||
любой вершины <math>p</math> дерева <math>T</math> фрагмент <math>G(p)</math> основного графа <math>G</math>, | любой вершины <math>p</math> дерева <math>T</math> фрагмент <math>G(p)</math> основного графа <math>G</math>, | ||
соответствующий <math>p</math>, является связным. | соответствующий <math>p</math>, является ''[[Связный граф|связным]]''. | ||
Пусть <math>H_1=(G_1,T_1)</math> и <math>H_2=(G_2,T_2)</math> --- | Пусть <math>H_1=(G_1,T_1)</math> и <math>H_2=(G_2,T_2)</math> --- | ||
два иерархических графа. <math>H_1</math> называется подграфом | два иерархических графа. <math>H_1</math> называется ''подграфом'' <math>H_2</math>, если <math>T_1</math> --- поддерево дерева <math>T_2</math> и для любой | ||
<math>H_2</math>, если <math>T_1</math> --- поддерево дерева <math>T_2</math> и для любой | |||
вершины <math>p</math> из <math>T_1</math> граф <math>G_1(p)</math> --- часть графа <math>G_2(p)</math>. | вершины <math>p</math> из <math>T_1</math> граф <math>G_1(p)</math> --- часть графа <math>G_2(p)</math>. | ||
| Строка 53: | Строка 51: | ||
образуют такие <math>H = (G,T)</math>, | образуют такие <math>H = (G,T)</math>, | ||
что каждая вершина дерева вложенности <math>T</math> соответствует | что каждая вершина дерева вложенности <math>T</math> соответствует | ||
некоторому порожденному подграфу (induced subgraph) основного графа <math>G</math>. Такие графы будем называть простыми (simple) иерархическими графами. Поскольку | некоторому порожденному подграфу (induced subgraph) основного графа <math>G</math>. Такие графы будем называть ''[[Простой иерархический граф|простыми]]'' (''[[Simple hierarchical graph|simple]]'') иерархическими графами. Поскольку | ||
подграфы однозначно определяются множествами своих вершин, | подграфы однозначно определяются множествами своих вершин, | ||
есть возможность определять простой иерархический граф <math>H</math> | есть возможность определять простой иерархический граф <math>H</math> | ||
| Строка 67: | Строка 65: | ||
вершинным. | вершинным. | ||
Кластерный граф ( | ''[[Кластерный граф]]'' (''[[clustered graph]]'') --- это простой вершинный иерархический граф с неориентированным основным графом. | ||
== Литература == | == Литература == | ||
