个人博客
www.tothefor.com
蓝桥杯复习知识点汇总

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

预知

1. 欧拉回路：若图G中存在这样一条路径， 使得它恰好通过G中每条边一次，则称该路径为欧拉路径（欧拉通路）。若该路径是一个环路, 则称为欧拉(Euler)回路。

• 具有欧拉回路的图称称为欧拉图。
• 具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

定理和推论

无向图

• 1. 一个无向图G存在欧拉路径当且仅当无向图G是连通图，且该图中有两个奇度顶点（度数为奇数）或者无奇度顶点。
• 2. 当无向图G是仅有两个奇度顶点的连通图时，G的欧拉路径必定以这两个奇度顶点为端点。
• 3. 一个无向图G存在欧拉回路当且仅当无向图G连通不存在奇度顶点。（当G是无奇度顶点的连通图时，G必有欧拉回路。）

有向图

1. 一个有向图G存在欧拉路径当且仅当G的基图连通，且满足以下两个条件之一 :
   • 所有顶点的入度和出度相等;
   • 除两个顶点外，其余顶点的出度与入度都相等。且这两个顶点有一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1。其他顶点的入度和出度相等。

2. 当有向图G包含两个入度和出度不相同的顶点且有欧拉路径时，欧拉路径必定以这两个入度出度不相同的顶点为端点，且必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点。

3. 一个有向图G存在欧拉回路当且仅当图G是连通的有向图，且所有顶点的入度和出度相等。

欧拉通路、回路存在的判断

判断欧拉通路是否存在的方法

有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图：图连通，所有的顶点出度=入度。

无向图：图连通，所有顶点都是偶数度。（G为欧拉图（存在欧拉回路）的充分必要条件是G为无奇度结点的连通图。）

讯享网

欧拉回路的应用

哥尼斯堡七桥问题、一笔画问题、旋转鼓轮的设计。

代码实现

无向图

邻接矩阵存图

import java.io.*; import java.math.BigInteger; import java.util.*; / * @Author DragonOne * @Date 2021/12/5 21:27 * @墨水记忆 www.tothefor.com */ public class Main { 
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out)); public static Scanner sc = new Scanner(System.in); public static int maxd = 2000+7; public static int INF = 0x3f3f3f3f; public static int mod = ; public static int[][] grap = new int[maxd][maxd]; //存储关系 public static boolean[][] vis = new boolean[maxd][maxd]; //是否访问过 public static int n; //n个点 public static int cnt=0; //找到的边的条数 public static void euler(int u){ 
    for(int i=1;i<=n;++i){ 
    if(grap[u][i]>0 && !vis[u][i]){ 
    vis[u][i]=vis[i][u]=true; euler(i); System.out.println(u+"->"+i); cnt++; } } } public static void main(String[] args) throws Exception { 
    n = nextInt(); int m = nextInt(); //m条边 for(int i=1;i<=m;++i){ 
    int a = nextInt(); int b = nextInt(); grap[a][b]++; grap[b][a]++; } euler(1); System.out.println("长度为："+cnt); closeAll(); } public static void cinInit(){ 
    cin.wordChars('a', 'z'); cin.wordChars('A', 'Z'); cin.wordChars(128 + 32, 255); cin.whitespaceChars(0, ' '); cin.commentChar('/'); cin.quoteChar('"'); cin.quoteChar('\''); cin.parseNumbers(); //可单独使用来还原数字 } public static int nextInt() throws Exception{ 
    cin.nextToken(); return (int) cin.nval; } public static long nextLong() throws Exception{ 
    cin.nextToken(); return (long) cin.nval; } public static double nextDouble() throws Exception{ 
    cin.nextToken(); return cin.nval; } public static String nextString() throws Exception{ 
    cin.nextToken(); return cin.sval; } public static void closeAll() throws Exception { 
    cout.close(); in.close(); out.close(); } } 

输入输出：

讯享网//输入 3 3 1 2 2 3 1 3 //输出  3->1 2->3 1->2 长度为：3 

有向图

邻接矩阵存图

import java.io.*; import java.math.BigInteger; import java.util.*; / * @Author DragonOne * @Date 2021/12/5 21:27 * @墨水记忆 www.tothefor.com */ public class Main { 
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out)); public static Scanner sc = new Scanner(System.in); public static int maxd = 2000+7; public static int INF = 0x3f3f3f3f; public static int mod = ; public static int[][] grap = new int[maxd][maxd]; public static boolean[][] vis = new boolean[maxd][maxd]; public static int n; public static int cnt=0; public static void euler(int u){ 
    for(int i=1;i<=n;++i){ 
    if(grap[u][i]>0 && !vis[u][i]){ 
    vis[u][i]=true; euler(i); System.out.println(u+"->"+i); cnt++; } } } public static void main(String[] args) throws Exception { 
    n = nextInt(); int m = nextInt(); for(int i=1;i<=m;++i){ 
    int a = nextInt(); int b = nextInt(); grap[a][b]++; } euler(1); System.out.println("长度为："+cnt); closeAll(); } public static void cinInit(){ 
    cin.wordChars('a', 'z'); cin.wordChars('A', 'Z'); cin.wordChars(128 + 32, 255); cin.whitespaceChars(0, ' '); cin.commentChar('/'); cin.quoteChar('"'); cin.quoteChar('\''); cin.parseNumbers(); //可单独使用来还原数字 } public static int nextInt() throws Exception{ 
    cin.nextToken(); return (int) cin.nval; } public static long nextLong() throws Exception{ 
    cin.nextToken(); return (long) cin.nval; } public static double nextDouble() throws Exception{ 
    cin.nextToken(); return cin.nval; } public static String nextString() throws Exception{ 
    cin.nextToken(); return cin.sval; } public static void closeAll() throws Exception { 
    cout.close(); in.close(); out.close(); } } 

输出输出：

讯享网//输入 5 6 2 3 2 5 3 4 1 2 4 2 5 1 //输出  5->1 2->5 4->2 3->4 2->3 1->2 长度为：6 

练习题目

洛谷 P7771 欧拉路径 ：判定 + 寻找欧拉路径

洛谷 P1341 无序字母对：判定 + 寻找欧拉路径

洛谷 P2731 骑马修栅栏：寻找欧拉路径

洛谷 P1127 词链：判定 + 寻找欧拉路径