Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card campaign. Click here for more details.”

@TOC

preface

Hello! Friend!!! ଘ(੭, ᵕ)੭ Nickname: Haihong Name: program monkey | C++ player | Student profile: Because of C language, I got acquainted with programming, and then transferred to the computer major, and had the honor to win some state awards, provincial awards… Has been confirmed. Currently learning C++/Linux/Python learning experience: solid foundation + more notes + more code + more thinking + learn English! Machine learning small white stage article only as their own learning notes for the establishment of knowledge system and review know why!

series

Graph theory (1) : The basic concepts of graphs

Graph theory (2) : Matrix representation of graphs

Graph theory for Machine Learning (3) : Paths and Connections

Graph Theory (4) : The connectivity of Directed Graphs

2.4 Numbers and their properties

2.4.1 Tree Features

Definition 2.10

Acyclic connected graphs are called trees and are denoted as TTT

The vertex VVV of T where D (v)= 1D (v)=1d(v)=1 is called a leaf

A graph in which each connected piece is a tree is called a forest or forest

Isolated vertices are called trivial trees

Different trees with six vertices, six of them

Theorem 2.4

GGG is a tree only if it is acyclic and there is a unique path between any two vertices

Proof:

Proof necessary: GGG is tree \Rightarrow$$G acyclic and has a unique path between any two vertices

Because GGG is a tree

So GGG is obviously acyclic and connected

For any two vertices u,vu,vu, V in V(G)V(G), there must be a path P1(u, V)P_1(u, V)P1(u, V)

If u, vu, vu, there is another path P2 between v (u, v) {P2 (u, v) indicates P1 (u, v)} P_2 (u, v) \ quad \ {P_2 (u, v) \ neq P_1 (u, v) \} P2 (u, v) {P1 P2 (u, v)  = (u, v)}

There must be an edge e=xye=xye=xy on P1P_1P1, but not on P2P_2P2

Or P2P_2P2, not P1P_1P1

However, P1∪P2−eP_1\ CUP P2-EP1 ∪P2− E is still connected. Let the union path be P(x,y)P(x,y)P(x,y).

P1∪P2−eP_1\ CUP P2-EP1 ∪P2− E connectivity Means that there is a union P2− E path between X, YX, YX, and Y after removing the EEE edge

So P(x,y)+eP(x,y)+eP(x,y)+e is a circle

This shows that GGG contains circles, which contradicts GGG as a tree

Only a unique path exists between any two points u, VU,vu, and v in GGG

Proof: GGG is acyclic and has a unique path between any two vertices \Rightarrow$$G is a tree

Because GGG is acyclic and there is a unique path between any two vertices

So GGG is a connected graph

A connected graph is one in which there is a path between any two vertices that can be reached

Suppose GGG contains a circle CCC

For any two vertices in CCC

There are two paths that connect these two vertices

Contradicts and has a unique path between any two vertices

If the hypothesis is not true, there is no cycle in GGG

So the GGG is tree

Acyclic connected graph tree

Theorem 2.5

GGG is necessary and sufficient condition of the tree is: GGG connected and ϵ (G) = argument (G) – 1 \ epsilon (G) = \ nu ϵ (G) – 1 (G) = argument (G) – 1

Proof:

The necessity: GGG is tree \ Rightarrow $$G connected and ϵ (G) = argument (G) – 1 \ epsilon (G) = \ nu ϵ (G) – 1 (G) = argument (G) – 1

If GGG is a tree, GGG must be connected

ϵ(G)=ν(G)−1\epsilon(G)= nu(G)-1ϵ(G)=ν(G)−1

Prove it by mathematical induction

Assume that when the v “nv” nv < n, ϵ (G) = argument (G) – 1 \ epsilon (G) = \ nu ϵ (G) – 1 (G) = argument (G) – 1

When v = v = 1 v = 1, ϵ (G) = 0 \ epsilon (G) = 0 ϵ (G) = 0, ϵ (G) = argument (G) – 1 \ epsilon (G) = \ nu ϵ (G) – 1 (G) = argument (G) – 1

When v = v = 2 v = 2, ϵ (G) = 1 \ epsilon (G) = 1 ϵ (G) = 1, ϵ (G) = argument (G) – 1 \ epsilon (G) = \ nu ϵ (G) – 1 (G) = argument (G) – 1

