This is the 21st day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Preface:

We put the trees in front of all the knowledge learned, today we’ll learn figure, if not algorithm, graph is is a kind of to learn our last “data structure”, figure is a kind of nonlinear data structure, it is more complicated than the tree structure, we learn knowledge is in front of the one-to-one or one-to-many relationship, today to learn is a many-to-many relationship, Usually used to represent data in a mesh structure. In fact, everything we’ve learned so far is a special kind of graph, a graph is used in a lot of neighborhoods, and when you’re a blogger, you’re learning about networks, a wan is a network, which means more than one channel.

Once a day, pay attention to rest

1. Definition of graph

Graph G (Graph) consists of two sets V(Vertex) and E (Edge), denoted as G=(V,E), where V is a finite set of vertices, denoted as V(G), and E is a finite set of edges connecting two different vertices (Vertex pairs) in V. Denoted as E(G). For a graph containing n vertices, letters or natural numbers are usually used to uniquely identify the vertices in the graph (the number of vertices).

2. Basic terms for graphs

2.1 Undirected graphs and directed graphs

For a graph G, the graph is said to be undirected if the edge set E(G) is the set of undirected edges

2.2 Endpoints and adjacent points

(undirected graph) In an undirected graph, if there is an edge (I,j), vertices I and j are called the endpoints of that edge and they are called adjacent points (or adjacents) to each other. Vertex 0 and vertex 1 are two endpoints, which are adjacent to each other. (Digraph) In a digraph, if there is an edge < I,j>, this edge is said to be an outgoing edge of vertex I and an incoming edge of vertex J, and vertices I and J are said to be the starting and ending points of this edge, respectively.

2.3 Degree, in degree and out degree

The degree of vertex V is called D(v). For undirected graphs, the degree of each vertex is defined as the number of edges with that vertex as an endpoint. For a directed graph, the degree of vertex V is divided into the degree of entry and the degree of exit. The degree of entry is the number of edges ending at this vertex. The degree of the vertex is equal to the sum of its degrees and degrees.

2.4 subgraph

Let two graphs G=(V,E) and G’=(V’,E’). If V’ is a subset of V, that is, V’ is contained in V, and E’ is a subset of E, that is,E’ is contained in E, G’ is said to be a subgraph of G.

2.5 Completely undirected graphs and completely directed graphs

For an undirected graph, if it has n(n-1)/2 edges, it is called a completely undirected graph. For a directed graph, if it has n(n-1) edges, it is called a completely directed graph

2.6 Sparse and dense graphs

A graph with fewer edges (edge number e<n(log2)n, where n is the number of vertices) is called a sparse graph. A graph with more edges is called a dense graph.

2.7 Path and Path Length

Path: In a graph G, a path from vertex I to vertex j is a sequence of vertices I =i0, i1… , im=j, if the graph is undirected, then (IK-1, IK)∈E(G), (1≤k≤m) if the graph is directed, then < IK-1, IK >∈E(G) (1≤ K ≤m), where vertex I is called the beginning point of the path, and vertex j is called the end point of the path.

** Path length :** refers to the number of edges passed along a path.

2.8 Simple Paths

A path is simple if its sequence of vertices does not repeat itself. For example, path 1→2→4 is a simple path with a length of 2.

2.9 Loop (Loop)

A path is called a loop if its beginning and ending points are the same vertex. A loop whose vertices do not repeat themselves except for the same starting and ending points is called a simple loop (simple loop). For example, in the figure, path 0→1→2→4→3→0 is a loop (ring) and also a simple loop (simple ring).

2.10 Connectivity, connectivity graphs, and connectivity components

In undirected graph G, vertices I and j are said to be connected if there is a path from vertex I to vertex J. Graph G is called connected if any two vertices in it are connected, otherwise it is disconnected. The maximally connected subgraph of an undirected graph G is called the connected component of G. For example, the connected component of a graph is itself, because the graph is connected

2.11 Strongly connected graphs and strongly connected components

A directed graph G is said to be strongly connected if any two vertices I and j are connected, i.e. there are paths from vertex I to j and from vertex j to I. The extremely strongly connected subgraph of a directed graph G is called the strongly connected component of G.

2.12 power and network

In a graph, each edge may be marked with a value that has some meaning, called the weight of the edge. A graph with weighted edges is called a weighted graph, also known as a net.

conclusion

Figure the basics of bloggers have almost finished, bloggers are drawing for each term explanation, this article belongs to the base paper, let us understand the basic knowledge of graph, bloggers feel blogger drawing into the easy to understand, although some of the pictures don’t look good, but bloggers give, for example, out of the knowledge, is almost hand-on teaching, students learn to see remember thumb up oh, Creation for not easy ah, like comment collection, love you!!