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

Graph Theory (5) : Trees and Their Properties

Graph Theory for Machine Learning (6) : Spanning tree algorithms

Graph theory for Machine Learning (7) : Connectivity

Graph theory (8) : Cutting edges, cutting sets, cutting points

5.1 Matching Concepts

Definition 5.1

Let G=(V,E)G=(V,E)G=(V,E) G=(V,E) be an undirected graph, and M⊆ \subseteq EM⊆E, in which any two edges are not adjacent, and we call MMM a match of GGG

The two endpoints of each edge in MMM are called paired

If the vertex VVV is associated with the middle edge of MMM, it is called the PENETRATION point of MMM; otherwise, it is called the non-penetration point of MMM

MMM penetration point: Vertex VVV at one of the two vertices that make up the matching edge

  • M = {v1v7 v2v3, v4v5} M = \ {v_1v_7 v_2v_3, v_4v_5 \} M = {v1v7 v2v3, v4v5} is a match

  • V1, v2, v3 and v4 and v5, v7v_1, v_2, v_3, v_4, v_5, v_7v1, v2, v3 and v4 and v5, v7 are MMM penetration point

  • V6, V8V_6, V_8v6, V8 are non-permeable points of MMM

Definition 5.2

Let MMM be a match of GGG

  • MMM is called an ideal match of GGG if it penetrates every vertex of GGG
  • If MMM is the match with the most edges in GGG, then MMM is called the maximum match of GGG

An ideal match is always a maximum match, but a maximum match is not always an ideal match

A necessary condition for a graph to have an ideal match is that it must have an even number of vertices

If a graph has an ideal match, then a graph with an even number of vertices does not necessarily have an ideal match

Definition 5.3

Let MMM be a match of GGG and PPP be a path in GGG

  • PPP is a MMM interleaved path if the edge of PPP alternates between MMM and E− me-me −M
  • A MMM interleaved path is called a MMM growable path if it starts and ends at MMM non-permeable points

Can grow meaning

Add the edges that are not in the match on MMM’s growable path to the match, remove the edges that originally belong to the match from the match (the matched edges on the growable path), so that the new match is 1 more than the original matched edges. Because in MMM growable path, both the starting point and the ending point are non-permeable points, the number of unmatched edges in the growable path must be the number of matched edges on the growable path +1. Then we change these unmatched edges into matched edges, and matched edges into unmatched 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