When v = nv = nv = n, arbitrary in GGG an edge (u, v) e ∈ e (G), e (u, v) \ in e (G), e (u, v) ∈ e (G)

The G0 = G – – – eG0 eG_0 = G = G e

Because there’s only one path between vertices U, VU,vu,v

So G0G_0G0 is disconnected and w(G0)=2w(G_0)=2w(G0)=2

Let the two connected slices in G0G_0G0 be G1,G2G_1,G_2G1,G2 respectively

Obviously, G1,G2G_1,G_2G1 and G2 are trees with no cycles and the number of vertices is less than NNN

Meet ϵ (G1) argument (G1) – 1, ϵ (G2) argument (G2) – 1 \ epsilon (G_1) = \ nu (G_1) – 1, \ epsilon (G_2) = \ nu ϵ (G_2) – 1 (G1) argument (G1) – 1, ϵ (G2) argument (G2) – 1

so ϵ (G) = ϵ (G1) + ϵ (G2) + 1 argument (G1) – 1 + argument (G2) – 1 + 1 = argument (G) – 1 \ epsilon (G) = \ epsilon (G_1) + \ epsilon (G_2) + 1 = \ + \ nu nu (G_1) – 1 (G_2) – 1 + 1 = \ nu ϵ (G) – 1 G ) = ϵ (G1) + ϵ (G2) + 1 = argument (G1) – 1 + argument (G2) – 1 + 1 = argument (G) – 1

namely


ϵ ( G ) = argument ( G ) – 1 \epsilon(G)=\nu(G)-1

The sufficiency: GGG connected and ϵ (G) = argument (G) – 1 ⇒ G \ epsilon (G) = \ \ Rightarrow nu (G) – 1 G ϵ (G) = argument (G) – 1 ⇒ G is a tree

Since trees are acyclic connected graphs, GGG is already a connected graph, so we only need to prove that it is acyclic

Prove it by mathematical induction

Assuming that v < nv “nv” n, GGG connected and ϵ (G) = argument (G) – 1 ⇒ G \ epsilon (G) = \ \ Rightarrow nu (G) – 1 G ϵ (G) = argument (G) – 1 ⇒ G acyclic was established

When v = v = 1 v = 1, ϵ (G) = argument (G) = 1-1-1 = 0 \ epsilon ⇒ G (G) = \ nu (G) – 1 = 1-1 = 0 \ Rightarrow G ϵ (G) = argument (G) = 1-1-1 = 0 ⇒ G is acyclic

When v = v = 2 v = 2, ϵ (G) = argument (G) – 2-1 = 1 = 1 \ epsilon ⇒ G (G) = \ nu (G) – 1 = 2-1 = 1 \ Rightarrow G ϵ (G) = argument (G) – 2-1 = 1 = 1 ⇒ G is acyclic

When v=nv=nv=n, then GGG has at least one uuu degree of 1

If δ≥2\delta \geq 2δ≥2, σ d(v)≥n⋅δ≥2n2\varepsilon=\sum d(v)\geq n\ cdot \delta\geq 2n2ε=∑d(v)≥n \varepsilon \geq ε≥n and ϵ(G)=ν(G)−1\epsilon(G)=\nu(G)-1ϵ(G)=ν(G)−1 contradictory so GGG has at least one vertex of degree 1 (cannot be 0, because GGG is connected, the minimum degree is at least 1)

Then G− ug-ug − U is connected

GGG is connected, and the number of uuu is 1, so GGG is still connected after uuu is removed

It can be deduced that: Epsilon (G – u) = epsilon (G) – 1 = (argument (G) – 1) – 1 argument (G – u) – 1 \ varepsilon -u (G) = \ varepsilon (G) 1 = (\ nu) (G) – 1-1 = \ nu epsilon -u (G) – 1 (G – u) = epsilon (G) – 1 = (argument (G) – 1) – 1 argument (G – u) – 1

Because for v “nv” nv < n, GGG connected and ϵ (G) = argument (G) – 1 \ epsilon ⇒ G (G) = \ \ Rightarrow nu (G) – 1 G ϵ (G) = argument (G) – 1 ⇒ G acyclic was established

So G− ug-ug −u is acyclic

And then GGG is acyclic

Adding a first-order vertex to an acyclic graph gives the new graph an acyclic graph

Theorem 2.6

