串并图
This article "串并图" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:串并图. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
在图论中，串并图（脚本错误：没有“lang”这个模块。）是一种特殊的图，有两“终端”。串并图能够模拟串联电路和并联电路（串并电路）。
串并图这术语也可以被称为是“系列平行图”[1]、“串列并列图”、“串联并联图”、还是“串行并行图”，可是串并图是最短的。
定义和术语[编辑]
建设图是伪图。定义串并图有几种方法。比方说，可以用所谓“series compositions”和“parallel compositions”[2]。另一个定义涉及完全图K2[3]。
主要定义：更简单地说，如果从零图（null graph）开始，可以通过以下操作(重复地)来构造G，那G是串并图：
注意这定义相当不同但是允许又方便又优雅的性能。
性能[编辑]
最重要的表征就是：当且仅当G没有K4子式时，G是串并的[4]。这定理源于Dirac/Duffin。
主义每个3-连接图都有完全图K4子式，所以根据上面定理，不可能是串并图。则串并图最多是2-连接的。
而且串并图是2-degenerate的，有最多2度的顶点。
串并图也有有些所谓treewidth、branchwidth性能[4][5][6]。极大串并图就是2-trees，也有ear decomposition的表征[2]。
Duffin定理的证明[编辑]
当且仅当G没有K4子式时，G是串并的
需要引理：如果G没有K4子式，X是团，，则有一个最多2度的顶点。
Duffin定理的证明使以上的引理以及 |V(G)| + |E(G)| 的归纳法[7]。
以上的引理还暗示串并图是2-degenerate。
参見[编辑]
參考文獻[编辑]
- REDIRECT Template:Delete
脚本错误：没有“Redirect_Template_List”这个模块。 This article "串并图" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:串并图. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
This article "串并图" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:串并图. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one. This article "串并图" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:串并图. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
