Important definitions:

Directed graph: A graph whose edges are directed.

Undirected graph: A graph whose edges are undirected.

Mixed graph: A graph with both directed and undirected edges.

Self-ring: The two ends of a side coincide.

Multiplicity: If there are several edges between two vertices, these edges are called parallel edges, and the number of parallel edges between two vertices A and B becomes the multiplicity of (a, b).

Multigraph: A graph with parallel edges.

Simple graph: a graph without parallel edges and self-circulation.

Attention! An undirected edge can be replaced by a pair of directed edges in opposite directions, so that an undirected graph can be transformed into a directed graph.

Directed graph: If each undirected edge of undirected graph G is given a direction, a directed graph D is obtained. It is called the G- pattern.

Basemap: If the direction of each directed edge of a directed graph is removed, then this undirected graph G is called a D basemap.

Inverse graph: the graph obtained by inverting each edge of directed graph D is called the inverse graph of D.

Weighted graph: Each edge is assigned a value.

Degree: The number of edges connected with the vertex is called the degree of the fixed point, and the number of edges from the fixed point is called the degree. In-degree: The number of edges with a fixed point as the terminal edge is in-degree.

Special! A fixed point of zero degree is called an isolated point. A point with a degree of 1 is a hanging point.

Undirected complete graph: in an undirected graph, if any two points are connected by edges, the graph is called undirected complete graph. (=knot) in the sea

Completely directed graph: in a hierarchical directed graph, if any two points are connected by directed edges in opposite directions, the graph is called completely directed graph.

Competitive graph: If the base graph in the step graph is undirected complete graph, then the directed complete graph is competitive graph.

Attention! The number of edges of a directed complete graph of order n is the square of n; The number of edges of an undirected complete graph is n(n- 1)/2.

Here are two operations of the graph: ① Edge deletion: deleting an edge in the graph, but still retaining the endpoint of the edge.

(2) Delete a point: delete a point in the graph and all the edges connected with the point.

Subgraph: Delete an edge or a point of the remaining graph.

Generate subgraph: only delete edges without deleting points.

Principal subgraph: the principal subgraph of a subgraph obtained by deleting a point in the graph.

Complementary graph: set it as a single undirected graph between steps, and after adding some edges to it, you can make a complete graph of steps; A graph composed of these vertices plus edges and sums is called a complementary graph.

Important theorem:

Theorem 5. 1. 1 Let a graph G be a directed graph with n vertices and m edges, where the point set V = {V, v, ..., V}

Degrees+(6) = Degrees-(6) = meters

Theorem 5. 1.2 Let graph G be an undirected graph with n vertices and m edges, where the point set V = {v, V, V, ..., v}

Degree (vi)=2m

It is inferred that in an undirected graph, the number of vertices whose degree is the product is even.

The shortest path of path and weighted graph

1 path and loop

Basic concepts:

Length of path: the number of sides of the path.

Loop: If the starting point and ending point in the path are the same.

Simple path: If all the edges in the path are different.

Basic path: If all vertices in the path are different. Obviously (the basic path must be a simple path, but the simple path is not necessarily a basic path)

Accessibility: In Figure G, if there is a path from V to D, it is said that V to D is reachable.

Connected: In an undirected graph, if any two points are reachable, otherwise they are not connected.

Strongly connected: If any two points in a directed graph are mutually reachable.

One-way connectivity: If there are any two paths in the directed graph.

Weakly connected: in a directed graph, if its base graph is connected.

Weight: a number that represents some information about a point or edge in a graph.

Weighted graph: a graph with weights.

The algorithm of weighted graph shortest path problem: first find the shortest path to a certain point, then use this result to determine the shortest path to another point, and so on until the shortest path is found.

Indicator: Let V be the point set of the graph, T be a subset of V, and T contain Z but not A, then T is called the target set. Take any point T in the target set T. In all paths from A to T but not passing through other points in the target set T, the minimum sum of edge weights is called point T, and the index of T is recorded as DT(t).

Graphics and matrices

The difference between the two meanings: the meaning of the elements in A: If and only if A and A are both 1, A = 1 and A and A are both1,which means that there are edges (v, v) and (v, v) in graph G, so it can be concluded that if the edges drawn from vertices V and V are terminated, Especially for b, its value is the degree of v.

The meaning of the element in A: A A = 1 If and only if both A and A are 1, this means that there are edges (v, v) and (v, v) in the graph. Therefore, it is concluded that if the edges drawn from some points end in V and V at the same time, then the number of such vertices is the value of. Especially for b, its value is V-in.

The meaning of elements in power A: When m= 1, the element in A = 1, which means that there is an edge (v, v) or a path with the length of 1 from v to v. ..

The element a in a represents the number of all paths of length m from v to v.

euler graph

Main definitions:

If a cycle in a graph passes through each edge of the graph once and only once, it is called Euler path, and a graph with Euler path is called Euler graph.

If a path in a graph passes through each edge of the graph once and only once, the circle is called Euler path, and a graph with Euler path 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-Euler graph if and only if there are at most two odd points in the graph.

Let graph G be a directed connected graph and an Euler graph if and only if the in-degree and out-degree of each vertex in the graph are equal.

Let a graph G be a directed connected graph and a semi-Euler graph if and only if there are at most two vertices, in which the degree of one vertex is greater than its degree 1 and the degree of the other vertex is less than its degree1; While the in-degree and out-degree of other vertices are equal.

Hamiltonian diagram

Main definitions: If a loop in a graph G passes through each vertex in the graph G once and only once, it is called a Hamiltonian loop of the graph; A graph with Hamilton cycles is called a Hamilton graph.

If there is a loop in graph G that passes through each vertex in graph G once and only once, it is called a Hamiltonian loop of graph. A graph with Hamilton cycles is called a Hamilton graph.

Main Theorem: Let graph G be a Hamilton graph. If graph G' is obtained by deleting p vertices from G, then the number of connected branches of graph G' is less than or equal to p..

Let graph G be an undirected simple graph with n vertices. If the sum of degrees of any two different vertices in G is greater than or equal to n- 1, it has a Hamilton path, that is, G is a semi-Hamilton graph.

Let graph G be an undirected simple graph with n vertices. If the sum of degrees of any two different vertices in G is greater than or equal to n, then G has a Hamilton cycle, that is, G is a Hamilton graph.

References:

/yzren/showthread.php？ t=29079