各种图

有向无环图

如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图
$DAG$的生成树个数等于入度非零节点的入度积

拓扑排序

$DAG$顶点的线性序列

补图

将完全图去除图$G$的边集后得到的图

反向图

将有向图$G$的边反向后得到的图

分层图

状态多维,层之间拓扑有序

links

平面图&对偶图

可以画在平面上且边只在顶点处相交的图称为平面图

平面图的对偶图是将这个平面的每个区域看成点,原图每一条边所属的两个相邻的区域对应在对偶图中的点有连边

links

竞赛图

将一个完全无向图的边定向后得到的有向图

兰道定理

比分序列:把竞赛图每一个点的出度从小到大排列得到的序列
一个长度为$n$的序列$s$$(s_1≤s_2≤…≤s_n,n≥1)$是合法的比分序列当且仅当

特别地,当$k=n$时式子取等号

区间图&弦图&完美图

弦:连接环中不相邻的两个点的边

弦图:

完美消除序列:

定理:一个无向图是弦图当且仅当它有一个完美消除序列

最大势算法:

lk1

lk2

仙人掌图

如果无向联通图$G$的任意一条边最多属于一个简单环,称$G$为仙人掌

简单环:不经过重复结点的环

祭出神图

分享到: