“This is the 30th 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

2.1 Paths and Connectivity

Definition 2.1

In undirected graph G = (V, E, bits) G = (V, E, \ psi) G = (V, E, bits), set bits (ei) argument I – 1 argument I (I = 1, 2,… , k) \ psi (e_i) = \ nu_ {1} I – \ nu_i (I = 1, 2,… , k) bits (ei) argument I – 1 argument I (I = 1, 2,… ,k):

• Sequence argument 0 e1 argument 1 e2 argument 2… Ek argument k \ nu_0e_1 \ nu_1e_2 \ nu_2… E_k \ nu_k argument 0 e1 argument 1 e2 argument 2… Ek argument called from argument \ 0 k nu_0 argument 0 to argument k \ nu_k argument k a pathway, remember to W argument 0 argument kW_ {\ nu_0 \ nu_k} W argument argument 0 k
• A path whose edges are not repeated but whose vertices can be repeated is called a path and is denoted Tν0νkT_{\nu_0\nu_k}Tν0νk
• A path whose vertices do not repeat is called a path, denoted as Pν0νkP_{\nu_0\nu_k}Pν0νk

In a simple graph, a path can be represented as a sequence of vertices
$\nu_0\nu_1\nu_2,… ,\nu_k$.

Obviously, if there is a path between UUu and VVV, then there must be a path between UUu and VVV

Definition 2.2

Let GGG be an undirected graph:

• If there is a path PuvP_{uv}Puv in GGG, then vertex UUu and VVV are connected in GGG
• GGG is connected if any two vertices in GGG are connected
• The largest connected subgraph of GGG is called the connected slice of GGG (or the sub-graph of GGG), and w(G) W (G)w(G) represents the number of connected slices of GGG

GGG is a connected graph if and only if w(G)=1w(G)=1w(G)=1

Example 2.1

There are 2N2N2N switchboards, each of which has a direct line with at least NNN switchboards, so any two of them can talk to each other

prove

The problem can be converted to: a simple graph of 2n2n2n vertices, denoted as GGG, each vertex of degree is at least NNN, then GGG is connected

First assume that graph GGG is not connected, then GGG contains at least two connected slices

We choose the connected slice with fewer vertices, and we can get that the maximum number of vertices in the connected slice is NNN

There are 2N2N2n, divided into two parts, the average score is NNN and NNN, the number of vertices in any connected slice is NNN if it is not the average score, there must be one vertices greater than NNN and one less than NNN, then the number of vertices in the connected slice that is less than NNN is also less than NNN. In sum, When selecting the connected slice with fewer vertices, the number of vertices is at most NNN (less than or equal to NNN)

In this connected slice, the maximum degree of vertices can only be N − 1n-1N −1, and the degree of each vertex is at least NNN, which is contradictory

When the number of vertices is NNN, the maximum number of vertices is n−1n-1n−1 because a vertex can only be connected to other n−1n-1n−1 vertices at most

Therefore, the hypothesis is not valid

Description: A simple graph with 2n2N2n vertices is called GGG, and if the degree of each vertex is at least NNN, GGG is connected

Example 2.3

If there are only two odd vertices in the graph, they must be connected

prove

Proof by contradiction, suppose these two vertices are not connected

It must belong to two different connected slices

Analyze one of the connected slices:

• Because there are only two odd vertices in the graph
• The two odd vertices belong to different connected slices
• Then one of the connected slices must contain only one odd vertex
• This contradicts the fact that in any graph the number of odd vertices must be even

Therefore, the hypothesis is not valid

Note: If there are only two odd vertices in the graph, the two vertices must be connected

Definition 2.3

(1) The path where the starting point and ending point coincide is called a circle, denoted as CkC_kCk, where KKK is the number of edges contained in the circle

(2) The number of edges contained in a path (or circle) is called the length of the path (or circle)

(3) the circle with odd length is called the odd circle, denoted as C2n+1C_{2n+1}C2n+1; The circle of even length is called even and is denoted C2nC_{2n}C2n

Definition 2.4

The length of the shortest path from vertex UUu to VVV in GGG is called the distance between uuu and VVV, denoted as d(u,v)d(u,v)d(u,v)

Theorem 2.1

GGG is a bipartite graph if and only if GGG does not contain odd cycles

prove

Proof necessity: GGG is bipartite graph \quad\Rightarrow\quad$$G without odd circles

If GGG has no circle, it must have no circle

If there are circles in GGG, assume C=v0v1v2…. Vkv0 (starting point and end point are v0) C=v_0v_1v_2…. V_kv_0 (start point and end point are v_0) C=v0v1v2…. Vkv0 (starting point and ending point are v0)

If v0∈Xv_0\in Xv0∈X, then

$v_0,v_2,v_4,… v_0\in X$

$v_1,v_3,v_5,… ,v_k\in Y$

V0v1v_0v_1v0v1 indicates that v0, V1V_0, v_1v0 and v1 are adjacent, so they belong to XXX and YYY respectively

You can see that KKK is odd.

So the length of this circle is going to be k plus 1k plus 1k plus 1, even

It means it’s not an odd circle

To sum up, GGG is a bipartite graph \Rightarrow$$G without odd circles

---

GGG does not contain odd circle \quad\Rightarrow\quad$$G is a bipartite graph

Assume that GGG is a connected graph with no circles in GGG

If v1∈V(G)v_1\in V(G)v1∈V(G), let

$X=\{v | v\in v (G),d(v_1,v) is even \}$

$Y=\{v | v\in v (G),d(v_1,v) is odd number \}$

D (v1,v)d(v_1,v) D (v1,v) represents the distance from vertex VVV to vertex v1v_1v1 (the length of the shortest path). Because GGG is a connected graph, all vertices can be connected with v1v_1v1 and have distance, so it can be divided into two parts according to the parity of distance

