图论（Graph Theory）是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点以及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用线连接两点表示相应两个事物间具有这种关系。

第一部分：图的基本概念

        在现实世界中有许多现象、事物、状态是用某种图来描述的。例如用途的节点来表示集合的元素，用图的变表示关系，所得到的是关系图。也就是说，集合和在集合上的关系可以用图来描述。如果我们考虑最一般的图形，只关心图形的节点和连接两个节点的连线，不关心具体形状、连线的长度和节点的位置，那么这种最一般的图形就可以表示某种数据结构。

       图是一种离散结构，它是由最基本的抽象结构–>集合派生出来的一种特殊的结构，在这种结构中，不尽需要了解某些对象是否属于某集合，同时还要了解两个对象之间是否有某种关系。在我们要了解的关系中，特别有意义的是等价关系和序关系。我们要讨论一个既要描述对象的从属性（既性质决定从属性），又要能描述两个对象之间的关系的结构，而这种结构再结合有限且规模不大的情况下可以用图来表示。但并不是只有能用有限图形表示的才是图，只要满足图的定义而并不一定能用有限图形表示的仍然是图。

        图的定义：图G是由两个集合V和E组成，计为G=<V,E>，其中V是顶点的有穷非空集合，E是V中定点偶对（称为边）的有穷集。通常，也将图G的顶点集和边分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。

        图分为有向图和无向图两种，在有向图中，一条有向边是由两个顶点组成的有序对，有许对通常用尖括号表示。(Vi,Vj)和(Vj,Vi)是两条不同的有向边。有向边也称为弧，边始点称为弧尾，终点称为弧头。在一个图中，两个结点由一条有向边或无向边关联，则这两个点称为邻接点。无向图的边均为顶点的无序对，无序对通常用圆括号表示。在无向图G中，假设i!=j，i、j属于V，(i,j)属于E，即i和j是G的两个不同的顶点，(i,j)是G中的一条边，顶点i和顶点j是相邻的顶点，便(i,j)是顶点i和顶点j相关联的边。

        在一个图中，不与任何节点相邻的节点，称为孤立点，仅有孤立点组成的图称为零图。仅由一个孤立点构成的图称为平凡图。

        一条边关联的两个顶点重合，称此边为环（即两顶点重合的边）。

        只有一条边与其关联的点，所对应的边叫悬挂边。

        关联于同一对定点的若干条边称为平行边，平行边的条数称为重数。含有平行边的图称为多重图。

        不含平行边和环的图称为简单图。

        设图G=<V，E>为n阶无向简单图，若G中每个顶点与其余n-1个顶点都相邻，则称G为n阶无向完全图，记作Kn。显然，n阶无向完全图具有n(n-1)/2条边