This is the 19th day of my participation in the Genwen Challenge

figure

The concept of the figure

Graph G is composed of vertex set V and edge set E, denoted as G=(V,E), where V(G) represents the finite non-empty set of vertices in graph G; E(G) represents the set of relations (edges) between vertices in graph G if V={v1,v2,v3… ,vnv_1,v_2,v_3… ,v_nv1,v2,v3… ,.vn}, use | V | for the vertices of a graph G number, also known as the order of graph G, E = {(u, V) | u ∈ V, V ∈ V \ in V, V/V ∈ V, in V ∈ V}, expressed in | E | article edges in the graph G

There are no empty graphs, i.e. graphs must have vertices

  • Directed graph
  • Undirected graph
  • A simple figure
    • There are no duplicate edges
    • There are no edges from vertices to themselves
  • Multigraph: As opposed to simple graph
  • Complete graph: In an undirected graph, if there are edges between any two vertices, the graph is called an undirected perfect graph; an undirected perfect graph with n vertices has N (n-1) edges; in a directed graph, if there are two arcs between any two vertices with opposite directions, the graph is called a directed perfect graph. A directed perfect graph with n vertices has n(n-1) directed edges. In FIG. 5.1, G2G_2G2 is an undirected perfect graph, while G3G_3G3 is a directed perfect graph

  • Subgraph: given two graphs G=(V,E) and G ‘=(V ‘,E’), G’ is said to be a subgraph of G if V’ is a subset of V and E’ is a subset of E. If G and G ‘have the same number of vertices, G’ is called a generated subgraph
  • Connected, connected graphs, and connected components: The maximally connected subgraph of an undirected graph is called a connected component
  • Strongly connected graph, strongly connected component: connected from vertex V to vertex W is strongly connected
  • 3. A spanning tree or forest:
    • The spanning tree of a connected graph is a minimal connected subgraph containing all the vertices in the graph
    • In an unconnected graph, the spanning tree of connected components constitutes the spanning forest of the unconnected graph
  • The degree, degree, or degree of a vertex:
    • Degree of vertices in a graph: the number of edges of this vertex
    • Entry: The number of directed edges terminating at vertex V,
    • The sum of the intakes equals the sum of the outtakes, and equals the number of edges
  • Edge weights and nets: Each edge has a number. A weighted graph is called a net
  • Path, path length, loop: Path — a sequence of paths from vertex VP to vertex vq a sequence of paths from vertex Vq v_p,v_1,v_2, v_qVP to vertex vq vp,v1,v2,vq, the number of paths above is called path length, A path whose last vertex is the same as the first vertex is called a loop or ring. If a graph has n vertices and more than n-1 edges, the graph must have a ring
  • Simple path, simple loop: a path with no repetition is called a simple path, and a path with no repetition except for the first vertex is called a simple loop
  • Distance: the shortest path length from I to V
  • A directed graph with a vertex of zero entry and other non-zero vertices is called a directed tree

How the graph is stored

Adjacency matrix < order >

A one-dimensional array stores information about vertices in the graph, and a two-dimensional array stores information about edges in the graph, which is called an adjacency matrix

The characteristics of

  • The adjacency matrix of an undirected graph must be symmetric, so only half of it can be saved
  • You can’t tell directly how many edges there are
  • Dense graph fit
  • The element A “[I][j] of A” is equal to the number of paths of length n from vertex I to vertex j

Adjacency list < links >

The characteristics of

  • Thin figure
  • If for undirected graph G, the required storage space is O (| V | | | E + 2); If G is have to plan for the O (+ | E | | V |)
  • There is no direct way to see if there is an edge between two nodes
  • It’s not easy to find the degree
  • Adjacency list means not unique