“This is the 25th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.
Seven,
7.1 Definition of graph
A Graph is a set of finite non-empty sets of vertices and edges between vertices. It is usually expressed as G(V,E), where G represents a Graph, where V is the set of vertices in Graph G, and E is the set of edges in Graph G.
-
In linear tables we call data elements elements, in trees we call data elements nodes, and in graphs we call data elements vertices.
-
A linear table can have no data elements, called an empty table. A tree can have no nodes, called an empty tree. What about graphs? In graph structures, no vertices are allowed. In the definition, if V is a set of vertices, it is emphasized that the set of vertices V is finite and not empty.
-
In a linear list, there is a linear relationship between adjacent data elements, and in a tree structure, the nodes of two adjacent layers have a hierarchical relationship. In a graph, there may be a relationship between any two vertices, and the logical relationship between vertices can be represented by edges, and the edge set can be empty.
7.1.1 Definitions of various diagrams
Unordered pairs are a special kind ofA collection of. That is, only twoThe elementThe collection.
Directed graph
Every edge has a direction
Undirected graph
Each edge is directionless
Complete graph
Any two points are connected by an edge
Thin figure
A graph with few edges or arcs (e <nlogn)
Dense figure
A graph having more sides or arcs
net
Graph with edge/arc weights
adjacency
The relationship between two vertices connected by an edge/arc
If (Vi, Vj) exists, v and V are called adjacency points of each other;
If
exists, it is said that Vi is adjacent to Vj and Vj is adjacent to Vi;
Association (attachment)
Relationship between edges/arcs and vertices
If (Vi, Vj)/
exists, the edge/arc is said to be associated with Vi and Vj;
Vertex degree
The number of edges associated with this vertex is called TD(v).
In a directed graph, the degree of a vertex is equal to the sum of the degree of entry and degree of exit of that vertex.
The entry of vertex V is the number of directed edges that end at V, called ID(V).
The degree of the vertex v is the number of directed edges at the point starting with v, so let’s call it OD of v.
See instances:
What is the shape of a directed graph when the degree of entry of only one vertex is 0 and the degree of entry of all other vertices is 1? Is the tree! And a directed tree!
The path
A sequence of vertices constructed by edges
The length of the path
Sum of the number/weights of edges or arcs on a path
If there were no weights, the length of the path above would be 2
If you have edge weights, then the weights add up to the length of the path
Loop (loop)
The first vertex is the same path as the last vertex
A simple path
A path with different vertices except where the start and end of the path may be the same
Simple loop (simple loop)
A path with different vertices except for the same starting and ending points.
Connected graph (strongly connected graph)
In a directed graph G=(V, {E}), G is said to be a connected graph (strongly connected graph) if there is a path from V to U for any two vertices V and u.
It is clear from the picture how different the concepts are
There’s not much explanation here
subgraph
As shown above, it is easy to see that figures B and C are both subgraphs of Figure A
Connected components
The maximally connected subgraph of an undirected graph G is called the connected component of G.
A maximally connected subgraph is one in which the number of vertices is already the maximum and the subgraph cannot be connected by adding vertices
Strongly connected component
The extremely strongly connected subgraph of a directed graph G is called the strongly connected component of G.
A maximally strongly connected subgraph means that the subgraph is a strongly connected subgraph of G, and if any vertices of D that are not in the subgraph are added, the subgraph is no longer strongly connected.
Minimal connected subgraph
The subgraph is a connected subgraph of G. Deleting any edge in the subgraph is not connected
A minimally connected subgraph may or may not contain all vertices
Spanning tree
A minimally connected subgraph containing all vertices of an undirected graph G
Generate the forest
For an unconnected graph, the set of spanning trees composed of connected components
7.1.2 Definition of figure and glossary summary
Graphs are divided into undirected graphs and directed graphs according to whether they have direction or not. An undirected graph consists of vertices and edges, while a directed graph consists of vertices and arcs. Arc has arc tail and arc head points.
The graph is divided into sparse and dense graphs according to the number of edges or arcs. If there are edges between any two vertices, it is called a complete graph, and directed is called a directed complete graph. A simple graph with no repeating edges or vertices to itself is called a simple graph
There are concepts of adjacency and attachment between vertices in graphs. The number of edges of an undirected graph vertex is called a degree, and a directed graph vertex is divided into an in degree and an out degree.
Edges or arcs on a graph with weights are called nets.
If there is a path between vertices in the graph, it means that the two vertices are connected. If the path eventually returns to the starting point, it is called a ring, and the simple path is not repeated. A graph is a connected graph if any two vertices are connected, and a directed graph is strongly connected. There are subgraphs in the graph. If the subgraph is extremely connected, it is a connected component. If the subgraph is directed, it is a strongly connected component.
An undirected graph with n vertices and n-1 edges connected is called a spanning tree. A directed graph with a vertex of 0 and other vertices of 1 is called a directed tree. A directed graph consists of thousands of directed trees forming a generative forest.