边图

一个图G的边图是指由G这样得到的图：节点集为G的边集，两节点有一条边相连当且仅当它们所对应的边在G中相邻。常用L(G)表示G的边图。图L(G)的边图称为G的2叠边图，常记为L(G)。

边图概念

一个图G的边图是指由G这样得到的图：节点集为G的边集，两节点有一条边相连当且仅当它们所对应的边在G中相邻。常用L(G)表示G的边图。图L(G)的边图称为G的2叠边图，常记为L(G)。类似地，G的k叠边图就是指G的(k-1)叠边图的边图，常记为L(G)。一个图G的团图是指这样的图：以G的每个团作为节点，两节点有一条边相连当且仅当它们所对应的团有公共节点。G的团图常记为cl(G)。cl(G)也称为G的1叠团图。G的(k-1)叠团图的团图称为G的k叠团图，常记为cl(G)，k≥2。一个图G的块图是指这样的图：以G的每个块作为节点，两节点有一条边相连当且仅当它们所对应的块有公共节点。G的块图常记为B(G)。一个图G的割点图是指这样的图；以G的每一个割点作为节点，两节点有一条边相连当且仅当它们所对应的割点在同一块中。G的割点图常记为C(G)。一个图G的块-割点图是指这样的图：以G的所有块和所有割点组成的集合为节点集，两节点有一条边相连，当且仅当它们对应于一个块和一个割点，并且这个块含这个割点.G的块-割点图常记为BC(G)。一个图G的k幂图(k≥1)是指这样的图：以G的节点集为节点集，两节点有一条边相连，当且仅当它们对应于G的节点在G上的距离最多为k。G的k幂图常记为G。当然，G的1幂图就是G本身。

边图交邻图

交邻图是一类特殊的图。它是由一个子集族产生的图。设F={S₁，S₂，…，S_p}是由一个有限集S的p个不同的非空子集S₁，S₂，…，S_p组成的族.以F为节点集，节点S_i和S_j有边相连当S_i∩S_j≠ ∅(i≠j)，这样所得的图称为F的交邻图，常记为Ω(F)。以数轴上的一些区间作为节点，两节点有一条边相连当且仅当它们所对应的区间的交非空，这样所得的图称为区间图。区间图还有两种有意义的推广。一种叫盒图：节点集为n维立方体的集合，两节点相邻当且仅当它们对应的两个立方体相交.另一种叫树路图：节点集为一树上的一些路组成的集合，两节点相邻当且仅当它们对应的两条路有公共部分(包括有公共端点).若将节点代表平面上一个圆的不包括二端点的弦，两节点相邻当且仅当它们相应的弦有一个公共点，称这样的图为圆图。

边图图

图论的研究对象。一个图是一个集合上的一种二元关系。这个集合的元素称为图的节点，若两节点之间有这种确定的二元关系，则称有一条边连这两个节点。一个图的节点的数目称为这个图的阶;图的边的数目称为它的度。在文献中，总是将一般的图记为G=(V，E)，其中，V=V(G)和E=E(G)分别表示G的节点集和边集。

若有一条边连一个图的某两个节点，则称这两个节点相邻，并称这两个节点为这条边的端点。若某一节点是某一条边的端点，则称这个节点和这条边关联。若两条边和同一节点关联，则称这两条边相邻，两个端点是同一个节点的边称为环。若某条边的两个端点不是同一个节点，且只有一条边连这两个节点，则称这条边为杆。

只有一个节点而没有边的图称为平凡图；没有边的图称为孤立图。以某两节点为端点的边可能不止一条，这时称连这两个节点的边为重边。既可以有环，也可以有重边的图称为准图；没有环而可能有重边的图称为带重图;没有重边而可能有环的图称为带环图；既没有重边也没有环的图称为简单图。若一个图的阶是有限的，则称这个图为有限图，否则称这个图为无限图。每两个节点都相邻的简单图称为完全图.若一个n阶图的节点用1，2，…，n来代表，则称它为标定图。若在图的每一条边上赋以一个实数或者对于每个节点赋以一个实数，则称它为赋权图。

边图图论

近年来比较活跃的数学分支之一。图论是研究各种图的性质和特征的一门理论，主要包括图与子图、图的连通性、可平面性、正则图、树、着色问题、图的矩阵以及网络等内容。图论的发展已有200多年的历史。早在18世纪中叶就已出现有关图的文字记载。这时的图论尚处于萌芽阶段，多数问题是围绕着游戏而产生的，最有代表性的是著名的哥尼斯堡七桥问题(相当于我国的一笔画问题)。19世纪中叶到20世纪中叶，图论问题大量出现，诸如哈密尔顿“绕行世界”问题，关于地图着色的四色问题以及与之有关联的图的可平面性等等。在这个阶段，也出现了以图为工具去解决其他领域中一些问题的成果，例如，凯莱把图论应用到有机化学中关于同分异构物的计数问题，克希霍夫应用树研究电网络的分析问题等等。20世纪中叶以后，由于生产管理、军事、交通运输、计算机网络等方面提出的实际问题的需要，特别是许多离散性问题的出现，以及由于有了大型超高速计算机，而使大规模问题的求解成为可能，图论及其应用的研究得到了飞速发展。这个阶段的开创性工作是以福特和福克逊建立的网络流理论为代表的。图论和线性规划、动态规划等优化理论和方法的相互渗透，促进了组合最优化理论和算法的研究以及图论对实际问题的应用，与此同时也丰富了图论的内容，使图论的发展更加充满活力。