计算机数学基础⑤(Graphs)

计算机数学基础⑤(Graphs)

文章目录

​​Graph Theory(图论)​​​​Graphs: Useful Concepts(图：有用的概念)​​​​Walks and connectedness(走法和连通性)​​

Graph Theory(图论)

Definition 5.1. Intuitively, a graph is just a way of modeling a collection of objects and the connections between them.

直观地说，图只是为对象集合及其之间的连接建模的一种方式。

Definition 5.2. A simple undirected loopless graph G consists oftwo things: a collection V of vertices, and another collection E ofedges, which we think of as distinct unordered pairs of distinct elementsin V . think of the vertices in a graph as the objects we’re studying, and the edges in a graph as a way to describe how those objects areconnected. describe an edge connecting a pair of vertices a, b in our graph G, weuse our set language from earlier and write this as {a, b}. We say thata and b are the endpoints of the edge {a, b} when this happens.

一个简单的无向无环图G由两部分组成:顶点的集合V，和边的集合E，我们认为它们是V中不同元素的不同的无序对。我们把图中的顶点看作是我们正在研究的对象，而图中的边则是描述这些对象之间如何连接的一种方式。 为了描述图G中连接顶点对a, b的一条边，我们使用之前的集合语言，将其写成{a, b}。我们说a和b是边{a, b}的端点。

例如：

根据以上的定义我们可以画出几种符合要求的图：

Definition 5.3. A simple graph with loops is just like a simple graphG, except we no longer require the pairs of elements in E to be distinct;that is, we can have things like {v, v} ∈ E. multigraph is a simple graph, except we allow ourselves to repeatedges in E multiple times; i.e. we could have three distinct edges e1, e2, e3 ∈E with each equal to the same pair {x, y}.A directed graph is a simple graph, except we think of our edges asordered pairs: i.e. we have things like x → y ∈ E, not {x, y}.You can mix-and-match these definitions: you can have a directed graphwith loops, or a multigraph with loops but not directions, or pretty muchanything else you’d want!

​​带有循环的简单图​​就像简单图G一样，只是我们不再要求E中的元素对是不同的;也就是说，我们可以有{v, v}∈E。

​​多重图​​是一个简单的图，除了我们允许我们自己多次重复E中的边;也就是说，我们有三条不同的边e1 e2 e3∈E和每一个都等于相同的一对{x, y}。

一个​​有向图​​是一个简单的图，除了我们认为我们的边是有序对:例如，我们有x→y∈E，而不是{x, y}。

您可以混合使用这些定义:您可以使用带有循环的有向图，或者使用带有循环但没有方向的多重图，或者几乎任何您想要的东西!

我们可以看几个示例图片：

接下来列举出一些较为特殊的图：

Definition 5.4. The complete graph on n vertices Kn is defined forany positive integer n as follows: take n vertices., take every possible pair of distinct vertices, and connect them with an edge! We drawseveral examples at right. this sense, a complete graph is a graph in which we have as manyedges as is possible for a graph on n vertices.

对于任意正整数n, n个顶点上的完整图Kn定义如下:取n个顶点。现在，取每一对可能的不同顶点，并将它们与一条边连接起来!

从这个意义上说，一个​​完整图​​是这样一个图，它有尽可能多的边对于一个有n个顶点的图来说。

例如：

Definition 5.6. The cycle graph on n vertices Cn is defined for anyinteger n ≥ 3 as follows: take n vertices, and label them 1, 2, . . . n.,draw edges {1, 2},{2, 3}, . . . until you get to the last edge {n− 1, n}; thenconnect this up into a closed cycle by drawing {n, 1} as an edge as well.

对于任意n≥3的整数，定义n个顶点Cn上的循环图如下:取n个顶点，标为1,2，…n.现在，绘制边{1,2}，{2,3}，…直到最后一条边{n−1,n};然后将其连接成一个闭合循环，将{n, 1}也画成一条边。

例如：

Graphs: Useful Concepts(图：有用的概念)

Definition 5.7. Take a graph G. say that two vertices a, b in G areadjacent if the edge {a, b} is in G. say that a and b are neighborsif they are adjacent.

以一个图G为例，如果边{a, b}在G中，我们说G中的两个顶点a, b是相邻的，我们可以说a，b两个顶点是neighbors

Definition 5.8. Take a graph G, and a vertex v in G. say that thedegree of v, written deg(v), is the number of edges that contain v as anendpoint.

以一个图G和G中的一个顶点v为例，我们说v的度，写成deg(v)，是包含v作为端点的边的数量。

例如：对于如下的图：

顶点a的度为0，顶点b的度为1，顶点d和e的度为2，顶点c的度为3。

Claim 5.1. (The “degree-sum formula,” or “handshaking theorem.”)Take any graph G., the sum of the degrees of all of the vertices inG is always two times the number of edges in G.

取任意图G，所有顶点的度数之和总是的边数的两倍。

Claim 5.2. You cannot have a graph on seven vertices in which thedegree of every vertex is 3.

你不可能有一个有七个顶点的图每个顶点的度数都是3。

Walks and connectedness(走法和连通性)

Definition 5.9. In a graph G, we define a walk of length n as anysequence of n edges from G of the form{v0, v1}, {v1, v2}, {v2, v3}, . . . , {vn−1, vn}.We say that this walk starts at v0 and ends at vn. say that a walk is a circuit or closed walk if it starts where it ends;i.e. if v0 = vn. say that a walk is a path if it does not repeat any vertices, with thefollowing exception: if the first and last vertex of path are the same andall of the others are distinct, we allow this to be a path as well. thislast case, we call our walk a cycle. often describe a walk by just listing its vertices in order: i.e.v0 → v1 → v2 → . . . → vn−1 → vnis a valid way to describe a walk.

在图G中，我们定义了一个长度为n的步长，即从图G出发的任意n条边的序列

对于： {v0, v1}, {v1, v2}, {v2, v3}, . . . , {vn−1, vn}.

这段路程从v0开始，到vn结束。 如果步行从终点开始，我们就称其为环行或封闭的步行;即如果v0 = vn。 我们说一次行走是一条路径，如果它没有重复任何顶点，除了以下的例外:如果路径的第一个和最后一个顶点是相同的，并且所有其他的顶点是不同的，我们允许它也是一条路径。在最后一种情况下，我们称之为步行周期。

我们经常通过按顺序列出它的顶点来描述一次行走。 v0→v1→v2→…→vn−1→vn是描述步行的有效方法。

注意，行走可以重复边和顶点!

Definition 5.10. Given a graph G, we say that G is connected if forevery pair of vertices a, b in G, there is a path from a to b in G.

给定一个图G，如果对于G中的每一对顶点a, b，在G中有一条从a到b的路径,我们说G是连通的，

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。