边收缩
在图论中，边收缩是指將一個圖的其中一個邊移除，並將被移除邊的兩個頂點合併，同時保持與被移除邊之頂點相連的其他頂點之連接關係的一種變換，為圖子式理論中的基本運算元之一，然而此種變換不一定是圖論中的變換，亦可以作用於拓樸結構甚至是幾何體，例如邊收縮二十面體，即正二十面體經過一次邊收縮變換後的像。另一種與邊收縮類似的圖論變換為點合併（vertex contraction）是邊收縮變換的一個廣義形式。 定义 邊收縮是一種作用於邊上的變換，因此其…
标签：#图论
共 82 篇文章
线完美图
在图论中，线完美图(line perfect graph)是其线图为完美图的图。同样的，这些图中每个奇数长度的简单环都是一个三角形。 当且仅当一个图的任意双连接组件都是二分图、完全图K_4或三角形书 K_{1,1,n}时，该图被称为线完美的，因为这三种类型的双连接组件本身是完美图，其形成的线图本身是完美的。 通过类似的推理，所有的线完美图都是奇偶图、梅尼尔图和完全有序图. 线完美图推广了二部图，并与二部图共同拥有最大匹配和最小顶点覆盖有…