当前位置：网站首页>Basic definition and concept of graph (II)

Basic definition and concept of graph (II)

2022-07-22 09:43:00 【InfoQ】

Complete graph

For one with n vertices ,e Undirected graph of strip and edge , If the total number of edges is n*(n-1)/2, The graph is called a complete graph .

Directed complete graph

For one with n vertices ,e A digraph of edges or arcs , If the total number of edges is n*(n-1), It is called directed complete graph .

power

Sometimes the edge or arc of a graph has a number related to it , This number related to the edge or arc of a graph is called weight .

network

These weights can represent the distance or cost from one vertex to another . This weighted graph is often called a net .

Subgraphs

It can be understood as an included part , Part of a big picture .

route

In a graph, if from any vertex v set out , You can reach another vertex along the edge v', There is a path between these two vertices . The number of non overlapping edges between two vertices is called the length of the path .

Simple path

When a path is represented by a sequence of vertices , If the same vertex does not appear repeatedly in the sequence , It is called a simple path . Except for the first vertex and the last vertex , Circuits with different vertices are called simple circuits .

Undirected connected graph

In the undirected graph G in , If from the top v To the top v' There is a path , said v and v' It's connected . If for any two vertex points in an undirected graph vi and vj(vi、vj ∈V), It's all connected , said G It's a connected graph .

Connected component

The polar Tongzi graph of undirected graph .

Directed connected graph

In digraph G in , If for each pair of vertices (vi,vj)(vi,vj ∈V)(vi≠vj), from vi To vj And from the vj To vi There are paths , said G It's a strongly connected graph . Directed graph G The maximal strongly connected subgraph in is called the strongly connected component of a digraph , Pictured 7.5（1） Shown . chart 7.5(2) Is a non strongly connected graph and its three strongly connected components .

Make trees

Minimal connected subgraph of a connected graph , Called its spanning tree . It contains all the vertices in the graph N, But only enough to make a tree N-1 side . The following figure shows the spanning tree . The graph contains 10 vertices , So the spanning tree has 9 side .

One has N A spanning tree of vertices , Yes and no N-1 side . If a picture has N The sum of vertices is less than N-1 side , Then the graph is unconnected .

If it has more than n-1 side , Then there must be a ring . But there are n-1 Not all graphs with edges are spanning trees .