| 失效链接处理 |
|
关于LKH算法的图论知识 PDF 下载
本站整理下载：
相关截图：
主要内容：
1 Trees
Today we’ll talk about a very special class of graphs called trees. Trees arise in all sorts
of applications and you’ll see them in just about every computer science class that you’ll
take at MIT. There are at least half a dozen ways to define a tree, but the simplest is the
following.
Definition. A tree is a simple 1 , connected, acyclic graph.
For example, a tree might look like this.
On the other hand, this is not a tree
and neither is this
1 Recall that we only consider simple graphs in this class, that is, graphs without loops or multiple edges.
2 Graph Theory III
Sometimes we’ll draw trees in a leveled fashion, in which case we can identify the top
node as the root, and every edge joints a “parent” to a “child”.
Parent
Child
Leaf
Root
The nodes at the bottom of degree 1 are called leaves.
Definition. A leaf is a node in a tree with degree 1.
For example, in the tree above there are 5 leaves. It turns out that no matter how we
draw a tree, every tree with more than 1 node always has some leaves.
Theorem 1. Every tree with more than 1 node has at least one leaf.
Proof. We prove the theorem by contradiction. Suppose it is not true. Then there exists
a tree T = (V,E) where every node has degree at least 2. Let P = v 1 ,v 2 ,...,v m be a
path of maximum length in T, i.e., there is no path with m + 1 or more nodes in T (recall
that all nodes in a path are distinct by definition). Note that we are implicitly using the
well-ordering principle here.
Since |V | ≥ 2 and T is connected, such a P exists and we have 2 ≤ m ≤ n. Since
T has minimum degree at least 2 by assumption, v m is joined to at least 2 nodes. In
particular, there is a node x 6= v m−1 such that {v m ,x} ∈ E. Since P has maximum length,
v 1 ,v 2 ,...,v m ,x is not a path, which means x = v i for some 1 ≤ i < m − 1. But then
v i ,v i+1 ,...,v m−1 ,v m ,v i is a cycle in T. But T is a tree, and so by definition contains no
cycle. This is a contradiction.
As it turns out, every tree has at least 2 leaves, which you’ll prove in the problem sets.
There is also a close correlation between the number of nodes and number of edges in a
tree. In the previous example we saw that N = 7 and E = 6. We also have the following
examples.
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
