单纯形图

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

此词条暂由彩云小译翻译，翻译字数共529，未经人工整理和审校，带来阅读不便，请见谅。

文件:Simplex graph.svg
A graph G and the corresponding simplex graph κ(G). The blue-colored node in κ(G) corresponds to the zero-vertex clique in G (the empty set), and the magenta node corresponds to the 3-vertex clique.


thumb|upright=1.3|A graph and the corresponding simplex graph . The blue-colored node in corresponds to the zero-vertex clique in (the empty set), and the magenta node corresponds to the 3-vertex clique.

图和相应的单纯形图。中的蓝色节点对应于(空集)中的零顶点团，而洋红节点对应于3个顶点团。

In graph theory, a branch of mathematics, the simplex graph κ(G) of an undirected graph G is itself a graph, with one node for each clique (a set of mutually adjacent vertices) in G. Two nodes of κ(G) are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex.

In graph theory, a branch of mathematics, the simplex graph of an undirected graph is itself a graph, with one node for each clique (a set of mutually adjacent vertices) in . Two nodes of are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex.

图论是数学的一个分支，无向图的单纯形图本身就是一个图，其中每个团(一组相邻的顶点)有一个节点。当相应的两个小团在单个顶点存在或不存在时，两个节点通过边连接。

The empty set is included as one of the cliques of G that are used to form the clique graph, as is every set of one vertex and every set of two adjacent vertices. Therefore, the simplex graph contains within it a subdivision of G itself. The simplex graph of a complete graph is a hypercube graph, and the simplex graph of a cycle graph of length four or more is a gear graph. The simplex graph of the complement graph of a path graph is a Fibonacci cube.

The empty set is included as one of the cliques of that are used to form the clique graph, as is every set of one vertex and every set of two adjacent vertices. Therefore, the simplex graph contains within it a subdivision of itself. The simplex graph of a complete graph is a hypercube graph, and the simplex graph of a cycle graph of length four or more is a gear graph. The simplex graph of the complement graph of a path graph is a Fibonacci cube.

空集被包括在用于形成团图的团之中，每个一个顶点的集合和每个相邻两个顶点的集合也包括在内。因此，单纯形图包含它自身的一个细分。完全图的单纯形图是一个超立方图，长度为四个或四个以上的循环图的单纯形图是一个齿轮图。路径图补图的单纯形图是斐波那契立方体。

The complete subgraphs of G can be given the structure of a median algebra: the median of three cliques A, B, and C is formed by the vertices that belong to a majority of the three cliques.[1] Any two vertices belonging to this median set must both belong to at least one of A, B, or C, and therefore must be linked by an edge, so the median of three cliques is itself a clique. The simplex graph is the median graph corresponding to this median algebra structure. When G is the complement graph of a bipartite graph, the cliques of G can be given a stronger structure as a distributive lattice,[2] and in this case the simplex graph is the graph of the lattice. As is true for median graphs more generally, every simplex graph is itself bipartite.

The complete subgraphs of can be given the structure of a median algebra: the median of three cliques , , and is formed by the vertices that belong to a majority of the three cliques., page 200. Any two vertices belonging to this median set must both belong to at least one of , , or , and therefore must be linked by an edge, so the median of three cliques is itself a clique. The simplex graph is the median graph corresponding to this median algebra structure. When is the complement graph of a bipartite graph, the cliques of can be given a stronger structure as a distributive lattice,. and in this case the simplex graph is the graph of the lattice. As is true for median graphs more generally, every simplex graph is itself bipartite.

完整的子图可以给出一个中值代数的结构: 三个团体的中值，由属于三个团体中大多数的顶点组成。属于这个中间集合的任意两个顶点都必须至少属于其中的一个，或者，因此必须由一条边连接，所以三个团体的中间值本身就是一个团体。单纯形图是对应于这个中值代数结构的中值图。当一个二部图的补图是分配格时，可以给出一个更强的结构。在这种情况下，单纯形图就是格的图。对于更普遍的中值图来说，每个单纯形图本身都是二部图。

The simplex graph has one vertex for every simplex in the clique complex X(G) of G, and two vertices are linked by an edge when one of the two corresponding simplexes is a facet of the other. Thus, the objects (vertices in the simplex graph, simplexes in X(G)) and relations between objects (edges in the simplex graph, inclusion relations between simplexes in X(G)) are in one-to-one correspondence between X(G) and κ(G).

