graphs

graphs

1. How are graphs classified?

   • graph
     • A graph is a set of vertices or nodes connected by edges or arcs.
   • acyclic graph
     • It is that graph does not contain any simple cycle.
   • cyclic graph
     • A graph is said to be cyclic if it contains any simple cycle.
   • bipartite graph
     • A bipartite graph is any graph, whose vertices can be divided into two sets, such that there are no edges between the vertices of the same set.
   • complete graph
     • A graph is complete if each vertex has a degree equal to n-1, where n is the number of the vertex that makes up the graph.
   • connected graph
     • A dense graph is that graph in which the number of edges is close to the maximum number of edges.
   • dense graph
     • It is a set of vertices V and a set of edges E such that for each edge belonging to the set of edges E it is associated with two vertices in an ordered way.
   • undirected graph
     • The null graph is the graph whose sets of edges and vertices are empty.
   • null graph
     • They are those graphics in which the sides are not oriented (they are not arrows). Each side is represented in parentheses, separating its vertices by commas.

2. Routes of a graph, what are they and how does it work?

   • In-Depth Tour
     • As we traverse the graph, we will correlatively number the nodes found (1,2,...). We assume that all these numbers are zero initially, and we use a global counter n, also initialized to zero.
   • Amplitude travel
     • The implementation is similar to DFS, but a queue is used instead of a stack. The result is that nodes are visited in increasing order relative to their distance from the origin node