Mathématiques et sciences humaines. Mathematics and social sciences | |
Graphes d'arches | |
Leclerc, Bruno1  | |
关键词: graph; algorithm; tree; 2-tree; tree encoding; distance; cycle; | |
DOI : 10.4000/msh.2858 | |
学科分类:数学(综合) | |
来源: College de France * Ecole des Hautes Etudes en Sciences Sociales (E H E S S) | |
【 摘 要 】
An arch-graph may be obtained from a simple edge by successive addings of 3-paths, grafted on their extremities. Equivalently, it admits no subgraph of which every vertex has degree at least three, and is maximal with this property, for a fixed number of vertices. It is known that a tree distance may be summarized by 2n-3 of its entries, conveniently chosen. Arch graphs with n vertices correspond to such sets of entries. They include the graphs of the so-called 2-tree type. We study these graphs, and the k-arch graphs and k-trees which naturally generalize them. It is recalled how a tree metric or function is associated to a valued arch graph, and the properties of this correspondence are investigated.
【 授权许可】
Unknown
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201912020428638ZK.pdf | 611KB | download |