The simplex graph has one vertex for every simplex in the clique complex of , and two vertices are linked by an edge when one of the two corresponding simplexes is a facet of the other. Thus, the objects (vertices in the simplex graph, simplexes in ) and relations between objects (edges in the simplex graph, inclusion relations between simplexes in ) are in one-to-one correspondence between and .

单纯形图的团复形中的每个单纯形都有一个顶点，当两个相应的单纯形中的一个是另一个的面时，两个顶点由一条边连接。因此，对象(单纯形图中的顶点，单纯形图中的单纯形)和对象之间的关系(单纯形图中的边，单纯形图中的单纯形之间的包含关系)处于和之间的双射。

Simplex graphs were introduced by 脚本错误：没有“Footnotes”这个模块。,[3] who observed that a simplex graph has no cubes if and only if the underlying graph is triangle-free, and showed that the chromatic number of the underlying graph equals the minimum number n such that the simplex graph can be isometrically embedded into a Cartesian product of n trees. As a consequence of the existence of triangle-free graphs with high chromatic number, they showed that there exist two-dimensional topological median algebras that cannot be embedded into products of finitely many real trees. 脚本错误：没有“Footnotes”这个模块。 also use simplex graphs as part of their proof that testing whether a graph is triangle-free or whether it is a median graph may be performed equally quickly.

Simplex graphs were introduced by , credit the introduction of simplex graphs to a later paper, also by Bandelt and van de Vel, but this appears to be a mistake. who observed that a simplex graph has no cubes if and only if the underlying graph is triangle-free, and showed that the chromatic number of the underlying graph equals the minimum number such that the simplex graph can be isometrically embedded into a Cartesian product of trees. As a consequence of the existence of triangle-free graphs with high chromatic number, they showed that there exist two-dimensional topological median algebras that cannot be embedded into products of finitely many real trees. also use simplex graphs as part of their proof that testing whether a graph is triangle-free or whether it is a median graph may be performed equally quickly.

单纯形图的引入是由，将单纯形图的引入归功于后来的一篇论文，也是由 Bandelt 和 van de Vel 引入的，但这似乎是一个错误。他观察到单纯形图没有立方体当且仅当底层图是无三角形的，并指出底层图的色数等于最小数，这样单纯形图可以等距嵌入到树的笛卡儿积中。由于具有高色数的无三角形图的存在，证明了存在不能嵌入到有限多实树乘积中的二维拓扑中值代数。也使用单纯形图作为他们的证明的一部分，测试是否一个图是三角形无关或是否它是一个中间图可以同样快速地执行。

Notes

  1. ↑ 脚本错误：没有“Footnotes”这个模块。, page 200.
  2. ↑ 脚本错误：没有“Footnotes”这个模块。.
  3. ↑ 脚本错误：没有“Footnotes”这个模块。 credit the introduction of simplex graphs to a later paper, also by Bandelt and van de Vel, but this appears to be a mistake.

References

  • Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J.E.; Pach, J.; Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemp. Math., vol. 453, Providence, RI: AMS, pp. 49–86.
  • Bandelt, H.-J.; van de Vel, M. (1989), "Embedding topological median algebras in products of dendrons", Proceedings of the London Mathematical Society, s3-58 (3): 439–453, doi:10.1112/plms/s3-58.3.439, archived from the original on 2013-04-15.
  • Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188.
  • Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Median graphs and triangle-free graphs", SIAM Journal on Discrete Mathematics, 12 (1): 111–118, CiteSeerX 10.1.1.28.5906, doi:10.1137/S0895480197323494, MR 1666073.
  • Propp, James (1997), "Generating random elements of finite distributive lattices", Electronic Journal of Combinatorics, 4 (2): R15, arXiv:math.CO/9801066.
  • .
  • .
  • .
  • .
  • .

References

  • .
  • .
  • .
  • .
  • .

Category:Graph operations Category:Graph families Category:Bipartite graphs

类别: 图运算类别: 图族类别: 二部图


This page was moved from wikipedia:en:Simplex graph. Its edit history can be viewed at 单纯形图/edithistory

取自“https://wiki.swarma.org/index.php?title=单纯形图&oldid=32667”