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
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
So if I simplify this, I get
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
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
Theorem 2.9: Caylay formula
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