文章目录一、道路与回路有向道路/有向回路无向图的道路及道路的长度联通图弦定义定理极长初级道路扩大初级道路法二分图定义定理图的性质两点间距离,割点,割边二、欧拉道路与回路定义欧拉定理应用三、哈密顿道路与回路定义(哈密顿图)回路-引理哈密顿道路与回路-充分性定理1闭合图哈密顿道路与回路-充分性定理2例子哈密顿道路与回路-必要性定理一、道路与回路有向道路/有向回路如果P中的边没有重复出现，则分别称为简单(simple)有向道路和简单有向回路进而,如果P中结点也不重复出现,又分别称它们是初级(primary)有向道路和初级有向回路,简称为路和回路显然,初级有向道路path(回路circuit)一定是简
130.被围绕的区域**题目：**给你一个mxn的矩阵board，由若干字符‘X’和‘O’，找到所有被‘X’围绕的区域，并将这些区域里所有的‘O’用‘X’填充。题目链接：130.被围绕的区域解题思路：在飞地的基础上做改动，使用一个栈存储需要改变的节点classSolution{publicint[][]move={{0,1},{0,-1},{1,0},{-1,0}};publicboolean[][]visited;publicbooleanflag;publicvoidsolve(char[][]board){//多一个栈记录要被改变的区域visited=newboolean[board.l
1.最短路径（ShortestPath）两顶点之间权值之和最小的路径。无权图相当于每条边的权值都是1。不能有负权环。有向图的最短路径：从顶点A出发到达其它顶点的最短路径如下表：无法到达的顶点以∞表示无向图的最短路径：也是以A顶点为起点到达其它顶点的最短路径：无权图的最短路径：即把每条边的权值都作为1来看：负权边：只有不存在负权环时才有最短路径。-负权环：不存在最短路径，如果一种绕环，路径值可以达到无穷小。1.1Dijkstra（迪杰斯特拉算法）单源最短路径算法，计算一个顶点到其它所有顶点的路径。不能有负权边时间复杂度O(ElogV)，E边数量，V节点数量，1.1.1思想幻想下图中每个顶点为一个
图论练习题1.把{1，2，3，4，5}任划分成两个子集。则必有一个子集含有两数及其差。2.在2n(n≥2)个人组成的人群中,每人至少有n个朋友.则存在四阶圈.3.k维立方体:以分量为0或1的k维向量集为顶集,仅当两向量只有一个同位分量相异时,相应的两顶相邻.(k∈Nk\inNk∈N)证:k维立方体是顶数2k,2^k,2k,边数k2k−1k2^{k-1}k2k−1的二分图.4.证明:无环图G必定存在二分生成子图H,使得∀v∈V(G)\forallv\inV(G)∀v∈V(G),都有dH(v)≥12dG(v)d_H(v)\ge\frac12d_G(v)dH(v)≥21dG(v)5.若G是连通
文章目录1哈密尔顿回路2哈密尔顿回路算法实现2.1常规回溯算法2.2引入变量记录剩余未访问的节点数量3哈密尔顿路径问题4状态压缩4.1查看第i位是否为14.2设置第i位是为1或者04.3小结4.4状态压缩在哈密尔顿问题中的应用5记忆化搜索5.1记忆化搜索与递推区别5.2记忆化搜索的实现-力扣9801哈密尔顿回路求解哈密尔顿回路如何求解一个图是否存在哈密尔顿回路呢？一个最直观的想法就是暴力求解。暴力求解的思路也很简单：我们遍历图的每一个顶点v，然后从顶点v出发，看是否能够找到一条哈密尔顿回路。暴力求解的代价同求解全排列问题是等价的，其时间复杂度为O(N!)O(N!)O(N!)，N为图的顶点的个数
目录DFSBFS树与图的深度优先遍历树与图的广度优先遍历拓扑排序Dijkstra求最短路1Dijkstra求最短路2bellmen-fordspfaFloydPrim最小生成树Kruskal最小生成树染色法判定二分图匈牙利算法代码部分DFSn−−皇后问题是指将n个皇后放在n×n×的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n，请你输出所有的满足条件的棋子摆法。输入格式共一行，包含整数n。输出格式每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。其中.表示某一个位置的方格状态为空，Q表示某一个位置的方格上摆着皇
参考资料：https://www.ultipa.cn/document/ultipa-graph-analytics-algorithms/degree/v4.0文章目录中心性节点度（Degree）概述基本概念特殊处理接近中心性（ClosenessCentrality）调和中心性（HarmonicCentrality）图中心性（GraphCentrality）中介中心性特征向量中心性（EigenvectorCentrality）CELF相似性（施工中）杰卡德相似性重叠相似度余弦相似度皮尔森相关系数欧几里得距离本文主要内容是介绍图分析相关的概念与算法中心性节点度（Degree）概述节点度算法为每
本文用来记录一篇普通的学校期末小论文（节选），可能存在部分用词不当、限定不准确、内容有误等的错误，欢迎批评指正，共同学习！ 其实离散数学在电路中也是能有所应用的。就像图可以运用在对电路的分析中。例如对于任意正确连接的电路图，由于电流具有方向性，可以把电路图看做是一个有向的连通图；忽略电流的方向，该无向连通图至少可以找到一条初级回路。若关注电流的流动，运用在电路中的节点电流定律又可以用图论中有向图的出度和入度的知识来理解。例如下图题目1-3所示电路，对于电路图中的A节点，运用节点电流分析法可知，在任一时刻，对电路中的任一节点，流入节点的电流之和等于流出节点的电流之和。
一、桥1.1定义对于无向图，如果删除了一条边，整个图的联通分量数量变化，则这条边称为桥如图，红色标注的线就是该图的一条桥(顶点3和顶点5的边)。1.2性质一个图中可以有多条桥如下图，红色的边都是图中的桥一棵树的所有边都是桥如下图，红色边都是图中的桥，一颗树中任意一条边的断开都会导致图中联通分量发生变化1.3寻找桥设置两个数组，Order和Low，并将已访问过的顶点置为绿色Order表示当前顶点遍历的顺序Low表示当前顶点能访问到的顶点的最小值递归遍历，给0-1-3-2顶点依次标上Order和Low，并且将已访问过的顶点置为绿色，如下图在顶点2时，所有连接的顶点都已被访问，并且可以访问到的最小顶
视频来源：6.1.1树的定义_哔哩哔哩_bilibili目录1.树的定义2.树的性质3.极小连通图4.树的中心5.生成树6.最小生成树7.割点8.割点的性质1.树的定义（1）定义：一个连通的无圈的图称为树（2）平凡树：只有一个顶点的树（3）推论1：非平凡树至少有两个叶子（？）（4）推论2：树是双图2.树的性质（1）定理1：若有G（V，E），且G是个（p，q）图，以下命题等价 ①G是树 ②G中任意两个顶点间有唯一的路 ③G连通，p=q+1 ④G中无圈，p=q+1 ⑤G中无圈，且G中任意两个不邻接顶点间加一条边得到一个有唯一圈的图（2）假设对少于p个顶点且满足（1）②