Let u, V ∈Xu, V \in Xu, V ∈X, PPP is the shortest path from V1V_1v1 to uuu, and QQQ is the shortest path from v1v_1v1 to VVV

Assuming MMM is the last common point of P, QP, QP, and Q, then P1(v1,m)P_1(v_1,m)P1(v1,m) to Q1(v1,m)Q_1(v_1,m)Q1(v1,m) is equal in length

If the path P, QP, QP, Q no common path, then ∣ P1 ∣ = ∣ Q1 ∣ = 0 | P_1 | = | Q_1 | = 0 ∣ P1 ∣ = ∣ Q1 ∣ = 0, and length If there is a common path, then, obviously, ∣ P1 ∣ = ∣ Q1 ∣ | P_1 | = | Q_1 | ∣ P1 ∣ = ∣ Q1 ∣, isometric

P2 (m, n) and Q2 (m, u) P_2 (m, n), Q_2 (m, u) P2 (m, n) and Q2 (m, u) for P, QP, QP, Q china-africa common path

According to the path definition, there are

And ∣ P1 ∣ = ∣ Q1 ∣ | P_1 | = | Q_1 | ∣ P1 ∣ = ∣ Q1 ∣, P1, Q1P_1, Q_1P1, Q1 have the same parity

Because ∣ P ∣ ∣ Q ∣ P | | and | | Q ∣ P ∣, ∣ Q ∣ is even, and P2, Q2P_2, Q_2P2, Q2 have the same parity

If P1=Q1P_1= q1p1 =Q1 is odd and P1+P2= even P_1+P_2= even P1+P2= even Q1+Q2= even Q_1+Q_2= even Q1+Q2= even P2=Q2 must be odd and P_2=Q_2 must be odd P2=Q2 must be odd, If P1=Q1 is even and P_1=Q_1 is even and P1=Q1 is even, then P2=Q2 must be even and P_2=Q_2 must be even and P2=Q2 must be even so, P2,Q2P_2, q2p2,Q2 have the same parity

If u,vu,vu,v are adjacent, then P2,Q2,uvP_2,Q_2,uvP2,Q2,uv must have an odd length

P2, Q2P_2 Q_2P2, Q2 have the same parity But whether it is odd or even number, ∣ P2 ∣ + ∣ Q2 ∣ | P_2 | | + Q_2 | ∣ P2 ∣ + ∣ Q2 ∣ is even Then add a d (u, v) = 1 d (u, v) = 1 d (u, v) = 1: an odd number, the result must be an odd number

This contradicts the assumption that GGG has no loop, so uvuvuv is definitely not adjacent

Because u,v∈Xu,v\in Xu,v∈X, it means that any two vertices in XXX are not adjacent

Similarly, any two vertices in YYY are not adjacent

To sum up, GGG is a bipartite graph divided into (X,Y)(X,Y)

Note: The proof of adequacy is a little lax. At the beginning, GGG was assumed to be a connected graph and GGG was not proved to be a disconnected graph

Example 2.3

In a simple graph GGG, if the degree of each vertex of GGG is 2, then GGG contains a circle

prove

Let P(u,v)P(u,v)P(u,v) be the longest path in graph G

Path: Vertex requirements cannot be repeated Simple graph: acyclic, double-edged Ring: Both endpoints of an edge are a vertex double-edged: there is more than one edge between two vertices, and these edges are called double-edged

Because every vertex in G has at least degree 2

So there’s at least one edge e associated with v, and let’s call the other end of E w

If WWW is notin path P(u,v), namely w∉P(u,v) (w not on path P(u,v)) w\notin P(u,v) (w not on path P(u,v))

So the longest path in figure G is actually
$P(u,w)$

But this contradicts the hypothesis

So w must be on the path P(u,v)

So G has a circle in it

To sum up: in a simple graph GGG, if the degree of each vertex of GGG is 2, then GGG contains a circle

Example 2.4

GGG is a simple graph, each vertex degree is not less than 3, then GGG has even cycles

prove

Note: according to the statement, we only need to prove the existence of an even cycle in G

Where v0, v1, v2,… ,vmv_0,v_1,v_2,… ,v_mv0,v1,v2,… ,vm is the longest path in G

Because the degree of any vertex is greater than or equal to 3

Then v0v_0v0 is associated with at least two endpoints vi,vj(I ≠j)v_i,v_j(I \neq j)vi,vj(I =j)

From Example 2.3, it can be seen that the two endpoints vi,vjv_i,v_jvi,vj must be in the path v0,v1,v2… ,vmv_0,v_1,v_2,… ,v_mv0,v1,v2,… , i.e. 1< I

When either I or JI or ji or j is odd, let’s say iii is odd

So v0v1v2,… ,viv_0v_1v_2,… ,v_iv0v1v2,… ,vi and viv0v_IV_0viv0 the length of the resultant circle is: I +1i+1i+1, it is an even circle

D (where v0, di) = id (v_0 d_i) = id (where v0, di) = I, is an odd number of d (vi.) where v0 = 1 d (v_i. V_0) = 1 d (vi.) where v0 = 1, D (where v0, di) + d (vi, where v0) d (v_0 d_i) + d (v_i, v_0) d (where v0, di) + d (vi, where v0) for even

当
$I, j$It’s all even numbers

Observation by vi, vi + 1,… ,vjv_i,v_{i+1},… ,v_{j}vi,vi+1,… ,vj and v0vi, v0VjV_0V_i, v_0v_jv0vi, v0vj

The length is: (j− I)+1+1(J-i)+1+1(j− I)+1+1, the result is even, that is, GGG also has even cycles

In conclusion,
$G$Is a simple graph, each vertex degree is not less than 3, then
$G$There are even

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