现代图论Ⅰ（图论概念） |
您所在的位置：网站首页 › 除号符号的笔顺是什么 › 现代图论Ⅰ（图论概念） |
现代图论Ⅰ（图论概念）
|
这篇文章首先发在bilibili。 前言：最近遇到了很多图论问题，于是计划读这本Modern graph theory, Bollobas (GTM184)。每天会发一部分提纲。今天的部分是1.1.1节 definitions。有过图论基础的朋友应该基本都知道，那我们的叙述就尽量简单但覆盖全面一点。 1. 基本定义（下汉语术语都由笔者捏造。在使用时将使用英文） 图(graph)、顶点(vertice)、边(edge)、连接(join)、相邻(neighbouring)、由…产生(be incident with)、子图(subgraph)、由…张成(spanned by)、阶(order)、大小(size)、同构(isomophic)、n-完全图(complete n-graph)、空图(empty graph)、补图(complement of)、开（闭）邻域((closed) neighbourhood)、度(degree)、行走(walk)、路(path)、独立的(independent)路、迹(trail)、圈(circle)、连通分量(complement)、最大\小度、最大连通子图、r分图(r-partite graph)、超图(hypergraph)、超图的生成图(incidence graph)、多重图(multigrpah)。几个术语的解释：这两个术语是比较陌生的 hypergraph: a pair (V,E) such that V∩E=∅ and E is a subset of P(V)， the power set of V. 翻译下就是这图的边（超边）可以和任意个顶点连接。 incidence graph of hypergraph: a bipartite graph with vertex classes V and E in which x∈V is joined to a hyperedge S∈E iff x∈S.把各个超边看作顶点和其包含的顶点连接形成的二分图。 例如说，此图（the fano plane)实际上是一个具有七条边和七个点的超图。其中大三角形的每条边过圆心的三条线段以及圆本身是边。这一超图的生成图就是标明每条边里有哪些顶点。定理：以后定理用TH标注 TH1. The edge set of a graph can be partiotioned into cycles iff every vertex has even degree. TH2. Every graph of order n and size greater than ⌊n^2/4⌋ contains a triangle.(用柯西不等式证明） 补充：握手引理(handshaking lemma)
∑
1
n
d
(
x
i
)
=
2
e
(
G
)
\sum_1^nd(x_i)=2e(G)
1∑nd(xi)=2e(G)补充说明 作为本篇第一节的补充，给出常用符号和几个定义的区分。
G
(
V
,
E
)
：
一
个
图
，
V
：
顶
点
集
，
E
:
边
集
。
G
[
W
]
:
G
的
子
图
，
顶
点
集
是
W
。
G(V,E)：一个图，V：顶点集，E:边集。G[W]:G的子图，顶点集是W。
G(V,E)：一个图，V：顶点集，E:边集。G[W]:G的子图，顶点集是W。
Γ
(
x
)
:
G
中
与
x
邻
接
的
点
集
(
缺
省
G
)
\Gamma(x):G中与x邻接的点集(缺省G)
Γ(x):G中与x邻接的点集(缺省G)
d
+
(
x
)
:
x
点
的
出
度
;
,
d
−
(
x
)
:
x
点
的
入
度
d^+(x):x点的出度;, d^-(x):x点的入度
d+(x):x点的出度;,d−(x):x点的入度
δ
(
G
)
最
小
度
顶
点
的
度
，
Δ
(
G
)
最
大
度
顶
点
的
度
\delta(G)最小度顶点的度，\Delta(G)最大度顶点的度
δ(G)最小度顶点的度，Δ(G)最大度顶点的度
P
l
是
任
意
一
个
l
长
的
P
a
t
h
，
C
l
是
一
个
任
意
l
长
的
圈
P_l是任意一个l长的Path，C_l是一个任意l长的圈
Pl是任意一个l长的Path，Cl是一个任意l长的圈 行走walk是顶点和边的交替序列
x
0
,
e
1
,
x
1
,
e
2
,
x
2
,
e
3
.
.
.
x
l
x_0,e_1,x_1,e_2,x_2,e_3...x_l
x0,e1,x1,e2,x2,e3...xl，其中
e
i
=
x
i
−
1
x
i
e_i=x_{i-1}x_i
ei=xi−1xi。从
x
0
到
x
l
x_0到x_l
x0到xl，称作
x
0
x_0
x0-
x
l
x_l
xl行走，一般记作
x
0
x
1
x
2
.
.
.
x
l
x_0x_1x_2...x_l
x0x1x2...xl. 边互不相同的walk被称为迹trail。首尾相接的迹被称为circuit回路。准确的说，回路是没有可区分的端点和方向的闭迹。 首尾相同，且除首尾外各个点均不同的行走成为圈circle。 一条路径path形如
V
(
P
)
=
{
x
1
,
x
2
,
.
.
.
,
x
n
}
,
E
(
P
)
=
{
x
0
x
1
,
x
1
x
2
,
.
.
.
,
x
l
−
1
x
l
}
V(P)=\{x_1,x_2,...,x_n\},E(P) = \{x_0x_1,x_1x_2,...,x_{l-1}x_l\}
V(P)={x1,x2,...,xn},E(P)={x0x1,x1x2,...,xl−1xl}也就是说它的顶点是互不相同的。
下面简单谈一下学习思路。 在所有的内容当中，最关键的是定义。——没有定义，任何内容都无从谈起。 对定义而言，有优劣之分。我们教科书当中绝大部分的定义都是well-defined，也就是说：没有歧义（基本）、符合逻辑、（例如说我们定义商映射，就一定要说明这的确是个映射。）并且一般具有着良好的数学结构、方便使用……在很多情况下，这表现为具有几何（直观）意义等等。 搞清定义，然后进行的下一步工作，就是证明定理。定理是由定义得到的、公认的深刻的结果。引理(lemma)辅助定理证明，或者是领域内基石性的结论（例如，区间套引理、zorn引理）。从定理自然得到推论(corollary)，推论和引理虽称不上定理，却也很重要。 定理证明则没有那么重要。有时是繁琐难懂的。只要掌握大概思路即可。 在数学书中第二个关键的部分就是习题。某些教材作者喜欢把大量结论放在习题当中。提议：闲着没事的时候，就去做习题吧。 现代图论pdf下载地址: http://library.lol/main/F5BCE767668334DD1019F9A7E4738351 |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |