fbpx
维基百科

完全点

十二月 12, 2023

在图论中，完全点（universal vertex）是一个在无向图中与其余所有顶点有连接的顶点。其又称作支配点（dominating vertex），因为它在图中形成了一个单元素支配集。

仅有一个完全点的图又称为椎体。在这种情况下，完全点称为椎体的顶点。[1]然而，这个术语与顶点图中的术语相冲突，在顶点图中顶点若被删除，留下的子图为平面图。

特殊图类 编辑

星图正是树图中含有一个完全点的图，且星图可以由向独立集中添加一个完全点来构造。类似地，轮图可以由向环形图中添加一个完全点来构造。[2]在几何学中，三维金字塔以轮图为骨架，其可推广为任何更高维金字塔的图都有一个完全点作为金字塔的顶点。

完备图(集合论中树的可比性图)总是包含一个完全点，即树的根，更准确地说其可以被描述为每个连通的导出子图都包含一个完全点的图。[3]连通阈值图是完备图的一个子类，因此它也包含一个完全点。其可以被定义为通过重复添加完全点或一个孤立点(没有关联边的顶点)而形成的图。[4]

每个含有完全点的图都是一个可拆解图，并且几乎所有可拆解图都有一个完全点。[5]

其他属性 编辑

在一个有n个顶点的图中，一个完全点的度恰好为n - 1。因此，像分裂图一样，具有一个完全点的图不需要查看图结构，可以只通过它们的度序列区分开。

参考文献 编辑

  1. ^ Larrión, F.; de Mello, C. P.; Morgana, A.; Neumann-Lara, V.; Pizaña, M. A., The clique operator on cographs and serial graphs, Discrete Mathematics, 2004, 282 (1-3): 183–191, MR 2059518, doi:10.1016/j.disc.2003.10.023 
  2. ^ Bonato, Anthony, A course on the web graph, Graduate Studies in Mathematics 89, Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS: 7, 2008 [2019-05-22], ISBN 978-0-8218-4467-0, MR 2389013, doi:10.1090/gsm/089, （原始内容于2019-04-04） .
  3. ^ Wolk, E. S., The comparability graph of a tree, Proceedings of the American Mathematical Society, 1962, 13: 789–795, MR 0172273, doi:10.2307/2034179 .
  4. ^ Chvátal, Václav; Hammer, Peter Ladislaw, Aggregation of inequalities in integer programming, Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (编), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics 1, Amsterdam: North-Holland: 145–162, 1977 .
  5. ^ Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł, Almost all cop-win graphs contain a universal vertex, Discrete Mathematics, 2012, 312 (10): 1652–1657, MR 2901161, doi:10.1016/j.disc.2012.02.018 .

外部链接 编辑

十二月 12, 2023
完全点, 在图论中, universal, vertex, 是一个在无向图中与其余所有顶点有连接的顶点, 其又称作支配点, dominating, vertex, 因为它在图中形成了一个单元素支配集, 仅有一个的图又称为椎体, 在这种情况下, 称为椎体的顶点, 然而, 这个术语与顶点图中的术语相冲突, 在顶点图中顶点若被删除, 留下的子图为平面图, 目录, 特殊图类, 其他属性, 参考文献, 外部链接特殊图类, 编辑星图正是树图中含有一个的图, 且星图可以由向独立集中添加一个来构造, 类似地, 轮图可以由向环形图中. 在图论中 完全点 universal vertex 是一个在无向图中与其余所有顶点有连接的顶点 其又称作支配点 dominating vertex 因为它在图中形成了一个单元素支配集 仅有一个完全点的图又称为椎体 在这种情况下 完全点称为椎体的顶点 1 然而 这个术语与顶点图中的术语相冲突 在顶点图中顶点若被删除 留下的子图为平面图 目录 1 特殊图类 2 其他属性 3 参考文献 4 外部链接特殊图类 编辑星图正是树图中含有一个完全点的图 且星图可以由向独立集中添加一个完全点来构造 类似地 轮图可以由向环形图中添加一个完全点来构造 2 在几何学中 三维金字塔以轮图为骨架 其可推广为任何更高维金字塔的图都有一个完全点作为金字塔的顶点 完备图 集合论中树的可比性图 总是包含一个完全点 即树的根 更准确地说其可以被描述为每个连通的导出子图都包含一个完全点的图 3 连通阈值图是完备图的一个子类 因此它也包含一个完全点 其可以被定义为通过重复添加完全点或一个孤立点 没有关联边的顶点 而形成的图 4 每个含有完全点的图都是一个可拆解图 并且几乎所有可拆解图都有一个完全点 5 其他属性 编辑在一个有n个顶点的图中 一个完全点的度恰好为n 1 因此 像分裂图一样 具有一个完全点的图不需要查看图结构 可以只通过它们的度序列区分开 参考文献 编辑 Larrion F de Mello C P Morgana A Neumann Lara V Pizana M A The clique operator on cographs and serial graphs Discrete Mathematics 2004 282 1 3 183 191 MR 2059518 doi 10 1016 j disc 2003 10 023 Bonato Anthony A course on the web graph Graduate Studies in Mathematics 89 Atlantic Association for Research in the Mathematical Sciences AARMS Halifax NS 7 2008 2019 05 22 ISBN 978 0 8218 4467 0 MR 2389013 doi 10 1090 gsm 089 原始内容存档于2019 04 04 Wolk E S The comparability graph of a tree Proceedings of the American Mathematical Society 1962 13 789 795 MR 0172273 doi 10 2307 2034179 Chvatal Vaclav Hammer Peter Ladislaw Aggregation of inequalities in integer programming Hammer P L Johnson E L Korte B H Nemhauser G L 编 Studies in Integer Programming Proc Worksh Bonn 1975 Annals of Discrete Mathematics 1 Amsterdam North Holland 145 162 1977 Bonato Anthony Kemkes Graeme Pralat Pawel Almost all cop win graphs contain a universal vertex Discrete Mathematics 2012 312 10 1652 1657 MR 2901161 doi 10 1016 j disc 2012 02 018 外部链接 编辑埃里克 韦斯坦因 Cone Graph MathWorld 取自 https zh wikipedia org w index php title 完全点 amp oldid 62228085, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。