“This is the 31st day of my participation in the First Challenge 2022. For details: First Challenge 2022.”
@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
2.2 Connectivity of digraphs
Definition 2.5
In the directed graph D=(V,A,ψ)D=(V,A, psi)D=(V,A,ψ) :
(1) set bits (ai) = (vi – 1, vi) \ psi (a_i) = (v_ {1} I -, v_i) bits (ai) = (vi – 1, vi), sequence v0a1v1a2v2,… ,akvkv_0a_1v_1a_2v_2,… ,a_kv_kv0a1v1a2v2,… ,akvk is called a directed path from V0V_0v0 to VKVK
(2) A directed path whose arc is not repeated but whose vertices can be repeated is called a directed path
(3) A directed path with non-repeating vertices is called a directed path
(4) A directed path with overlapping starting point and ending point is called a directed circle
(5) A directed path whose starting point and ending point overlap is called a directed loop
2. A directed path that may repeat vertices or edges and requires only that one point be passed to another: V1e1v2e2v3e3v2e4v4v_1e_1v_2e_2v_3e_3v_2e_4v_4v1e1v2e2v3e3v2e4v4 (vertex v2V_2V2 is repeated, but there is no edge repetition) A directed path can be as long as the vertices are not repeated: For example, v1e1v2E3v3V_1e_1V_2E_3V_3V1E1V2E3V3 directed circle requires that the starting point and ending point be the same point on the basis of directed path. In fact, there are still no repeated vertices in the circle
Definition 2.6
In a directed graph:
(1) If there is a directed path from vertex UUu to VVV, it is said that vertex UUu can reach VVV
(2) If the direction of some arcs can be changed from vertex UUu to VVV, it is said that vertex UUu and VVV are connected, and that there is a half path between UUu and VVV
Definition 2.7
In directed graph DDD, for any two vertices vi,vj:v_i,v_j:vi,vj:
(1) If VIV_IVI and VJV_Jvj can reach each other, D is called strongly connected graph
(2) If VIV_IVI can reach VJV_JVj, or VJV_JVj can reach VIv_IVI, DDD is called a unidirectional connected graph
(3) If VIV_IVI and VJV_JVj are connected, DDD is called weakly connected graph
(4) Graphs that do not meet the above conditions are called disconnected graphs
Strongly connected graph
Can reach
, but
Can’t reach
.
and
No one can reach each other, but satisfying one vertex can reach the other
Compared to strongly connected graphs, the requirement is much lower and only one of any two vertices can reach the other, not each other
clearly
- Strongly connected graphs must also be unidirectional and weakly connected graphs
- A unidirectional connected graph must also be a weakly connected graph
Definition 2.8
In directed graph DDD:
(1) The directed loop through all vertices is called the complete loop of DDD
(2) The directed path through all vertices is called DDD complete path
(3) A semi-path through all vertices is called a complete semi-path of DDD
Theorem 2.2
A directed graph DDD is strongly connected if and only if it has a complete loop
prove
Necessity of proof: Directed graph D is a strongly connected vector with a complete circuit
Suppose graph D has n vertices: v1,v2… ,vnv_1,v_2,… ,v_nv1,v2,… ,vn
Because D is strongly connected
Therefore, there must be a directed path between V1V_1V1 and V2V_2V2, which is set as W1W_1W1
In the same way
There must be a directed path between V2V_2V2 and V3V_3V3, W2W_2W2
.
Vn − 1V_ {n-1} THERE must be a directed path between VN −1 and VNV_NVN. Wn-1w_ {n-1} Wn-1
There must be a directed path between VNV_nvn and V1V_1V1, WnW_nWn
So W1W2,… ,WnW_1W_2,… ,W_nW1W2,… ,Wn can represent a path from vertex V1v_1v1 to vnv_nvn and finally back to v1v_1v1, which passes through all vertices of D, and the starting point and ending point coincide, indicating a complete loop
To sum up: The fact that directed graph D is strongly connected indicates that graph D has a complete loop
Evidence Sufficiency: Directed graph D has a complete circuitry
Since figure D has a complete loop, let’s call it C
So any two vertices vi,vjv_i, vjvi,vj in D must be in the complete loop C
There is a path from vertices viv_ivi to vjv_jvj: vivi+1… vjv_iv_{i+1}… v_jvivi+1… vj
There is a path from vertex Vjv_jvj to viv_ivi: VJVJ +1… vtv1v2… viv_jv_{j+1}… v_tv_1v_2… v_ivjvj+1… vtv1v2… vi
So any two vertices vi,vjv_i, vjvi,vj, are reachable to each other
Figure D is strongly connected
Corollary 2.2.1
A directed graph is unidirectionally connected if and only if it has a complete path
Corollary 2.2.2
A directed graph is weakly connected if and only if it has a complete semi-path
Definition 2.9
In the directed graph D, the largest strongly connected subgraph D1D_1D1 is called the strongly connected slice or strongly connected universal graph of D
The maximum strongly connected subgraph D1D_1D1 means that D1D_1D1 is a strongly connected subgraph and D no longer contains a strongly connected subgraph of D1D_1D1
Theorem 2.3
Each vertex of the directed graph D must be in one and only one strongly partitioned graph
Reasoning 2.3
The strong partitioned graphs of directed graphs have neither common vertices nor common edges
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
