二分图
在圖論中，二部圖（）是一類特殊的圖，又稱為-{zh-cn:二部图; zh-tw:二分圖; zh-hk:二部圖}-、偶图、雙分圖。二分圖的頂點可以分成兩個互斥的独立集 U 和 V 的圖，使得所有邊都是連結一個 U 中的點和一個 V 中的點。頂點集 U、V 被稱為是圖的兩個部分。等價的，二分圖可以被定義成圖中所有的環都有偶數個頂點。 可以将 U 和 V 当做一個着色：U 中所有頂點为蓝色，V 中所有頂點着绿色，每条边的两个端点的颜色不同，符…
标签：#图
共 10 篇文章
连通图
连通图（）是图论中最基本概念之一，其定义基于连通的概念。在一个无向图G中，若从顶点v_i到顶点v_j有路径相连（从v_j到v_i也一定有路径），则称v_i和v_j是连通的。如果G是有向图，那么连接v_i和v_j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。连通度是指为了让图分解成孤立的子图所要删除的顶点数的最小值。连通度是刻画网络的一个重要指标。 严格定义 对一个图G= (V,E)…
凱萊圖
的凱萊圖]] 凱萊圖（），也叫做凱萊著色圖，是將離散群的抽象結構畫出的一種圖。它的定義是凱萊定理（以阿瑟·凱萊命名）所暗含的。畫凱萊圖時，要選定群的一個生成元集合（通常有限），不同選法可能得到不同的凱萊圖。凱萊圖是與幾何群論的中心工具。 定義 假設G 是群，而S 是G的生成集。凱萊圖\Gamma=\Gamma(G,S) ，是如下構造的著色的有向圖： G 的每個元素g 對應一個頂點。換言之，圖\Gamma 的頂點集合V(\Gamma) 視…
完全圖
{{infobox graph | name = 完全图 | image = | image_caption = K7，含有7个顶点的完全图 | vertices = | edges = \textstyle\frac{n(n - 1)}{2} |notation = K_n | automorphisms = | chromatic_number = | spectrum = \left\{\begin{array}{lll}\emp…
平面图 (图论)
在圖論中，平面圖是可以画在平面上并且使得不同的邊可以互不交疊的圖。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图 K5和完全二分图 K3,3（湯瑪森圖）是最“小”的非平面图。 一個將平面圖畫在平面上的方法稱為平版圖，又稱為圖的平面嵌入，更精確地說，平版圖包含一個平面圖與一個映射，此映射將平面圖的頂點對應到平面上的一點，邊對應到一條平面曲线段，滿足邊兩端點對應到線段的兩端點，…
图 (数据结构)
和3条边的有向图]] 在计算机科学中，图（）是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。 图的数据结构包含一个有限（可能是可变的）的集合作为节点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边（有向图中也称作弧）的集合。节点可以是图结构的一部分，也可以是用整数下标或引用表示的外部实体。 图的数据结构还可能包含和每条边相关联的数值（），例如一个标号或一个数值（即权重，；表示花费、容量、长度等）。 操作…
信号流图
信号流图（Signal-flow graph）最早是由克劳德·香农所發明 ，但因為美国麻省理工学院的于20世纪50年代初提出這個詞，因為也稱梅森圖（Mason graph），信号流图是特殊的，屬於，其中的節點表示系統的變數，而連接兩節點的邊表示二個變數之間的函數關係。信号流图的理論是以有向圖為基礎，不過是應用有向圖來表示系統，和有向圖的原理差異較大。 信号流图最常用來表示物理系統和其控制器（網宇實體系統或控制系統）之間的關係，不過在許多…
完全二分图
完全二分图是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。 定义 完全二分图G:=(V_1 + V_2, E)是一个二分图，使得对于任何两个顶点v_1 \in V_1和v_2 \in V_2，v_1 v_2都是G中的一条边。\left|V_1\right|=m且\left|V_2\right|=n的完全二分图记为K_{m,n}。 例子 File:Complete biparti…
自环
在图论中，自环（Loop）是一条顶点与自身连接的边。简单图中不包含自环。 根据上下文的不同，一个图或者多重图可能被定义为允许或不允许拥有自环（通常与允许或不允许拥有重边一致）： 当允许重边与自环存在于图中时，没有重边或自环的图通常被称为“简单图”与图区分开。 当不允许重边与自环存在于图中时，含有重边或自环的图通常被称为“多重图”或“伪图”与图区分开。 在只有一个顶点的图中，所有的边都必须是自环。这种图叫花束图。 度 在无向图中，顶点的度…
線圖
在图论中，图G所对应的线图是一张能够反映G中各边邻接性的图，记作L(G)。简单来说，L(G)将G中的每条边各自抽象成一个顶点；如若原图中两条边相邻，那么就给线图中对应顶点之间连接一条边。因为线图将原图的边化作了顶点，所以也可以将其视作原图的一种对偶。 哈斯勒·惠特尼证明了：假定图G是连通的，那么除了一种特殊情况外，我们总能根据线图L(G)的结构还原出G的结构。以该定理为中介，可以证明线图的许多其它性质。线图总是无爪图，即线图的所有导出子…