Basic concepts of graph theory

The basic concepts of graph theory Important definitions ：

1、 Directed graph ： Every edge is a graph with a directed edge . 

  Undirected graph ： Every edge is a graph of undirected edges .

Mixed picture ： A graph with both directed and undirected edges .

  Self return ： The two ends of an edge coincide .

  Multiplicity ： If there are several edges between two vertices , Call these edges parallel , Two vertices a,b The number of parallel edges between becomes （a,b） The multiplicity of .

  Multiple pictures ： Graphs with parallel edges . 

  Simple picture ： Graphs without parallel edges and self loops . 

Be careful ！ An undirected edge can be replaced by a pair of opposite directed edges , So an undirected graph can be transformed into a directed graph in this way . 

Directional graph ： If for an undirected graph G Each undirected edge of the a graph specifies a direction D. It's called G Directional graph .

  Base map ： If the direction of each directed edge of a directed graph is removed , Undirected graph G It's called D Base map . 

Inverse graph ： Put a directed graph D Each edge of the graph is reversed, and the resulting graph is called D The inverse of .

  Empowerment map ： Each edge is assigned a value .

  The degree of ： The number of edges connected to the vertex is called the degree of the fixed point , The number of edges with the fixed point as the starting edge is the degree . 

The degree of ： Take the number of edges with the fixed point as the final edge as the depth . （ special ！ A fixed point with zero degree is called an outlier . The point with one degree is the suspension point .  ）

Undirected complete graph ： stay K An undirected graph of order is called if any two points have a boundary connection Undirected complete graph .

Kn Completely directed graph ： stay K A digraph of order is called a graph if any two points are connected by directed edges with opposite directions Completely directed graph .

Competition chart ： In a degree graph, if its base graph is undirected complete graph , Then the directed complete graph is Competition chart .

  Be careful ！n The number of edges of a directed complete graph of order is n The square of ; The number of edges of an undirected complete graph is n(n-1)/2. 

 2、 The following two operations are described in the call diagram ：

① Edge deletion ： Delete an edge in the graph but keep the end of the edge .

② Delete point ： Delete a point in the graph and all edges connected to it .

  Subgraphs ： Delete an edge or a bit of the remaining graph . 

Generating subgraphs ： Delete only the edges but not the dots .

Master subgraph ： The subgraph obtained by deleting a point in the graph is called the master subgraph . 

Make up a picture ： Let it be an inter order simple undirected graph , After adding some edges in , Can make a complete graph of order ; A graph consisting of these vertices with edges added is called a complement graph . 

Important theorem ： 

  Theorem 5.1.1 Set up a picture G Yes. n vertices m Directed graph of strip edge , The point set V={v,v,….,v} deg+(vi)=deg-(vi)=m 

Theorem 5.1.2 Set up a picture G Yes. n vertices m Undirected graph of strip and edge , The point set V={v,v,v,……,v} deg(vi)=2m

  inference In the undirected graph , The number of vertices whose degree is the product is even . Path and the shortest path of the weighted graph 1 Paths and loops  

  Basic concepts ： 

  The length of the passage ： The number of edges in the path .

  loop ： If the starting point in the path is the same as the ending point .

  Simple access ： If each side of the path is different . 

Basic access ： If the vertices in the path are different . obviously （ The basic path must be a simple path , But the simple path is not necessarily the basic path ） 

Can be up to ： In the figure G If there is one v To d The passage is called from v To d It's reachable .

connected ： If any two points in an undirected graph are reachable , Otherwise, it is disconnected . 

  Strong connectivity ： In a directed graph, if any two points are mutually reachable . 

  Unidirectional connectivity ： If there is a path of any two points in a directed graph . 

  Weakly connected ： In a directed graph, if its base graph is connected .

power ： The number of points or edges of a graph indicating certain information . 

  Empowerment map ： Graphs with weights . 

3、 Algorithm for the shortest path problem of weighted graph ：

First, find the shortest path to a certain point , Then use this result to determine the shortest path to another point , Go on like this , Until the shortest path is found . 

indicators ： set up V Is the point set of a graph ,T yes V Subset , And T contain z But it doesn't include a, said T For the target set . In the target set T Take any point in t, from a To t But not through the target set T In all paths at other points in , The smallest of the sum of edge weights is called a point t Relationship with T The index of is recorded as DT(t). Graphs and matrices The difference between the two ：A·A The meaning of the elements in ： If and only if a and a All are 1 when ,a a =1 and a and a All for 1 It means figure G There is a side in (v ,v ) and (v ,v ).

So we can draw the following conclusion ：

1、 From the top v and v The leading edge , If the joint ends at some vertex , Then the number of these termination vertices is b Value ; Especially for b , Its value is v The degree of . A ·A The meaning of the elements in ： If and only if a and a All for 1 when ,a a =1, This means that there are edges in the graph (v ,v ) and (v ,v ).

2、 Edges from certain points , If both ends at v and v , Then the number of such vertices is the value of . Especially for b , Its value is v The degree of . power A The meaning of the elements in ： When m=1 when ,a The elements in =1, Indicates that there is an edge (v ,v ), Or from v To v There is a path with a length of one . A Medium element a From v To v The length of is m The number of all paths of .

  Olatu The main definition is ： If there is a circuit in the graph that passes through one edge of the graph once and only once , This circuit is called Euler circuit , A graph with Euler loop is called Olatu . If there is a path through each edge of the graph once and only once , This path is called Euler pathway , A graph with Eulerian paths is called Semi Euler graph . 

  Main theorem ：

An undirected connected graph is an Euler graph if and only if the degree of each point in the graph is even .

  An undirected connected graph is a semi Eulerian graph if and only if there are at most two odd degree points in the graph .

  Set up a picture G Is a directed connected graph , chart G Is an Euler graph if and only if the in degree and out degree of each vertex in the graph are equal . 

  Set up a picture G Is a directed connected graph , chart G Is a semi Eulerian graph if and only if there are at most two vertices , The in degree of one of the vertices is larger than its out degree 1, The other vertex has less in degree than its out degree 1; Other vertices have the same in and out degrees .

  Hamilton The main definition is ： If the figure G There is a pass through graph in G A circuit in which each vertex in the is once and only once , This circuit is called the Hamiltonian circuit ; A graph with a Hamiltonian loop is called Hamilton .  If the figure G There is a pass through graph in G A path through which each vertex in a path passes once and only once , Then this path is called the Hamiltonian path ; A graph with a Hamiltonian path is called And a half Hamilton .

  Main theorem ： Set up a picture G It's a Hamiltonian graph , If from G Delete from p Vertex gets graph G’, Plan G’ The number of connected branches of is less than or equal to p. Set up a picture G Yes. n An undirected simple graph of vertices , If G The sum of the degrees of any two different vertices in is greater than or equal to n-1, Then there is a Hamiltonian path , namely G It's a semi Hamiltonian graph . Set up a picture G Yes. n An undirected simple graph of vertices , If G The sum of the degrees of any two different vertices in is greater than or equal to n, be G With Hamiltonian loop , namely G It's a Hamiltonian graph .