Cluster graph: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) (Новая страница: «'''Сluster graph''' (''кластерный граф'') is a graph formed from the disjoint union of complete graphs (or cliques). Equivalently, a graph is a cluster graph if and only if it has no '''three-vertex induced path''' (i.e. three-vertex path as an induced subgraph) '''''P''<sub>3</sub>'''; for this reason, the cluster graphs are also called '''''P''<su...») |
KVN (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Сluster graph''' (''кластерный граф'') is a [[Graph (undirected graph)|graph]] formed from the disjoint union of [[Complete graph|complete graphs]] (or [[Clique|cliques]]). Equivalently, a graph is a cluster graph if and only if it has no '''three-vertex induced path''' (i.e. three-vertex path as an [[Induced (with vertices) subgraph|induced subgraph]]) '''''P''<sub>3</sub>'''; for this reason, the cluster graphs are also called '''''P''<sub>3</sub>-free graphs.''' The cluster graphs are the graphs for which [[adjacency]] is an [[equivalence relation]], and their connected components are the equivalence classes for this relation. | '''Сluster graph''' (''кластерный граф'') is a [[Graph (undirected graph)|graph]] formed from the disjoint union of [[Complete graph|complete graphs]] (or [[Clique|cliques]]). Equivalently, a graph is a cluster graph if and only if it has no '''three-vertex induced path''' (i.e. three-vertex path as an [[Induced (with vertices) subgraph|induced subgraph]]) '''''P''<sub>3</sub>'''; for this reason, the cluster graphs are also called '''''P''<sub>3</sub>-free graphs.''' The cluster graphs are the graphs for which [[adjacency]] is an [[equivalence relation]], and their connected components are the equivalence classes for this relation. | ||
[[Категория:Деревья]] | |||
[[Категория:Основные термины]] | |||
[[Файл:Cluster graph.png|350px|альт=Cluster_graph.png]] | |||
Текущая версия от 12:17, 21 ноября 2024
Сluster graph (кластерный граф) is a graph formed from the disjoint union of complete graphs (or cliques). Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path (i.e. three-vertex path as an induced subgraph) P3; for this reason, the cluster graphs are also called P3-free graphs. The cluster graphs are the graphs for which adjacency is an equivalence relation, and their connected components are the equivalence classes for this relation.
