Graphs

Graphs

1. Concepts

   • a graph is a collection of points in the plane called nodes or vertices, some of them connected by line segments called edges.
     • It is normally convenient to label vertices of a graph with letters, integer numbers, or character strings
   • Graph representations
     • Graphs for computer algorithms are usually represented in one of two ways: the adjacency matrix and adjacency lists.
       • The adjacency matrix of a graph with n vertices is an n × n boolean matrix with one row and one column for each of the graph’s vertices
         • the element in the ith row and the j th column is equal to 1 if there is an edge from the i th vertex to the j th vertex, and equal to 0 if there is no such edge
       • The adjacency lists of a graph or a digraph is a collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list’s vertex
         • Usually, such lists start with a header identifying a vertex for which the list is compiled
   • Weighted Graphs
     • is a graph (or digraph) with numbers assigned to its edges
       • These numbers are called weights or costs
     • This kind of graphs has a lot of applications, such as finding the shortest path between two points in a transportation or communication network or the traveling salesman problem
       • If a weighted graph is represented by its adjacency matrix, then its element A[i, j] will simply contain the weight of the edge from the ith to the jth vertex if there is such an edge and a special symbol
         • if there is no such edge. Such a matrix is called the weight matrix or cost matrix
   • Paths and Cycles
     • Among the many properties of graphs, two are important for a great number of applications: connectivity and acyclicity
       • A path from vertex u to vertex v of a graph G can be defined as a sequence of adjacent (connected by an edge) vertices that starts with u and ends with v.
         • If all vertices of a path are distinct, the path is said to be simple.
           • The length of a path is the total number of vertices in the vertex sequence defining the path minus 1, which is the same as the number of edges in the path
         • In the case of a directed graph, we are usually interested in directed paths.
           • A directed path is a sequence of vertices in which every consecutive pair of the vertices is connected by an edge directed from the vertex listed first to the vertex listed next.

2. Searchs

   • The term “exhaustive search” can also be applied to two very important algorithms that systematically process all vertices and edges of a graph: depth-first search (DFS) and breadth-first search (BFS)
     • Depth-first search
       • starts a graph’s traversal at an arbitrary vertex by marking it as visited.
         • On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in.
           • This process continues until a dead end—a vertex with no adjacent unvisited vertices— is encountered
             • At a dead end, the algorithm backs up one edge to the vertex it came from and tries to continue visiting unvisited vertices from there.
               • The algorithm eventually halts after backing up to the starting vertex, with the latter being a dead end
                 • By then, all the vertices in the same connected component as the starting vertex have been visited
                   • If unvisited vertices still remain, the depth-first search must be restarted at any one of them
                     • It is not difficult to see that this algorithm is, in fact, quite efficient since it takes just the time proportional to the size of the data structure used for representing the graph in question
     • depth-first search
       • is a traversal for the brave (the algorithm goes as far from “home” as it can), breadth-first search is a traversal for the cautious
         • It proceeds in a concentric manner by visiting first all the vertices that are adjacent to a starting vertex
           • Them, all unvisited vertices two edges apart from it, and so on, until all the vertices in the same connected component as the starting vertex are visited
             • If there still remain unvisited vertices, the algorithm has to be restarted at an arbitrary vertex of another connected component of the graph.
               • It is convenient to use a queue to trace the operation of breadth-first search
                 • The queue is initialized with the traversal’s starting vertex, which is marked as visited
                   • On each iteration, the algorithm identifies all unvisited vertices that are adjacent to the front vertex, marks them as visited, and adds them to the queue
                     • after that, the front vertex is removed from the queue
                       • Breadth-first search has the same efficiency as depth-first search

3. Topological Sorting

   • for topological sorting to be possible, a digraph in question must be a dag
     • It turns out that being a dag is not only necessary but also sufficient for topological sorting to be possible
       • if a digraph has no directed cycles, the topological sorting problem for it has a solution.
       • Moreover, there are two efficient algorithms that both verify whether a digraph is a dag and, if it is, produce an ordering of vertices that solves the topological sorting problem
         • The first algorithm is a simple application of depth-first search: perform a DFS traversal and note the order in which vertices become dead-ends
           • Reversing this order yields a solution to the topological sorting problem, provided, of course, no back edge has been encountered during the traversal
             • If a back edge has been encountered, the digraph is not a dag, and topological sorting of its vertices is impossible.
               • This algorithm works because When a vertex v is popped off a DFS stack, no vertex u with an edge from u to v can be among the vertices popped off before v.
                 • Hence, any such vertex u will be listed after v in the popped-off order list, and before v in the reversed list
         • The second algorithm is based on a direct implementation of the decrease-(by one)-and-conquer technique:
           • repeatedly, identify in a remaining digraph a source, which is a vertex with no incoming edges, and delete it along with all the edges outgoing from it
             • If there are several sources, break the tie arbitrarily. If there are none, stop because the problem cannot be solved
             • The order in which the vertices are deleted yields a solution to the topological sorting problem
               • the solution obtained by the source-removal algorithm is different from the one obtained by the DFS-based algorithm
                 • Both of them are correct, of course; the topological sorting problem may have several alternative solutions.
                   • imagine a large project—e.g., in construction, research, or software development—that involves a multitude of interrelated tasks with known prerequisites.
                     • The first thing to do in such a situation is to make sure that the set of given prerequisites is not contradictory.
                       • The convenient way of doing this is to solve the topological sorting problem for the project’s digraph
                         • Only then can one start thinking about scheduling tasks to, say, minimize the total completion time of the project.
                           • This would require other algorithms that you can find in general books on operations research or in special ones on CPM (Critical Path Method) and PERT (Program Evaluation and Review Technique) methodologies.

Imágenes y archivos del mapa