Algorithms on Graphs
Algorithms on graphs involve the study and development of methods for solving problems related to graphs, which are mathematical structures consisting of nodes and edges. These algorithms are used to analyze and manipulate graphs, such as finding the shortest path between two nodes or determining if a graph is connected. They have applications in various fields, including computer science, operations research, and network analysis.
5 Key excerpts on "Algorithms on Graphs"
eBook - ePubBioinformatics Algorithms
Design and Implementation in Python
- Miguel Rocha, Pedro G. Ferreira(Authors)
- 2018(Publication Date)
- Academic Press(Publisher)
...Chapter 13 Graphs: Concepts and Algorithms Abstract In this chapter, we present the mathematical concept of graph and its computational representation. We address some of the main algorithms over graphs and develop a set of Python classes to implement different types of graphs and underlying algorithms. Graphs will be central in the development of algorithms for handling biological networks and genome assembly, tasks addressed in the next chapters. Keywords Graphs; Graph representations; Adjacency lists; Node degree; Paths and distances in graphs; Graph search algorithms In this chapter, we present the mathematical concept of graph and its computational representation. We address some of the main algorithms over graphs and develop a set of Python classes to implement different types of graphs and underlying algorithms. Graphs will be central in the development of algorithms for handling biological networks and genome assembly, tasks addressed in the next chapters. 13.1 Graphs: Definitions and Representations A graph can be defined, in Mathematics, as a set of objects in which some of the pairs of the objects in this set are related. While they can be easily defined and have a simple structure, they are powerful and flexible data structures, with a huge set of applications in computer science and many fields of science and engineering. Formally, a graph G can be defined by two sets: (V, E), where V is the set of objects, named as vertices or nodes of the graph, and E is a set of pairs (u. v) of vertices from V, named edges or arcs, indicating the existence of a relationship between u and v. The edges in E may have an orientation, i.e. the pairs are ordered, in which case the graph is classified as directed, or digraph. Otherwise, the pairs are unordered and the graph is termed undirected...
eBook - ePub- Stephen P Borgatti, Martin G Everett, Jeffrey C Johnson(Authors)
- 2018(Publication Date)
- SAGE Publications Ltd(Publisher)
...2 Mathematical Foundations Learning Outcomes Represent networks in graph-theoretic language Identify paths, walks, trails and components Formulate networks in matrix terms Compute and interpret multiplication of adjacency matrices Don’t forget to visit the website at https://study.sagepub.com/borgatti2e 2.1 Introduction As should be evident from Chapter 1, social network analysis is a social science. The actors we study are typically individuals (specifically humans, but also other social species such as apes and dolphins) or organizations (such as corporations). But networks are encountered in many other fields as well, including physics, ecology, chemistry, neurology, genetics and computer science. What these instances of network analysis have in common is an underpinning in a branch of discrete mathematics called graph theory. In this chapter we introduce the terminology and basic conceptual building blocks of graph theory. In addition, we present a short introduction to matrices, which can also be used to represent networks, and matrix algebra, which has proved very useful in network analysis. 2.2 Graphs One way of conceptualizing networks mathematically is as graphs. The term ‘graph’ here does not refer to a diagram but rather a mathematical object (Harary, 1969). A graph G (V, E) consists of a set of vertices V (also called nodes or points), and a set of edges E (or links or lines). The edges connect pairs of vertices. To express that an edge connecting vertices u and v exists in a graph G, we write (u, v) ∈ E (G). If we think of G as a binary relation, then we could also write uGv. For example, if G represents the ‘likes’ relation, the uGv would indicate that u likes v. When two vertices are joined by an edge, we say the vertices are adjacent. So, adjacent just means ‘has a tie’. If an edge connects A with B, and another edge connects A with C, we say that the two edges are incident upon A...
eBook - ePubCulture, Curiosity and Communication in Scientific Discovery
The Eye in Ideas
- Nigel . Sanitt(Author)
- 2018(Publication Date)
- Routledge(Publisher)
...6 Graph theory Up to now I have described the network model for scientific theorizing in qualitative terms. There is, however, a branch of mathematics which deals with networks at a quantitative level called graph theory. There is an enormous range of types of networks and graph theory provides a mathematical and formal framework for describing, analysing and calculating with networks. All the procedures and characteristics of networks, which I have described, have a ready interpretation in graph theory and many results and theorems in graph theory have a corresponding application in the network model I have proposed. There are no true propositions in science but mathematics is an effective tool both as cement within scientific theories, linking assumptions and predictions, and as a logical foundation for the network structures that constitute the backbone of our understanding. 6.1 What is a graph? There are two different meanings of graph, which have arisen rather confusingly in mathematics. The more commonly known meaning of graph refers to a data plot. The usual example of this type of graph is the familiar diagram of Cartesian coordinates, which consists of two perpendicular axes designated x (horizontal) and y (upright). There are many kinds of graph other than the Cartesian coordinate graph, which was described by René Descartes in 1637. The second meaning of graph, and the one relevant to the present work, was first proposed by the Swiss mathematician Leonhard Euler in 1735. In this sense of the word, a graph is a collection of objects linked together. Pictorially, they are represented by nodes, which may or may not be linked together by lines. 1 If the links are ordered then the lines have arrows on them and are referred to as arcs and the nodes are called vertices; such a graph is said to be directed. Figures 5.1 and 5.2 in the previous chapter are examples of directed graphs or digraphs. The vertices or nodes of a graph may be labelled or unlabelled...
eBook - ePub- Gary Chartrand(Author)
- 2012(Publication Date)
- Dover Publications(Publisher)
...*Chapter 10Graphs and Other MathematicsGraph theory has close relationships with several mathematical areas. In this chapter we consider three of these areas: matrices, topology, and groups.10.1Graphs and MatricesA graph is completely determined by its vertex set and by a knowledge of which pairs of vertices are adjacent. This same information can easily be given by a matrix. In fact, much of graph theory could be investigated as a subject within matrix theory. There are certain advantages to this approach, since matrices can serve as computer input to work a variety of computations. On the other hand, there are several disadvantages to representing graphs as matrices, for this destroys the visual aspect of graphs, and the recognition of certain graphical properties in matrices is not necessarily simpler than in the diagram of a graph.LetGbe a graph of orderpwith vertices denoted byv1, v2,..., vp.Then theadjacency matrix A=A(G)=[aij] is thatpxpmatrix in whichaij= 1 ifviandvjare adjacent andaij= 0 otherwise. Thus, the matrixAis a (0, 1) matrix (i.e., every entryof Ais 0 or 1); the main diagonal ofAconsists entirely of 0’s (i.e.,aii= 0 fori= 1, 2, ...,p); andAis symmetric (i.e.,aij=ajifor 1 ≤i≤pand 1 ≤j≤p). A graphGand its adjacency matrix are given inFigure 10.1.Figure 10.1Note that the adjacency matrix of a graphGordinarily depends on how we label the vertices. For example, the graphGofFigure 10.1is shown again inFigure 10.2with a different labeling, resulting in a different adjacency matrix. Although the matrices ofFigures 10.1and10.2are unequal (as matrices), they represent isomorphic graphs.Figure 10.2One interesting property of an adjacency matrix of a graph concerns the entries of its various powers. Thelengthof a walk is the number of occurrences of edges in it, and twou−vwalks of the same length areequalif their edges occur in exactly the same order.Theorem 10.1Let A be the adjacency matrix of a graph G, where V(G)={v1, v2, ..., vp}...
eBook - ePub- Stephen Wise(Author)
- 2018(Publication Date)
- CRC Press(Publisher)
...First, some new terminology will be introduced. So far, it has been assumed that we are trying to find a route along a real road network. However, this is simply one example of a more general problem of finding the least-cost route through a graph. Graph theory was introduced in Chapter 3 as one of the roots of vector data structures. However, graphs, as well as modelling maps, can be used to represent all sorts of problems. Some of these involve real networks such as transport networks. However, in some, the graph is being used to represent other sorts of connections, such as the links between different stages of a project in critical path analysis. In the more general terminology of graph theory, the starting node is usually referred to as the origin and the destination as the goal. At any point in the algorithm, there are two sets of nodes: • The open set – those nodes which are under active consideration as candidates for being part of the solution. • The closed set – those nodes which have been considered and will not be looked at again. Note that some of these will be on the final route and some will not. FIGURE 11.22 Network with h values shown. In this, the heuristic is the straight line distance to node f. First we will take a look at the Dijkstra algorithm again using this new terminology and then compare this with the A-star algorithm. The Dijkstra algorithm starts with the open and closed sets populated as follows: Open set={All nodes except for the origin} Closed set={The origin} Nodes are moved to the closed set once their distance value has been updated from its initial value of infinity and labelled with their parent node. The full algorithm as applied to the example network is shown in Figure 11.23. The A-star algorithm begins with the two sets as follows: Open set = {Origin} Closed set = {The empty set} Step 1 Open set: {A,0; B,INF; C,INF; D,INF; E,INF; F,INF} Closed set {} Move A to closed set...
