layout:cycle
title:Space
date: 2019-09-25 16:06:10
tags:
以下讨论中，图均指无向联通图
定义1：欧拉网，指只保留图中某一个边集形成的子图，使得这个子图中每个点的度数都是偶数
欧拉网可以认为是不要求联通的欧拉图。
根据定义，无边图也是一个欧拉网
命题1：在一个图所有欧拉网构成的集合上定义运算$\oplus$：$A\oplus B=A$与$B$的对称差，则欧拉网集合关于这个运算构成一个群，称为网群G
证明：考虑每个点的度数，显然在取对称差之后依然满足每个点的度数均为偶数，空图是单位元，逆元是其本身
命题2：H是一个包含图中所有简单环(包括无边图)的集合，且H可以生成G
证明：对于任意一个欧拉网，将其进行不能重复经过点的$dfs$，最终必会找到一个简单环，可以将这个环去掉，剩下的还是欧拉网，继续下去，最终可将任何一个欧拉网分解成一些简单环。
命题3：对于一个无向联通图，任意求出一个生成树，找出所有非树边，设有$k$条，每条本身以及对应的树链构成一个简单环，这种环被称为基础环，基础环集合是网群的一组基
证明：显然任意一些基础环的对称差是欧拉网，现在只需证，任意一个欧拉网都能唯一由一组基础环边对称差表示。
等价于去证明：每一个简单环都可以唯一由一组基础环对称差表示，考虑枚举走过了哪些非树边，之后对于每一条树边，如果这个点$x$子树中含有奇数个选定的基础环树上端点，那么这条边一定在环上，否则一定不在环上，可以发现子树中含有奇数个选定的基础环树上端点这个条件等价于环的对称差，因此这些基础环的对称差就是那个简单环。
用处：数环，数欧拉网，异或最短路