图论的介绍(1)
·
一.简介
图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两
顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边
则用于表示两个事物间具有这种关系。
二.概念
图 (Graph) 是一个二元组 𝐺 = (𝑉 (𝐺), 𝐸(𝐺))。其中 𝑉 (𝐺) 是非空集，称为点集 (Vertex set)，对于 𝑉
中的每个元 素，我们称其为顶点 (Vertex) 或节点 (Node)，简称点；𝐸(𝐺) 为 𝑉 (𝐺) 各结点之间边的集合，称为边集 (Edge set)。
常用 𝐺 = (𝑉 , 𝐸) 表示图。
当 𝑉 , 𝐸 都是有限集合时，称 𝐺 为有限图。
当 𝑉 或 𝐸 是无限集合时，称 𝐺 为无限图。
图有多种，包括无向图 (Undirected graph)，有向图 (Directed graph)，混合图 (Mixed graph) 等
若 𝐺 为无向图，则 𝐸 中的每个元素为一个无序二元组 (𝑢, 𝑣)，称作无向边 (Undirected edge)，简称边 (Edge)， 其中 𝑢, 𝑣 ∈ 𝑉 。设 𝑒 = (𝑢, 𝑣)，则 𝑢 和 𝑣 称为 𝑒 的端点 (Endpoint)。
若 𝐺 为有向图，则 𝐸 中的每一个元素为一个有序二元组 (𝑢, 𝑣)，有时也写作 𝑢 → 𝑣，称作有向边 (Directed edge) 或弧 (Arc)，在不引起混淆的情况下也可以称作边 (Edge)。设 𝑒 = 𝑢 → 𝑣，则此时 𝑢 称为 𝑒 的起点 (Tail)，𝑣 称为 𝑒 的 终点 (Head)，起点和终点也称为 𝑒 的端点 (Endpoint)。并称 𝑢 是 𝑣 的直接前驱，𝑣 是 𝑢 的直接后继。
为什么起点是 Tail，终点是 Head？
边通常用箭头表示，而箭头是从“尾”指向“头”的。
若 𝐺 为混合图，则 𝐸 中既有向边，又有无向边。
若 𝐺 的每条边 𝑒𝑘 = (𝑢𝑘 , 𝑣𝑘 ) 都被赋予一个数作为该边的权，则称 𝐺 为赋权图。如果这些权都是正实数，就称 𝐺 为正权图。 图 𝐺 的点数 |𝑉 (𝐺)| 也被称作图 𝐺 的阶 (Order)。
形象地说，图是由若干点以及连接点与点的边构成的。
相邻
在无向图 𝐺 = (𝑉 , 𝐸) 中，若点 𝑣 是边 𝑒 的一个端点，则称 𝑣 和 𝑒 是关联的 (Incident) 或相邻的(Adjacent)。对 于两顶点 𝑢 和 𝑣，若存在边 (𝑢, 𝑣)，则称 𝑢 和 𝑣 是相邻的 (Adjacent)。
一个顶点 𝑣 ∈ 𝑉 的邻域 (Neighborhood) 是所有与之相邻的顶点所构成的集合，记作 𝑁(𝑣)。
一个点集 𝑆 的邻域是所有与 𝑆 中至少一个点相邻的点所构成的集合，记作 𝑁(𝑆)，即： 𝑁(𝑆) =
⋃ 𝑣∈𝑆 𝑁(𝑣)
度数
与一个顶点 𝑣 关联的边的条数称作该顶点的度 (Degree)，记作 𝑑(𝑣)。特别地，对于边 (𝑣, 𝑣)，则每条这样的边要 对 𝑑(𝑣) 产生 2 的贡献。 对于无向简单图，有 𝑑(𝑣) = |𝑁(𝑣)|。
握手定理（又称图论基本定理）：对于任何无向图 𝐺 = (𝑉 , 𝐸)，有 ∑𝑣∈𝑉 𝑑(𝑣) = 2 |𝐸|。
推论：在任意图中，度数为奇数的点必然有偶数个。
若 𝑑(𝑣) = 0，则称 𝑣 为孤立点 (Isolated vertex)。
若 𝑑(𝑣) = 1，则称 𝑣 为叶节点 (Leaf vertex)/悬挂点 (Pendant vertex)。
若 2 ∣ 𝑑(𝑣)，则称 𝑣 为偶点 (Even vertex)。
若 2 ∤ 𝑑(𝑣)，则称 𝑣 为奇点 (Odd vertex)。图中奇点的个数是偶数。
若 𝑑(𝑣) = |𝑉 | − 1，则称 𝑣 为支配点 (Universal vertex)。
对一张图，所有节点的度数的最小值称为 𝐺 的最小度 (Minimum degree)，记作 𝛿(𝐺)；最大值称为最大度 (Maximum degree)，记作 Δ(𝐺)。即：𝛿(𝐺) = min𝑣∈𝐺 𝑑(𝑣)，Δ(𝐺) = max𝑣∈𝐺 𝑑(𝑣)。
在有向图 𝐺 = (𝑉 , 𝐸) 中，以一个顶点 𝑣 为起点的边的条数称为该顶点的出度 (Out-degree)，记作
𝑑 +(𝑣)。以一 个顶点 𝑣 为终点的边的条数称为该节点的入度 (In-degree)，记作 𝑑 −(𝑣)。显然 𝑑 +(𝑣) + 𝑑−(𝑣) = 𝑑(𝑣)。
对于任何有向图 𝐺 = (𝑉 , 𝐸)，有： ∑ 𝑣∈𝑉 𝑑 +(𝑣) = ∑ 𝑣∈𝑉 𝑑 −(𝑣) = |𝐸|
若对一张无向图 𝐺 = (𝑉 , 𝐸)，每个顶点的度数都是一个固定的常数 𝑘，则称 𝐺 为𝑘- 正则图 (𝑘-Regular Graph)。
如果给定一个序列 a，可以找到一个图 G，以其为度数列，则称 a 是可图化的。
如果给定一个序列 a，可以找到一个简单图 G，以其为度数列，则称 a 是可简单图化的。
简单图
自环 (Loop)：对 𝐸 中的边 𝑒 = (𝑢, 𝑣)，若 𝑢 = 𝑣，则 𝑒 被称作一个自环。
重边 (Multiple edge)：若 𝐸 中存在两个完全相同的元素（边）𝑒1 , 𝑒2，则它们被称作（一组）重边。
简单图 (Simple graph)：若一个图中没有自环和重边，它被称为简单图。具有至少两个顶点的简单无向图中一 定存在度相同的结点。（鸽巢原理） 如果一张图中有自环或重边，则称它为多重图 (Multigraph)。
warning
在无向图中 (𝑢, 𝑣) 和 (𝑣, 𝑢) 算一组重边，而在有向图中，𝑢 → 𝑣 和 𝑣 → 𝑢 不为重边。
warning
在题目中，如果没有特殊说明，是可以存在自环和重边的，在做题时需特殊考虑。
路径
途径 (Walk)：途径是一个将若干个点连接起来的边的集合。形式化地说，途径 𝑤 是一个边的集合
{𝑒1 , 𝑒2 , … , 𝑒𝑘}， 这个边集需要满足条件：存在一个由点构成的序列 𝑣0 , 𝑣1 , … , 𝑣𝑘 满足 𝑒𝑖 的两个端点分别为 𝑣𝑖−1 和 𝑣𝑖。这样的路径可以 简写为 𝑣0 → 𝑣1 → 𝑣2 → ⋯ → 𝑣𝑘。通常来说，边的数量 𝑘 被称作这条途径的
长度（如果边是带权的，长度通常指路径 上的边权之和，题目中也可能另有定义）。
迹 (Trail)：对于一条途径 𝑤，若 𝑒1 , 𝑒2 , … , 𝑒𝑘 两两互不相同，则称 𝑤 是一条迹。
路径 (Path)（又称简单路径 (Simple path))：对于一条迹 𝑤，若其连接的点的序列中点两两不同，则称 𝑤 是一 条路径。
回路 (Circuit)：对于一个迹 𝑤，若 𝑣0 = 𝑣𝑘，则称 𝑤 是一个回路。
环/圈 (Cycle)（又称简单回路/简单环 (Simple circuit))：对于一个回路 𝑤，若 𝑣0 = 𝑣𝑘 是点序列中唯一重复出现 的点对，则称 𝑤 是一个环。
warning
关于路径的定义在不同地方可能有所不同，如，“路径”可能指本文中的“途径”，“环”可能指本文中的“回 路”。如果在题目中看到类似的词汇，且没有“简单路径”/“非简单路径”（即本文中的“途径”）等特殊说明，最 好询问一下具体指什么。
子图
对一张图 𝐺 = (𝑉 , 𝐸)，若存在另一张图 𝐻 = (𝑉 ′ , 𝐸′ ) 满足 𝑉 ′ ⊆ 𝑉 且 𝐸′ ⊆ 𝐸，则称 𝐻 是 𝐺 的子图 (Subgraph)，
若对 𝐻 ⊆ 𝐺，满足 ∀𝑢, 𝑣 ∈ 𝑉 ′，只要 (𝑢, 𝑣) ∈ 𝐸，均有 (𝑢, 𝑣) ∈ 𝐸′，则称 𝐻 是 𝐺 的导出子图/诱导子图 (Induced subgraph)。
容易发现，一个图的导出子图仅由子图的点集决定，因此点集为 𝑉 ′ (𝑉 ′ ⊆ 𝑉 ) 的导出子图称为 𝑉 ′ 导出的子图，记 作 𝐺 [𝑉 ′ ]。
若 𝐻 ⊆ 𝐺 满足 𝑉 ′ = 𝑉 ，则称 𝐻 为 𝐺 的生成子图/支撑子图 (Spanning subgraph)。
显然，𝐺 是自身的子图，支撑子图，导出子图；空图是 𝐺 的支撑子图。原图 𝐺 和空图都是 𝐺 的平凡子图。
如果一张无向图 𝐺 的某个生成子图 𝐹 为 𝑘- 正则图，则称 𝐹 为 𝐺 的一个𝑘- 因子 (𝑘-Factor)
如果有向图 𝐺 = (𝑉 , 𝐸) 的导出子图 𝐻 = 𝐺 [𝑉 ∗ ] 满足 ∀𝑣 ∈ 𝑉 ∗ , (𝑣, 𝑢) ∈ 𝐸，有 𝑢 ∈ 𝑉 ∗，则称 𝐻 为 𝐺 的一个闭合 子图 (Closed subgraph)。
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)