前言
图论起源于著名的哥尼斯堡七桥问题——从这四块陆地中任何一块开始，通过每一座桥正好
一次，再回到起点。欧拉在 1736 年解决了这个问题，欧拉证明了这个问题没有解，并且推广
了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后来的欧拉路
径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。
基本概念
图的定义和分类
图是由顶点V的集合和边E的集合组成的二元组：
• 记 G = ( V ， E ) G=(V，E) G=(V，E)
• 存在一个结点 v v v，可能含有多个前驱结点和后继结点。文章来源：https://www.toymoban.com/news/detail-491816.html
- 有向图，点与有向边的集合
- 带权图(网)，图中的边加上表示某种含义的数值，数值称为边的权
- 连通，两顶点间有路可通
- 连通图：能连成一片的图
- 连通分量：无向图中的极大连通子图
路径
在图 G = ( V ， E ) G=(V，E) G=(V，E)中，如果对于结点 a a a ， b b b，存在满足下述条件的结点序列 x 1 … … x k ( k > 1 ) x_1……x_k(k>1) x1……xk(k>1)
⑴ x 1 = a ， x k = b x_1=a，x_k=b x1=a，xk=b ⑵ ( x i ， x i + 1 ) ∈ E ( i = 1 ‥ k − 1 ) (x_i，x_{i+1})∈E (i=1‥k-1) (xi，x文章来源地址https://www.toymoban.com/news/detail-491816.html
到了这里，关于竞赛知识点5【图论】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[知识点整理]中科院/国科大 自然语言处理nlp 期末考试知识点整理](https://imgs.yssmx.com/Uploads/2024/02/492641-1.png)
