图论
图论
图的概念
结点 vertices
边 Edges
环
- 自环：a->a
- 平凡环：a->b, b->a
平行边：关联于同一对结点的若干条边
有向图：只有有向边的图。
无向图：只有无向边的图。
简单图：不含有环和平行边的图。
多重图：含有平行边的图。
无权图：边长均为1
带权图：
度
路的概念
路：其中ei是关联vi-1 ,vi的边, 则称结点和边的交叉序列
- 简单图， 则路可以只用结点序列表示.
如右图中，路：abcad - 有向图，则路可以只用边序列表示。
如有向图中 e1e5e2e3 e6 是一条路.
回路：如果一条路的起点和终点是一个结点，则称此路是一个回路
迹与闭迹：
如果一条路中，所有边都不同，则称此路为迹。
如果一条回路中，所有边都不同，则称此回路为闭迹。
通路与圈：
- 如果一条路中，所有结点都不同，则称此路为通路。
- 如果一条回路中，除起点和终点外，其余结点都不同，则称此回路为圈。
连通性
无向图的连通性
两点间连通：在无向图中,结点u和v之间如果存在一条路， 则称u与v是连通的。
对称关系
连通分支（分量）：令G=<V,E>是无向图, R是V上连通关系, 设R对V的商集中有等价类V1,V2,V3,…, Vn ,这n个等价类构成的n个子图分别记作G(V1),G(V2),G(V3),…, G(Vn),并称它们为G的连通分支. 并用W(G)表示G中连通分支数。
连通图: 如果一个图G只有一个连通分支(W(G)=1)，则称G是连通图。
强连通、单侧连通和弱连通
- 在简单有向图G中，如果任何两个结点间相互可达，则称G是强连通。
- 如果任何一对结点间，至少有一个结点到另一个结点可达，则称G是单侧连通。
- 如果将G看成无向图后(即把有向边看成无向边)是连通的，则称G是弱连通。
强分图、单侧分图和弱分图
有向图的连通性
结点间的可达性：G=<V,E>是有向图, u,v∈V, 如果从u到v有一条路, 则称从u到v可达。
结点间的可达关系，具有自反性和传递性。
结点u到v的距离：如果u可达v, 可能从u到v有多条路,其中最短的路的长度,称之为从u到v的距离.记作d<u,v>.
割集 (Cut Set)
点割集与割点：
令G=<V,E>是连通无向图, 结点集合V1 ,V1V，如果删去V1中所有结点后,G就变得不连通了, 而删去V1的任何真子集中的所有结点得到的子图仍然连通.则
称V1是G的一个点割集. 如果点割集V1中只有一个结点，则称此结点为割点。
边割集与割边(桥)
令G=<V,E>是连通无向图, 边的集合E1,E1E, 如果删去E1中所有边后,G就变得不连通了, 而删去E1的任何真子集中的所有边,得到的子图仍然连通.则称E1是G的一个边割集. 如果边割集E1中只有一条边, 则称此边为割边, 也称之为桥。
图的表示
矩阵
邻接矩阵
可达性矩阵
最短路和关键路径
无权图：边长均为1
带权图：
欧拉图、汉密尔顿图
欧拉图 E图(Euler)
- 欧拉路：在无孤立结点的图G中，如果存在一条路，它经过图中每条边一次且仅一次，称此路为欧拉路。
- 欧拉回路：在无孤立结点的图G中，若存在一条回路，它经过图中每条边一次且仅一次，称此回路为欧拉回路。称此图为欧拉图,或E图.(Euler)
汉密尔顿图 H图
汉密尔顿路：通过G中每个结点恰好一次的路。
汉密尔顿回路(H回路)：通过G中每个结点恰好一次的回路。
汉密尔顿图(H图)：具有汉密尔顿回路(H回路)的图。
二部图
平面图
对偶图与着色
树与生成树
根树