Definitions and terms of drawings

1. chart （Graph） It is composed of the finite non empty set of vertices and the set of edges between vertices , Usually expressed as ：G(V,E), among ,G Represents a graph ,V The picture is G The set of vertices in ,E The picture is G A collection in the middle .
2. For the definition of graph , We need to be clear about a few things to pay attention to ：
   In linear tables we call data elements elements elements , A tree is called a node , In the graph, the data elements are called vertices (Vertex).
   Linear tables can have no data elements , Known as the empty table , There can be no nodes in the tree , It's called the empty tree , And graph structure emphasizes vertex set in most textbooks in our country V Be poor, not empty .
   In the linear table , There is a linear relationship between adjacent data elements , In the tree structure , The nodes of two adjacent layers have hierarchical relationship , And in the graph structure , There may be a relationship between any two vertices , The logical relationship between vertices is represented by edges , Edge sets can be empty .
3. No to the edge ： If the summit Vi To Vj The edge between has no direction , We call this edge undirected (Edge), With unordered pairs (Vi,Vj) To express .
   
   Upper figure G1 It's an undirected graph ,G1={V1,E1}, among V1={A,B,C,D},E1={(A,B),(B,C),(C,D),(D,A),(A,C)}.
4. There is a directional side ： If from the top Vi To Vj There's a direction on the side of , We call this side a directed side , Also become an arc (Arc), With an orderly couple <Vi,Vj> To express ,Vi It's called the arc tail ,Vj It's called the arc head .
   
   Upper figure G2 It's a digraph ,G2={V2,E2}, among V2={A,B,C,D},E2={<B,A>,<B,C>,<C,A>,<A,D>}
5. Simple picture ： In the diagram structure , If there is no edge from vertex to itself , And the same edge does not appear repeatedly , This is called a simple graph .
6. Undirected complete graph ： In the undirected graph , If there is an edge between any two vertices , The graph is called undirected complete graph . contain n The undirected complete graph of vertices has n*(n-1)/2 side .
   
7. Directed complete graph ： In a directed graph , If there are two arcs with opposite directions between any two vertices , It is called directed complete graph . contain n The directed complete graph of vertices has n*(n-1) side .
   
8. Sparse graph and dense graph ： Sparse and dense here are fuzzy concepts , Are relative , It is generally considered that the number of edges or arcs is less than n*logn（n Is the number of vertices ） A graph of is called a sparse graph , On the contrary, it is called dense graph .
9. Some graphs have edges or arcs with numbers associated with them , The number related to the edge or arc of a graph is called weight (Weight), Weighted graphs are often called nets (Network).
10. Suppose there are two graphs G1=(V1,E1) and G2=(V2,E2), If V2⊆V1,E2⊆E1, said G2 by G1 The children of (Subgraph).
    
11. For undirected graphs G=(V,E), If the side (V1,V2)∈E, It's called the summit V1 and V2 They are adjacency points to each other (Adjacent), namely V1 and V2 Next to each other . edge (V1,V2) Attachment (incident) At the top V1 and V2, Or in other words (V1,V2) And the summit V1 and V2 Related to .
12. The vertices V Degree (Degree) Is and V Number of sides associated , Write it down as TD(V), Here's the picture , The vertices A And B They are adjacency points to each other , edge (A,B) Attached to the apex A And B On , The vertices A The degree of 3.
    
13. For digraphs G=(V,E), If there is <V1,V2>∈E, It's called the summit V1 Adjacent to the vertex V2, The vertices V2 Adjacency from vertex V1.
    At the top V The number of arcs for the head is called V The degree of (InDegree), Write it down as ID(V), With V The number of arcs with tails is called V The degree of (OutDegree), Write it down as OD(V), So the apex V The degree of TD(V)=ID(V)+OD(V).
    Following vertex A My penetration is 2, The output is 1, So the summit A The degree is 3.
    
14. Undirected graph G=(V,E) From the top V1 To the top V2 The path of (Path).
    The following figure lists the vertices with red lines B To the top D Four different paths ：
    
15. If G It's a directed graph , Then the path is also directed .
    The following figure lists vertices with red lines B To the top D Two paths to , And the summit A To the top B There is no path
    
16. The length of the path is the number of edges or arcs on the path .
17. The same path from the first vertex to the last vertex is called a loop or ring (Cycle).
18. The path in which vertices do not appear repeatedly in a sequence is called a simple path , Except for the first vertex and the last vertex , The rest of the vertices do not repeat the loop , It's called a simple loop or a simple ring .
    The left side of the figure below is a simple ring , The right side is not a simple ring ：
    
19. In the undirected graph G in , If from the top V1 To the top V2 There is a path , said V1 and V2 It's connected , If for any two vertices in the graph Vi and Vj It's all connected , said G It's a connected graph (ConnectedGraph)
    The left side of the figure below is not a connected graph , On the right is the connected graph ：
    
20. In undirected graph, the polar connected subgraph is called connected component .
    （ Connected components are “ The entire undirected graph is not a connected graph ” Put forward for the premise ）
    Note the following concepts ：
    1） First, let's say subgraphs , And subgraphs are connected ;
    2） Connected subgraphs contain maximal vertex points ;
    3） Connected subgraphs with maximal vertex number contain all edges attached to these vertices .
    The left figure below shows the connected components , The right figure does not contain D The vertices , So it's not a connected component .
    
21. In digraph G in , If for each pair Vi To Vj There are paths , said G It's a strongly connected graph .
    The maximal strongly connected subgraph in a directed graph is called the strongly connected component of a directed graph .
    The left side of the figure below is not a strongly connected graph , The right side is . And on the right is the maximal strongly connected subgraph on the left , It's also the strongly connected component on the left .
    
22. The spanning tree of a connected graph is a minimal connected subgraph , It contains all the n vertices , But only enough to make a tree n-1 side .
    
    The following figure shows a spanning tree in the above figure
    
23. If a directed graph has exactly one vertex, the degree of penetration is 0, The penetration of the other vertices is 1, Is a directed tree .
    
    Connected graph
    http://data.biancheng.net/view/201.html