下载文档原格式
图论知识点摘要：图论是数学的一个分支，它研究图的性质和应用。
图由节点（或顶点）和连接这些节点的边组成。
本文将概述图论的基本概念、类型、算法以及在各种领域的应用。
1. 基本概念1.1 节点和边图由一组节点（V）和一组边（E）组成，每条边连接两个节点。
边可以是有向的（指向一个方向）或无向的（双向连接）。
1.2 路径和环路径是节点的序列，其中每对连续节点由边连接。
环是一条起点和终点相同的路径。
1.3 度数节点的度数是与该节点相连的边的数量。
对于有向图，分为入度和出度。
1.4 子图子图是原图的一部分，包含原图的一些节点和连接这些节点的边。
2. 图的类型2.1 无向图和有向图无向图的边没有方向，有向图的每条边都有一个方向。
2.2 简单图和多重图简单图是没有多重边或自环的图。
多重图中，可以有多条边连接同一对节点。
2.3 连通图和非连通图在无向图中，如果从任意节点都可以到达其他所有节点，则称该图为连通的。
有向图的连通性称为强连通性。
2.4 树树是一种特殊的连通图，其中任意两个节点之间有且仅有一条路径。
3. 图的算法3.1 最短路径算法如Dijkstra算法和Bellman-Ford算法，用于在加权图中找到从单个源点到所有其他节点的最短路径。
3.2 最大流最小割定理Ford-Fulkerson算法用于解决网络流中的最大流问题。
3.3 匹配问题如匈牙利算法，用于解决二分图中的匹配问题。
4. 应用4.1 网络科学图论在网络科学中有广泛应用，如社交网络分析、互联网结构研究等。
4.2 运筹学在运筹学中，图论用于解决物流、交通网络优化等问题。
4.3 生物信息学在生物信息学中，图论用于分析蛋白质相互作用网络、基因调控网络等。
5. 结论图论是数学中一个非常重要和广泛应用的领域。
它不仅在理论上有着深刻的内涵，而且在实际应用中也发挥着关键作用。
随着科技的发展，图论在新的领域中的应用将会不断涌现。
本文提供了图论的基础知识点，包括概念、图的类型、算法和应用。
图论期末总结一、引言图论是一门研究图和网络结构的数学学科。
图论不仅在数学领域中有着广泛的应用，而且在计算机科学、物理学、化学、生物学等交叉学科中也扮演着重要的角色。
在本学期的图论课程中，我系统地学习了图论的基本概念、算法和应用，对图论的知识有了更深入的理解和认识。
在本文中，我将对本学期学习的图论知识进行总结和归纳。
二、基本概念1. 图的定义与表示：图是由一组顶点和一组边组成的数学模型。
在图中，顶点表示图中的实体，边表示顶点之间的关系。
图可以用邻接矩阵或邻接表来表示。
2. 图的类型：图可以分为有向图和无向图、加权图和非加权图、简单图和多重图等。
有向图的边具有方向性，无向图的边没有方向性。
加权图的边带有权重，非加权图的边没有权重。
简单图没有自环和平行边，多重图可以有自环和平行边。
3. 图的基本术语：顶点的度数是指与该顶点相关联的边的数量。
入度是有向图中指向该顶点的边的数量，出度是有向图中从该顶点发出的边的数量。
路径是由边连接的一系列顶点，路径的长度是指路径上边的数量。
连通图是指从一个顶点到任意其他顶点都存在路径。
三、图的算法1. 图的遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图遍历算法。
DFS从一个顶点出发，探索所有可能的路径，直到无法继续深入为止。
BFS从一个顶点开始，逐层探索图中的其他顶点，直到所有顶点都被访问过为止。
2. 最短路径算法：最短路径算法用来计算图中两个顶点之间的最短路径。
迪杰斯特拉算法和弗洛伊德算法是两种常用的最短路径算法。
迪杰斯特拉算法适用于没有负权边的图，通过每次选择到某个顶点的最短路径来逐步扩展最短路径树。
弗洛伊德算法适用于有负权边的图，通过每次更新两个顶点之间的最短路径来逐步求解最短路径。
3. 最小生成树算法：最小生成树算法用于找到连接图中所有顶点的最小代价树。
克鲁斯卡尔算法和普林姆算法是两种常用的最小生成树算法。
克鲁斯卡尔算法通过每次选择代价最小的边来逐步扩展最小生成树。
图论常考知识点总结1. 图的基本概念图是由顶点集合和边集合构成的。
顶点之间的连接称为边，边可以有方向也可以没有方向。
若图的边没有方向，则称图为无向图；若图的边有方向，则称图为有向图。
图的表示方式：邻接矩阵和邻接表。
邻接矩阵适合存储稠密图，邻接表适合存储稀疏图。
2. 图的连通性连通图：如果图中任意两点之间都存在路径，则称该图是连通图。
强连通图：有向图中，任意两个顶点之间都存在方向相同的路径，称为强连通图。
弱连通图：有向图中，去掉每条边的方向之后，所得到的无向图是连通图，称为弱连通图。
3. 图的遍历深度优先搜索（DFS）：从起始顶点出发，沿着一条路往前走，走到不能走为止，然后退回到上一个分支点，再走下一条路，直到走遍图中所有的顶点。
广度优先搜索（BFS）：从起始顶点出发，先访问它的所有邻居顶点，再按这些邻居顶点的顺序依次访问它们的邻居顶点，依次类推。
4. 最短路径狄克斯特拉算法：用于计算图中一个顶点到其他所有顶点的最短路径。
弗洛伊德算法：用于计算图中所有顶点之间的最短路径。
5. 最小生成树普里姆算法：用于计算无向图的最小生成树。
克鲁斯卡尔算法：用于计算无向图的最小生成树。
6. 拓扑排序拓扑排序用于有向无环图中对顶点进行排序，使得对每一条有向边(u,v)，满足排序后的顶点u在顶点v之前。
以上就是图论中一些常考的知识点，希望对大家的学习有所帮助。
当然，图论还有很多其他的知识点，比如欧拉图、哈密顿图、网络流等，这些内容都值得我们深入学习和探讨。
图论在实际应用中有着广泛的应用，掌握好图论知识对于提升计算机科学和工程学的技能水平有着重要的意义。
图论基础知识汇总(总32页) -CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除图与网络模型及方法§1 概论图论起源于18世纪。
第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。
1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。
1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。
哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。
图论中所谓的“图”是指某类具体事物和这些事物之间的联系。
如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。
图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。
哥尼斯堡七桥问题就是一个典型的例子。
在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。
当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。
欧拉为了解决这个问题，采用了建立数学模型的方法。
他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。
问题成为从任一点出发一笔画出七条线再回到起点。
欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。
图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。
图论课期末总结首先，我在课程中学习了图的基本概念和性质。
图是由一组顶点和一组边组成的数据结构，可以用来描述很多现实生活中的问题。
在图的定义中，顶点表示问题中的对象，而边表示对象之间的关系。
图可以分为有向图和无向图，有向边表示关系有方向性，无向边表示关系无方向性。
另外，图还可以分为带权图和非带权图，带权图中的边上有权重，非带权图中的边没有权重。
接着，我学习了图的连通性和路径的概念。
在图中，如果任意两个顶点之间都存在路径，那么这个图就是连通的。
连通图中的任意两个顶点都是连通的，非连通图中存在孤立的顶点。
路径是从一个顶点出发，经过若干个顶点，到达另一个顶点的序列。
在有向图中，路径有方向性，即从起点到终点的方向。
而在无向图中，路径没有方向性，即可以从任意一端出发。
然后，我学习了图的表示方法。
常见的图的表示方法有邻接矩阵和邻接表。
邻接矩阵是一个二维数组，其中数组的行和列分别代表图的顶点，数组元素的值表示顶点之间是否有边相连。
邻接表是由一组链表组成的数据结构，链表的每个节点表示一个顶点，链表节点中存储了与该顶点相邻的其他顶点。
除了学习图的基本概念和表示方法，我还学习了一些图的算法和应用。
其中包括最短路径算法、最小生成树算法和网络流算法等。
最短路径算法是用来寻找图中两个顶点之间最短路径的算法，其中最著名的算法是Dijkstra算法和Floyd-Warshall算法。
最小生成树算法是用来寻找连通图中一棵包含所有顶点的生成树的算法，其中最著名的算法是Prim算法和Kruskal算法。
网络流算法是用来解决网络中最大流和最小割问题的算法，其中最著名的算法是Ford-Fulkerson算法和Edmonds-Karp算法。
在图的应用方面，图论在计算机科学、通信网络、交通运输等领域都有广泛的应用。
在计算机科学中，图可以用来表示网页链接、社交网络和路由问题等。
在通信网络中，图可以用来建模网络拓扑和路由算法。
在交通运输中，图可以用来建模交通流量和路径规划。
图论总结(超强大) -标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII1.图论 Graph Theory1.1.定义与术语 Definition and Glossary1.1.1.图与网络 Graph and Network1.1.2.图的术语 Glossary of Graph1.1.3.路径与回路 Path and Cycle1.1.4.连通性 Connectivity1.1.5.图论中特殊的集合 Sets in graph1.1.6.匹配 Matching1.1.7.树 Tree1.1.8.组合优化 Combinatorial optimization1.2.图的表示 Expressions of graph1.2.1.邻接矩阵 Adjacency matrix1.2.2.关联矩阵 Incidence matrix1.2.3.邻接表 Adjacency list1.2.4.弧表 Arc list1.2.5.星形表示 Star1.3.图的遍历 Traveling in graph1.3.1.深度优先搜索 Depth first search (DFS)1.3.1.1.概念1.3.1.2.求无向连通图中的桥 Finding bridges in undirected graph1.3.2.广度优先搜索 Breadth first search (BFS)1.4.拓扑排序 Topological sort1.5.路径与回路 Paths and circuits1.5.1.欧拉路径或回路 Eulerian path1.5.1.1.无向图1.5.1.2.有向图1.5.1.3.混合图1.5.1.4.无权图 Unweighted1.5.1.5.有权图 Weighed —中国邮路问题The Chinese post problem1.5.2.Hamiltonian Cycle 哈氏路径与回路1.5.2.1.无权图 Unweighted1.5.2.2.有权图 Weighed —旅行商问题The travelling salesman problem1.6.网络优化 Network optimization1.6.1.最小生成树 Minimum spanning trees1.6.1.1.基本算法 Basic algorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3.Sollin（Boruvka）1.6.1.2.扩展模型 Extended models1.6.1.2.1.度限制生成树 Minimum degree-bounded spanning trees1.6.1.2.2.k小生成树 The k minimum spanning tree problem(k-MST)1.6.2.最短路Shortest paths1.6.2.1.单源最短路 Single-source shortest paths1.6.2.1.1.基本算法 Basic algorithms1.6.2.1.1.1...................................................................................................... Dijkstra1.6.2.1.1.2........................................................................................... Bellman-Ford1.6.2.1.1.2.1. ................................... S hortest path faster algorithm(SPFA)1.6.2.1.2.应用Applications1.6.2.1.2.1............................ 差分约束系统 System of difference constraints1.6.2.1.2.2. ...... 有向无环图上的最短路 Shortest paths in DAG1.6.2.2.所有顶点对间最短路 All-pairs shortest paths1.6.2.2.1................................. 基本算法 Basic algorithms1.6.2.2.1.1. ......................................Floyd-Warshall1.6.2.2.1.2. ............................................. Johnson 1.6.3...................................................... 网络流 Flow network1.6.3.1.最大流 Maximum flow1.6.3.1.1................................. 基本算法 Basic algorithms1.6.3.1.1.1. .............................. F ord-Fulkerson method1.6.3.1.1.1.1....................... Edmonds-Karp algorithm1.6.3.1.1.1.1.1.................... Minimum length path1.6.3.1.1.1.1.2............... Maximum capability path1.6.3.1.1.2. ................. 预流推进算法 Preflow push method1.6.3.1.1.2.1................................... Push-relabel1.6.3.1.1.2.2.............................. Relabel-to-front1.6.3.1.1.3. ........................................ Dinic method1.6.3.1.2.................................. 扩展模型 Extended models1.6.3.1.2.1. ................................... 有上下界的流问题1.6.3.2.最小费用流 Minimum cost flow1.6.3.2.1.................. 找最小费用路 Finding minimum cost path1.6.3.2.2......................... 找负权圈 Finding negative circle1.6.3.2.3.....................网络单纯形 Network simplex algorithm1.6.4............................................................. 匹配 Matching1.6.4.1.二分图 Bipartite Graph1.6.4.1.1.无权图-匈牙利算法Unweighted - Hopcroft and Karpalgorithm1.6.4.1.2... 带权图-KM算法 Weighted –Kuhn-Munkres(KM) algorithm1.6.4.2.一般图General Graph1.6.4.2.1....... 无权图-带花树算法 Unweighted - Blossom (Edmonds) 1.图论 Graph Theory1.1.定义与术语 Definition and Glossary1.1.1.图与网络 Graph and Network,V E称为图(graph)。
图论基本知识点梳理第一部分（基本概念）1.G 连通的充分必要条件是1)(=G ω。
或若k G V 2|)(|=，且对)(G V v ∈∀，有k v d ≥)(，则G 是连通图。
4.图G 为二分图当且仅当G 中无奇圈。
5.在仅两个奇次顶点的图中，此二奇次顶点连通。
6.设G 为简单图，若2)(≥G δ，则G 中有圈。
7. 设G 为简单图，若3)(≥G δ，则G 中有偶圈。
具体地，(1)单星妖怪中有偶圈。
(2)在-k 正则图G 中，若3≥k ，则G 中有偶圈。
8.简单图G 与其补图c G 不能都不连通。
9.在2∆的三角剖分中，正常三角形为奇数个。
10.以下等价(1) G 是树（无圈连通图）。
(2) G 中任两顶点间恰有一条轨。
(3) G 无圈，1-=νε。
(4) G 是连通图，1-=νε 。
(5) G 是连通图，且对G 的任意边e ，e G -不连通。
（树每边皆割边）(6) G 无圈，且对任一不在)(G E 的边e ，e G +恰含一个圈。
11. 若G 连通，则1)()(-≥G G νε。
G 的生成树是G 最小的连通生成子图。
12. G 是连通图的充分必要条件是G 有生成树。
13. 2≥ν的树T 至少有两个叶。
14.完全图n K 的生成树个数2)(-=n n n K τ。
15. 图G 可平面嵌入的充分必要条件是G 可以球面嵌入。
（染地球上各国等价于染地图上各国）16. （Euler 公式） G 是连通平面图, 则2=+-φεν.17. 证明：若G 是3≥ν的连通平面图，则63-≤νε。
18. 证明：平面图G 的最小顶点次数5≤δ。
19 3≥ν平面图G 是极大平面图的充要条件是G 的平面嵌入的每个面皆三角形。
3≥ν平面图G 是极大平面图的充要条件是63-=νε。
20 G 是平面图当且仅当G 中不含与5K 和3,3K 同胚的子图。
21M 是图G 的最大匹配当且仅当G 中无M 的可增广轨。
22婚配定理：设G 是具有二分类),(Y X 的偶图，存在把X 中顶点皆许配的匹配的充要条件是|||)(|,S S N X S ≥⊆∀，其中)(S N 是S 中每个顶点的邻点组成的所谓S 的邻集。
图论知识点总结•对应简单图的度序列，在同构意义下可能不止一个•简单图的度序列最大度一定要小于等于n-1•只要和为偶数就是图的度序列•若图中两点u与v间存在途径，则u与v间存在路•若过点u存在闭迹，则过点u存在圈•一个图是偶图当且仅当它不包含奇圈•无向图的顶点之间的连通关系一定是等价关系•有向图的顶点之间的单向连通关系不是等价关系•一个简单图G的n个点的度不能互不相同•无向图的邻接矩阵的行和对应顶点的度数•无向图的邻接矩阵的所有元素之和等于边数的2倍•无向图的邻接矩阵的平方的对角线元素等于对应顶点的度数•无向图的邻接矩阵的平方的对角线元素之和等于边数的2倍•无向图的邻接矩阵的特征值的平方和等于边数的2倍•若G是非连通的，则邻接矩阵相似于某个对角矩阵•树一定是连通无圈图•树G无环且任意两点之间存在唯一的路•树无回路但任意添加一条边后有回路•回路是边不重的圈的并•如果一个闭迹不是一个圈，那么它一定是没有重边的圈的并集。
•n阶树T的形心由一个点或两个相邻点组成。
•若T只有一个形心，则形心的权小于n/2•若T有两个形心，则形心的权等于n/2•树T的对偶图全是环•G是极大平面图的充要条件各面的次数均为3且为连通图每个n方体都有完美匹配由n方体的构造知：n方体有2n个顶点，每个顶点可以用长度为n的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。
划分顶点，把坐标之和为偶数的顶点归入X，否则归入Y。
X中顶点互不邻接，Y中顶点也如此。
所以n方体是偶图。
很容易验证n方体的每个顶点度数为n，所以n方体是n正则偶图。
因此，n方体存在完美匹配。
树T有完美匹配当且仅当对所有顶点v∈T，o(T-v)=1必要性：树T有完美匹配，由Tutte定理知o(T-v)≤|{v}|=1显然T是偶数阶的图，o(T-v)≥1.因此o(T‒v)=1。
充分性：对于T的任意顶点v，假设Tv是T-v仅有的奇分支，且Tv与v之间的边为uv。
1.图论Graph Theory1.1.定义与术语Definition and Glossary1.1.1.图与网络Graph and Network1.1.2.图的术语Glossary of Graph1.1.3.路径与回路Path and Cycle1.1.4.连通性Connectivity1.1.5.图论中特殊的集合Sets in graph1.1.6.匹配Matching1.1.7.树Tree1.1.8.组合优化Combinatorial optimization1.2.图的表示Expressions of graph1.2.1.邻接矩阵Adjacency matrix1.2.2.关联矩阵Incidence matrix1.2.3.邻接表Adjacency list1.2.4.弧表Arc list1.2.5.星形表示Star1.3.图的遍历Traveling in graph1.3.1.深度优先搜索Depth first search (DFS)1.3.1.1.概念1.3.1.2.求无向连通图中的桥Finding bridges in undirected graph1.3.2.广度优先搜索Breadth first search (BFS)1.4.拓扑排序Topological sort1.5.路径与回路Paths and circuits1.5.1.欧拉路径或回路Eulerian path1.5.1.1.无向图1.5.1.2.有向图1.5.1.3.混合图1.5.1.4.无权图Unweighted1.5.1.5.有权图Weighed —中国邮路问题The Chinese post problem1.5.2.Hamiltonian Cycle 哈氏路径与回路1.5.2.1.无权图Unweighted1.5.2.2.有权图Weighed —旅行商问题The travelling salesman problem 1.6.网络优化Network optimization1.6.1.最小生成树Minimum spanning trees1.6.1.1.基本算法Basic algorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3.Sollin（Boruvka）1.6.1.2.扩展模型Extended models1.6.1.2.1.度限制生成树Minimum degree-bounded spanning trees1.6.1.2.2.k小生成树The k minimum spanning tree problem(k-MST)1.6.2.最短路Shortest paths1.6.2.1.单源最短路Single-source shortest paths1.6.2.1.1.基本算法Basic algorithms1.6.2.1.1.1.Dijkstra1.6.2.1.1.2.Bellman-Ford1.6.2.1.1.2.1.Shortest path faster algorithm(SPFA)1.6.2.1.2.应用Applications1.6.2.1.2.1.差分约束系统System of difference constraints1.6.2.1.2.2.有向无环图上的最短路Shortest paths in DAG1.6.2.2.所有顶点对间最短路All-pairs shortest paths1.6.2.2.1.基本算法Basic algorithms1.6.2.2.1.1.Floyd-Warshall1.6.2.2.1.2.Johnson1.6.3.网络流Flow network1.6.3.1.最大流Maximum flow1.6.3.1.1.基本算法Basic algorithms1.6.3.1.1.1.Ford-Fulkerson method1.6.3.1.1.1.1.Edmonds-Karp algorithm1.6.3.1.1.1.1.1.Minimum length path1.6.3.1.1.1.1.2.Maximum capability path1.6.3.1.1.2.预流推进算法Preflow push method1.6.3.1.1.2.1.Push-relabel1.6.3.1.1.2.2.Relabel-to-front1.6.3.1.1.3.Dinic method1.6.3.1.2.扩展模型Extended models1.6.3.1.2.1.有上下界的流问题1.6.3.2.最小费用流Minimum cost flow1.6.3.2.1.找最小费用路Finding minimum cost path1.6.3.2.2.找负权圈Finding negative circle1.6.3.2.3.网络单纯形Network simplex algorithm1.6.4.匹配Matching1.6.4.1.二分图Bipartite Graph1.6.4.1.1.无权图-匈牙利算法Unweighted - Hopcroft and Karp algorithm1.6.4.1.2.带权图-KM算法Weighted –Kuhn-Munkres(KM) algorithm1.6.4.2.一般图General Graph1.6.4.2.1.无权图-带花树算法Unweighted - Blossom (Edmonds)1.图论Graph Theory1.1.定义与术语Definition and Glossary1.1.1.图与网络Graph and Network二元组(),V E称为图(graph)。
V为结点(node)或顶点(vertex)集。
E为V中结点之间的边的集合。
点对(),u v称为边(edge)或称弧(arc)，其中,u v V∈，称,u v是相邻的(adjacent)，称u,v与边(),u v相关联(incident)或相邻。
若边的点对(),u v有序则称为有向(directed)边，其中u称为头(head)，v称为尾(tail)。
所形成的图称有向图(directed graph)。
为对于u来说(),u v是出边(outgoing arc)；对于v来说(),u v是入边(incoming arc)。
反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图(undirected graph)。
若图的边有一个权值(weight)，则称为赋权边，所形成的图称赋权图(weighted graph)或网络(network)。
用三元组G(V,E,W)表示网络。
其中W表示权集，它的元素与边集E一一对应。
满足||||log||E V V<的图，称为稀疏(sparse)图；反之，称为稠密(dense)图。
1.1.2.图的术语Glossary of Graph阶(order)：图G中顶点集V的大小称作图G的阶。
环(loop)：若一条边的两个顶点为同一顶点，则此边称作环。
简单图(simple graph)：没有环、且没有多重弧的图称作简单图。
定向图：对无向图G的每条无向边指定一个方向得到的有向图。
底图：把一个有向图的每一条有向边的方向都去掉得到的无向图。
逆图：把一个有向图的每条边都反向由此得到的有向图。
竞赛图(tournament)：有向图的底图是无向完全图，则此有向图是竞赛图。
邻域(neighborhood)：在图中与u 相邻的点的集合{|,(,)}v v V u v E ∈∈，称为u 的邻域，记为()N u 。
度：度(degree)：一个顶点的度是指与该边相关联的边的条数，顶点v 的度记作deg(v)。
握手定理：无向图：deg()2||v V v E ∈=∑；有向图：deg ()deg ()v V v Vv v +-∈∈=∑∑。
入度(indegree)：在有向图中，一个顶点v 的入度是指与该边相关联的入边(即边的尾是v)的条数，记作deg ()v +。
出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数，记作deg ()v -。
孤立点(isolated vertex)：度为0的点。
叶(leaf)：度为1的点。
源(source)：有向图中，deg ()v +=0 的点。
汇(sink)：有向图中，deg ()v -=0的点。
奇点(odd vertex)：度为奇数的点。
偶点(even vertex)：度为偶数的点。
子图：子图(sub-graph)：G'称作图G 的子图如果(')()V G V G ⊆以及(')()E G E G ⊆。
生成子图(spanning sub-graph)：即包含G 的所有顶点的连通子图，即满足条件(')()V G V G =的G 的子图G ’。
生成树(spanning tree)：设T 是图G 的一个子图，如果T 是一棵树，且()()V T V G =，则称T 是G 的一个生成树。
即G 的生成子图，且子图为树。
点导出子图(induced subgraph)：设)(G V V ⊆'，以V '为顶点集，以两端点均在V '中的边的全体为边集所组成的子图，称为G 的由顶点集V '导出的子图，简称为G 的点导出子图，记为[]G V '。
边导出子图(edge-induced subgraph)：设)(G E E ⊆'，以E '为顶点集，以两端点均在E '中的边的全体为边集所组成的子图，称为G 的由边集E '导出的子图，简称为G 的边导出子图，记为][E G '。
图的补图(complement)：设G 是一个图，以)(G V 为顶点集，以{(,)|(,)()}u v u v E G ∉为边集的图称为G 的补图，记为G 。
点集的补集：记 ''V V V =-为点集'V 的补集。
特殊的图：零图(null graph)：E =∅，即只有孤立点的图。
n 阶零图记为n N 。
平凡图(trivial graph)：一阶零图。
空图(empty graph)：V E ==∅的图。
有向无环图(directed acyclic graph(DAG))：有向的无环的图。
完全图(complete graph)：完全图是指每一对不同顶点间都有边相连的的无向图，n 阶完全图常记作n K 。
二分图（bipartite graph ）：若图G 的顶点集可划分为两个非空子集X 和Y ，即V X Y =⋃且X Y ⋂=∅，且每一条边都有一个顶点在X 中，而另一个顶点在Y 中，那么这样的图称作二分图。
