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

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 graphWeakly connected graph:
e e
Can reach
a a
, but
a a
Can’t reach
e e
.
a a
and
e e
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

Weakly connected graph: Any two vertices can be reachable without looking at the directionDisconnected graph:

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


c = v 1 v 2 . . . . v i v i + 1 . . . v j v j + 1 . . . v t v 1 ( t Or less n ) c=v_1v_2…. v_iv_{i+1}… v_jv_{j+1}… v_tv_1\quad( t\leq n)

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