图论

定义

一个图G由一个非空集的元素V(G)和一个子集E(G)的无序对不同的元素的集合V(G)。的元素V(G),称为顶点G,可能是由点。如果(x,y)∊E(G),然后边(x,y)可能是由弧形加入x和y。然后x和y据说相邻和边缘(x,y)是事件x和y。如果(x,y)不是一个边缘,然后顶点x和y据说不相邻。G是一个有限图如果V(G)是有限的。一个图表H的子图G如果V(H)⊂V(G),E(H)⊂E(G)。

一个链的图G是一个顶点和边的交替序列x₀,e₁,x₁,e₂,···e_n,x_n顶点,开始和结束事件的每条边的两个顶点前后立即。这条链连接x₀和x_n也可以用x₀,x₁,,x_n明显的边缘上下文。如果链封了x₀=x_n和开放。如果链是封闭的,它被称为周期,它的顶点(除了提供x₀和x_n)是不同的,n≥3。链的长度的边的数量。

一个图表G是贴上各种υ顶点时杰出的等名称x₁,x₂,···x_υ。两个图形G和H据说同构(写G≃H)如果之间存在着一对一的对应关系顶点集保存邻接。例如,G₁和G₂所示,图3同构对应下x_我↔y_我。

两个同构图形被视为相同的(未标记的)图。图是一个树如果它不包含周期的例子中,图G₃的图3。

枚举的图

与υ标签图顶点的数量是2^{υ(υ−1)/ 2}因为υ(υ−1)/ 2是对顶点的数量,和每一对优势或不是一个优势。凯利1889年显示标签树的数量随着υυ顶点^υ−2。

未标记的图形与υ的数量顶点可以通过使用聚的定理。第一个产生的一些术语函数F(x)的系数x^υ给的数量(未标记的)图表υ顶点,可以

。

一个根树有一个点,其根,区别于他人。如果T_υ与υ顶点的树木的数量,生成函数T_υ也可以给

。

1937年的聚(显示在他的回忆录中已经提到,根树的生成函数满足功能方程

。

让t_υ的数量(未标记的)与υ顶点树,生成函数t(x)t_υ可以获得的吗T(x)

。

这个结果是在1948年获得由美国数学家理查德·r·水獭。

许多枚举问题带有指定属性的图形可以解决由聚(定理的应用和推广,由荷兰数学家,1959年净收益de Bruijn。

描述图论的问题

如果有一个类C图的每一个都具有特定的属性P,那么组属性P据说描述类C,提供每一个图G拥有的属性P属于类C。有时会发生一些特殊图拥有的属性P。许多这样的特征是已知的。这是一个典型的例子。

一个完全图K_米是一个图,米顶点,任意两个相邻。的线形图H的图G是一个图的顶点对应的边缘G任意两个顶点的H被邻近当且仅当相应的边缘G事件和相同的顶点吗G。

一个图表G据说是常规的程度n₁如果每个顶点相邻n₁其他的顶点。正则图的学位n₁一般υ顶点是强烈的参数(υn₁,p₁₁¹,p₁₁²)如果任何两个相邻顶点都是毗邻p₁₁¹其他顶点和任意两个不相邻顶点都是毗邻p₁₁²其他的顶点。强正则图和两级协会是同构的概念。的治疗方案对应于图的顶点,两个治疗第一助手或第二个同事根据相应的顶点相邻或不相邻。

它很容易证明行图T₂(米)的一个完整的图形K_米,米≥4强正则参数υ=米(米−1)/ 2,n₁= 2 (米−2),p₁₁¹=米−2,p₁₁²= 4。

令人惊讶的是,这些属性特征T₂(米)除了米= 8,在这种情况下存在三个强烈正则图nonisomorphic彼此和相同的参数T₂(米)。

一个部分几何(r,k,t)是两种类型的对象的一个系统,点和线,与一个关联关系服从以下公理:

1。任意两个点是事件不超过一行。

2。每个点是事件r行。

3所示。每一行都是事件k点。

4所示。给定的一个点P不与线ℓ事件,有确切的t行事件P也有一些ℓ点。

一个图表G从部分获得吗几何以几何的点为顶点的G的两个顶点G被邻近当且仅当相应的点是相同的事件的几何学。强烈正则参数

是否与上述参数强正则图的图像部分几何是感兴趣的。1963年由玻色显示,答案是肯定的如果一个特定的条件

。

我们不太清楚的情况如果不满足此条件,除了特定的值r和t。例如,T₂(米)是同构的图部分几何(2米−1、2)。因此,米> 8其特征是上述定理的结果。另一个结果如下:

给定一组的k−−1d相互正交拉丁方格的秩序k,可以扩展到一套完整的集合k−1相互正交的方块如果条件成立

。

这个案子d= 2是由于1961年Shrikhande和普遍的结果在1963年美国数学家理查德·h·勃拉克。