Basic concepts and definitions of Graphs

Let's start with a few words ：

1.

2.

3.

 

4.

  

Let's talk about the following concepts ：

        1. chart ：

         A finite nonempty set of vertices and a set of edges between vertices , Usually expressed as G=(V,E),G Represents a graph ,V Represents a collection of vertices ,E Represents a collection of edges

        2. Undirected edge and directed edge ：

                 No to the edge ： Like from the top v1 To v2 The side of has no direction , We call this edge undirected , Use disorder to couple (v1,v2) Express

                 There is a directional side ： From the top v1 To v2 With direction , We call this side a directed side , Also become an arc arc, Use ordered pairs (v1,v2) Express , among v1 Represents the arc tail ,v2 Indicates arc head , Be careful (v2,v1) And (v1,v2) It's two different directions , That is, two different directed edges

        3. Digraph and undirected graph

                Undirected graph ： Any two vertices in the graph are undirected edges

                

                Directed graph ： The edge between any two points is a directed edge

                

        4. Undirected complete graph and directed complete graph

                Undirected complete graph ： There are edges between any two vertices , contain n Undirected complete graphs of nodes have n(n-1)/2 side

                

                Directed complete graph ： In a directed graph , There are two arcs with opposite directions between any two vertices . contain n A directed complete graph of nodes contains n(n-1) side

                

         

5. Some other basic definitions

        

         

              Now let's talk about in and out ：

                         

                about A Come on , If you put A Think of it as a head arc , The degree of penetration is 2, from B->A,C->A

                If you put A As tail of arc , The output is 1,A->D

                The number of arcs is equal to the sum of the degrees of each vertex , It is equal to the sum of the penetration of each vertex  

         

 6. Connected graph

          In the undirected graph , Any two vertices are interconnected , That is, what can be reached , It's a connected graph

        

        The left is not a connected graph , On the right is

        Let's talk about connected graph spanning tree

                First, it is a minimal connected graph subgraph , It contains all the n Nodes , But only enough to make a tree n-1 side

        

        chart 1 Yes n vertices ,n side , Not a connected graph spanning tree , chart 2 yes , Note that the first must be a connected graph