Graphe基础知识
Graphe non orienté
G = (S,A)
连通（connexité）
在无向图中，顶点v到顶点w之间有路径存在，则称v和w是连通的
连通图（Graphe connexe）
若图G中任意两个顶点之间都直接或间接连通，则称图G为连通图，否则为非连通图
连通分量（Composante connexe）
无向图中的极大连通子图称为连通分量
Graphe orienté
G = (S,A)
On note l’arc (s,t)par s->t
强连通（forte connexité）
在有向图中，如果有一对顶点v和w，从v到w和w到v之间都有路径，则称这两个顶点是强连通的
强连通图（Graphe forte connexité）
若有向图G中任意一对顶点都是强连通的，则称图G为强连通图
强连通分量（Composante fortement connexe (CFC)）
有向图中的极大强连通子图称为有向图的强连通分量
###完全图
graphe valué
G = (S,A,C)
ordre d’un graphe （图的阶数）
Le nombre de sommets d’un graphe G s’appelle l’ordre du graphe
图的顶点的数量
P-Graphe
P-Graphe 是一个图，其中任意两个顶点之间的边（弧）最多为 p 条。
形式化定义：
一个P-Graphe 是一个有向图 G = (V, A) ，其中：
• V 是顶点集（sommets）。
• A 是弧集（arcs）。
• 对于任意两个不同的顶点 s, t ∈ V ，满足：|{ (s, t) ∈ A }| ≤ p
即在 s 和 t 之间，最多只能有 p 条有向边（弧）。
Graphe plein
Existence d’un arc entre toute paire de sommets.
任意两个顶点之间都有边相连
Multigraphe （多重图）
两个顶点之间可以有多条边
Graphe Simple （简单图）
Un graphe est dit simple si
- Il est sans boucles （没有循环）
- Il n’y a jamais plus d’une arête entre deux sommets quelconques （任意两个点之间不会有多条边）
sous graphe （子图）
G' = (S', A')
G'是G 的一部分，顶点和边都可以减少
Graphe Partiel （部分图）
G' = (S, A')
G'的顶点和G一样，只是缺少一些边
Graphe Planaire（平面图）别管不会
Kuratowski 定理是判定一个图是否是平面图的一个重要工具。它指出：
• 一个图是平面图当且仅当它不包含以下两个图的子图：
• K_5 （完全图，5 个顶点的图）。
• K_{3,3} （完全二分图，3 个顶点与另 3 个顶点相连的图）。
换句话说，如果图中存在 K_5 或 K_{3,3} 的子图，那么它一定不是平面图。
Successeur / Prédécesseur （前序顶点和后继顶点）
V(s) = T(s) ∪ T-1 (s)
Arcs Adjacents (resp. arêtes Adjacentes)（相邻边）
Degré d’un sommet (顶点的度数)
在图论中，顶点的度数（Degré） 是指与该顶点相连接的边的数量。度数可以分为以下两类：
- Degré sortant (外度)：对于有向图，顶点的外度是指从该顶点出发的边的数量
- Degré entrant (入度)：对于有向图，顶点的入度是指指向该顶点的边的数量。
对于无向图来说，每条边连接两个顶点，因此每条边会增加两个顶点的度数。
表示方法：
无向图中，度数通常记作 deg(v) ，其中 v 是顶点。
有向图中，度数可能有两个分量： d-(v), d+(v)
Demi-degré d’un sommet (半度数)
半度数（Demi-degré） 通常是指每个顶点的度数的一半。这个术语在一些特定的上下文中使用，比如在有向图中，半度数表示的是入度和出度的和的一半。
Co-cycle d’un graphe（图的共循环）
Graphes Symétriques（对称图）
Graphe AntiSymétrique（反对称图）
Graphe Complet（完全图）
Un graphe G=(S, A) est dit complet si, pour toute paire de sommets (s, t), il existe au moins un arc de la forme (s, t) ou (t, s) dans le graphe.
Dans le cas non orienté, le graphe est dit complet s’il existe au moins
une arête {s, t}pour tout couple de sommets (s, t) ∈ SxS.
对于无向图，在无向完全图中任意两个顶点之间都存在边；对于有向图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。
- 对于无向图，有
n(n-1)/2条边的无向图称为完全图 - 对于有向图，有
n(n-1)条弧的图称为完全图
Graphe vide
On appelle graphe vide tout graphe qui ne contient aucun arc (resp.
Aucune arête).G=(S, A) avec A={}
Clique（团）
Une clique est un graphe simple pour lequel il existe exactement une
arête entre toutes paires de sommets.
在图论中，团（Clique） 是一种特殊类型的图。具体来说，团 是一个完全图（Complete Graph），它满足以下条件：
在团中，每对顶点之间都有一条边。也就是说，图中的每个顶点都与其它顶点相连。
定义：
- Clique 是一个无向图，其中任何两个不同的顶点都通过一条边直接相连。
- 一个包含 n 个顶点的团是一个包含 n 个顶点且所有顶点对之间都有边的图，通常记为 K_n ，其中 K_n 表示一个有 n 个顶点的完全图。
Graphe complémentaire d’un graphe simple（补图）
补图的顶点与原图相同，边集合由不属于原图的边组成
Graphe Bi – Parti（二分图）
**Graphe biparti（二分图）**是指这样的一张图，它的顶点集可以划分为两个不相交的子集，使得所有的边都只在这两个子集之间，而不是子集内部。
形式化定义:
一个无向图 G = (V, E) 是二分图，当且仅当其顶点集 V 可以分成两个互不相交的子集 V1 和 V2 ，即：
V = V1 ∪ V2 et V1 ∩ V2 = ∅
并且所有的边 E 只连接 V1 和 V2 之间的顶点，而不是 V1 内部或 V2 内部的顶点。
图论专业术语中法对照表
1. 基础概念
| 中文 | 法语 |
|---|---|
| 图（Graph） | Graphe |
| 顶点（Vertex） | Sommet |
| 边（Edge） | Arête（无向图）/ Arc（有向图） |
| 无向图（Undirected Graph） | Graphe non orienté |
| 有向图（Directed Graph） | Graphe orienté |
| 邻接（Adjacency） | Adjacence |
| 连接（Connection） | Connexion |
2. 连通性
| 中文 | 法语 |
|---|---|
| 连通图（Connected Graph） | Graphe connexe |
| 连通分量（Connected Component） | Composante connexe |
| 强连通（Strong Connectivity） | Forte connexité |
| 强连通分量（SCC） | Composante fortement connexe (CFC) |
| 弱连通（Weak Connectivity） | Connexité faible |
3. 图的遍历
| 中文 | 法语 |
|---|---|
| 深度优先搜索（DFS） | Parcours en profondeur (DFS) |
| 广度优先搜索（BFS） | Parcours en largeur (BFS) |
| 后序遍历（Postorder） | Ordre suffixe |
| 递归（Recursion） | Récursion |
4. 图论算法
| 中文 | 法语 |
|---|---|
| 算法（Algorithm） | Algorithme |
| 复杂度（Complexity） | Complexité |
| 迭代（Iteration） | Itération |
| 递归（Recursion） | Récursion |
| 数据结构（Data Structure） | Structure de données |
| 队列（Queue） | File d’attente |
| 栈（Stack） | Pile |
5. 特殊路径与性质
| 中文 | 法语 |
|---|---|
| 哈密顿路径（Hamiltonian Path） | Chemin hamiltonien |
| 哈密顿回路（Hamiltonian Cycle） | Circuit hamiltonien |
| 欧拉路径（Eulerian Path） | Chemin eulérien |
| 欧拉回路（Eulerian Cycle） | Circuit eulérien |
| 最短路径（Shortest Path） | Chemin le plus court |
| 生成树（Spanning Tree） | Arbre couvrant |
6. 图的操作
| 中文 | 法语 |
|---|---|
| 完全图（Complete Graph） | Graphe complet |
| 转置图（Transpose Graph） | Transposé d’un graphe |
| 子图（Subgraph） | Sous-graphe |
| 逆邻接（Predecessor） | Prédécesseur |
| 后继（Successor） | Successeur |
| 邻接矩阵（Adjacency Matrix） | Matrice d’adjacence |
| 邻接表（Adjacency List） | Liste d’adjacence |
Wechat
Alipay
