图的基本概念：一个图G定义为一个有序对＜V，E＞，记为G=＜V，E＞.其中V为非空有限集，其元素称为结点或顶点，E也是有限集，其元素称为边.对E中的每条边都有V中的两个结点与之对应，其结点对可以有序也可无序.
无向边、环：若边e与无序结点对［u，v］对应，称e为无向边，简称边，记为e=［u，v］，u，v称为边e的端点，也称u和v为邻接点，边e关联u与v.关联同一结点的两条边称为邻接边.连接一结点与它自身的边称为环或自回路.两条端点对应相同的边称为平行边.
有向边（弧）：若边e与有序结点对＜u，v＞对应，称e为有向边或弧，记为e=＜u，v＞，u和v分别称为弧e的始点和终点，也称u邻接到v，v邻接于u.若e和e′有相同的始点，称e和e′相邻.始点和终点都对应相同的弧称为平行弧.
孤立结点：在图中不与任何结点相邻接的结点称为孤立结点.
无向图、有向图、混合图、有向图的基图：每条边都是无向边的图称为无向图.每条边都是有向边的图称为有向图.既有有向边又有无向边的图称为混合图.将有向图各有向边去掉方向后得到的无向图称为原图的基图.
多重图、简单图、零图、平凡图、完全图：
（1）含有平行边（或弧）的图称为多重图.不含平行边（或弧）和环的图称为简单图.
（2）具有n个结点和m条边的图称为（n，m）图，也称n阶图.一个（n，0）图称为零图，（1，0）图称为平凡图.
（3）任两结点之间都有边（或弧）的简单图称为完全图.n个结点的无向完全图记为Kn.
定理9.1 完全图Kn的边数为C（n，2）.
带权图（加权图）：给每条边（或弧）都赋予权的图G=＜V，E＞称为带权图或加权图，记为G=＜V，E，W＞，W为各边（或弧）权的集合.
子图、生成子图：设G=＜V，E＞、G′=＜V′，E′＞是两个图.(www.xing528.com)
（1）若V⊆′V且E⊆′E，则称G′为G的子图，G为G′的母图.
（2）若G′是G的子图，且V⊂′V或E⊂′E，则称G′为G的真子图.
（3）若V′=V且E⊆′E，则称G′为G的生成子图或支撑子图.
度数、出度、入度：在有向图G=＜V，E＞中，对于结点v∈V，以v为始点的弧的条数称为v的出度，记为d+（v）；以v为终点的弧的条数称为v的入度，记为d-（v）；v的出度和入度之和称为v的度数，记为d（v）.
在无向图G=＜V，E＞中，结点v的度数等于它关联的边数，记为d（v）.若v有环，规定该结点度数因环而增加2.
定理9.2（欧拉握手定理） 在图G=＜V，E＞中，结点度数的总和等于边数的两倍，即
定理9.3 图G中度数为奇数的结点必为偶数个.
定理9.4 在任何有向图中，所有结点的入度之和等于所有结点的出度之和.
悬挂结点、悬挂边：无向图中度数为1的结点称为悬挂结点，它对应的边称为悬挂边.
正则图：各结点度数均相同的图称为正则图.各结点度数均为k的图称为k度正则图.
定理9.5 设G为任意n阶无向简单图，则每个结点的度数都不超过n-1.
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