The necessary and sufficient condition for GGG to be a tree is that GGG is connected and that G− EG-EG − E is disconnected for any EEE of GGG

Proof:

Proof necessity: GGG is tree \Rightarrow$$G connected, and for either side of GGG eEE, G− EG-eg − E is not connected

If GGG is a tree, it must be connected

E = uve = uve = uv

Because there’s only one path between u, VU, VU,v

Therefore, G− EG-EG − E is disconnected, and w(G−e)= 2W (g-e)= 2W (G−e)=2

GGG is connected, and for any eEE of GGG, G− EG-eg − E is not connected \Rightarrow$$G is a tree

Given that GGG is connected, it is necessary to prove that GGG is a tree

We just need to prove again that GGG has no cycles

Use proof by contradiction

Suppose GGG contains a circle CCC

If Eee belongs to an edge in the circle CCC

Then G− EG-EG − E is also connected

It contradicts what we already know

Therefore, the hypothesis is not true, GGG has no cycles

So GGG is a tree

Theorem 2.7

(1) the GGG is necessary and sufficient condition of the tree is GGG acyclic and epsilon argument (G) (G) – 1 \ varepsilon (G) = \ nu epsilon (G) – 1 (G) = argument (G) – 1

(2) the GGG is necessary and sufficient condition of the tree is GGG acyclic, for any uv ∉ e (G) = e (u, v ∈ v (G)) e = uv \ notin e (G) (u, v/v in (G)) = uv ∈ e/e (G) (u, v ∈ v (G)), G + eG + eG + e a circle

Corollary 2.7.1

Every nontrivial tree has at least two first-order vertices

Proof:

GGG is a nontrivial tree

Use proof by contradiction

Suppose you have less than two vertices at a time

Then there are at least v− 1V – 1V −1 vertices of a degree greater than or equal to 2

According to the handshake theorem, then


2 Epsilon. = ∑ v ∈ V ( G ) d ( v ) > 2 ⋅ ( v – 1 ) 2\varepsilon=\sum_{v\in V(G)}d(v)>2\cdot(v-1)

So if I simplify this, I get


Epsilon. > v – 1 \varepsilon > v-1

Because GGG is a tree, there is ε=v−1\varepsilon = V – 1ε= V −1

So the hypothesis is not valid

States that every nontrivial tree has at least two first-order vertices

Definition 2.11: Spanning tree

If TTT is a spanning subgraph of GGG and TTT is a tree, TTT is called the spanning tree of GGG

Corollary 2.7.2

The necessary and sufficient condition for GGG connectivity is that GGG grows trees

Proof:

Proof necessity: GGG connected \Rightarrow$$G Living tree

Suppose GGG is connected and TTT is the connected generated subgraph with the least number of edges in GGG

Graphs are connected, there must be subgraphs generated

If I have a circle in TTT

If eEE is removed, T−eT-eT− E is still connected

However, it contradicts the assumption that TTT is the connected generated subgraph with the least number of edges in GGG

Therefore, TTT has no circle

Because TTT is both the survival subgraph of GGG and a tree (connected and acyclic)

So TTT is the spanning tree of GGG

GGG connected \Rightarrow$$G living tree

Certificate sufficient: GGG living tree \Rightarrow$$G connected

Let TTT be a spanning tree of GGG

Then TTT must be connected

Because TTT is a generated subgraph of GGG and TTT is connected

This means that GGG must also be connected

2.4.2 Number of spanning trees

edge
e e The contraction of

Shrunking the EEE on one side of the GGG refers to deleting the EEE from the GGG and superposition the two endpoints of the EEE. The result is denoted as G⋅eG\cdot eG⋅e

Theorem 2.8: Find the number of spanning trees of graphs

Eee is the non-ring edge of connected graph GGG, and the number of different spanning trees τ(G)\tau(G)τ(G) of graph GGG is


tau ( G ) = tau ( G – e ) + tau ( G ⋅ e ) \tau(G)=\tau(G-e)+ \tau(G\cdot e)

Theorem 2.9: Caylay formula


tau ( K n ) = n n – 2 \tau(K_n)=n^{n-2}

conclusion

Description:

  • Refer to the textbook Graph Theory
  • With the book concept explanation combined with some of their own understanding and thinking

The essay is just a study note, recording a process from 0 to 1

Hope to have a little help to you, if there is a mistake welcome small partners correct