Algorithms on Graphs

7 Key excerpts on "Algorithms on Graphs"

• 

  eBook - ePub

  Principles of Computational Cell Biology

  From Protein Complexes to Cellular Networks

  • Volkhard Helms(Author)
  • 2018(Publication Date)
  • Wiley-VCH

    (Publisher)

  4 Algorithms on Mathematical Graphs

  In this chapter, we introduce the mathematical object of a graph and some basic algorithms that operate on graph structures. These concepts are essential for analyzing the topologies of protein–protein interaction networks in Chapter 6 using undirected graphs and for analyzing gene‐regulatory networks in Chapter 9 using directed graphs.

  4.1 Primer on Mathematical Graphs

  A graph G is an ordered pair (V, E) of a set V of vertices and of a set E of edges (Figure 4.1 ). E is always a subset of the set V(2) of unordered pairs of V, which consists of all possible connections between all vertices. If E = V(2) , we say the graph is fully connected. In this chapter, we will consider fully connected subsets of the full graph that are also called cliques. A weighted graph has a real‐ or integer‐valued weight assigned to each edge. A subgraph of a graph G is a graph whose vertex and edge sets are subsets of those of G.

  Figure 4.1 A mathematical graph consists of vertices and edges. (a) An undirected graph is shown consisting of four vertices (A, B, C, and D) and five edges (connections). This example could represent the results from a yeast two‐hybrid experiment probing binary protein–protein interactions that gave positive results for five interactions A–B, A–D, A–C, B–C, and C–D. (b) Almost the same system is shown, but this time as a directed graph with arrows (arcs) instead of edges. This example could, for example, visualize a gene regulatory network where a transcription factor A controls the expression of genes B, C, D, etc. Here, A, B, C, and D are the four vertices of the graph, and the five arcs are the directed edges of the graph.

  A path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the successor vertex. The first vertex is called the start vertex, and the last vertex is called the end vertex. Both of them are called end or terminal vertices of the path. The other vertices in the path are internal vertices. Two paths are independent (alternatively called internally vertex‐disjoint) if they do not have any internal vertex in common (Figure 4.2 ). Given an undirected graph, two vertices u and v are called connected if there exists a path from u to v. Otherwise, they are called disconnected. The graph is called a connected graph if every pair of vertices in the graph is connected. A connected component is a maximal connected subgraph. Here, maximal means that it can only be enlarged by rearranging the edges. The giant component

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  C++ Data Structures and Algorithm Design Principles

  Leverage the power of modern C++ to build robust and scalable applications

  • John Carey, Shreyans Doshi, Payas Rajan(Authors)
  • 2019(Publication Date)
  • Packt Publishing

    (Publisher)

  6. Graph Algorithms I

  Learning Objectives

  By the end of this chapter, you will be able to:

  • Describe the utility of graphs for solving various real-world problems
  • Choose and implement the right traversal method to find an element in a graph
  • Solve the minimum spanning tree (MST) problem using Prim's algorithm
  • Identify when to use the Prim's and Kruskal's algorithms to solve the MST problem
  • Find the shortest path between two vertices/nodes in a graph using Dijkstra's algorithm

  In this chapter, we will study the basic and most commonly used algorithms for solving problems that can be represented in the form of graphs, which shall then be discussed further in the next chapter.

  Introduction

  In the previous two chapters, we discussed two algorithm design paradigms: divide and conquer and the greedy approach, which led us to well-known solutions to widely used and important computational problems such as sorting, searching, and finding the minimum weight spanning tree on a graph. In this chapter, we shall discuss some algorithms that are specifically applicable to the graph data structure.

  A graph is defined as a set of vertices and edges that connect a pair of vertices. Mathematically, this is often written as G = < V, E > , where V denotes the set of vertices and E denotes the set of edges that constitute a graph. Edges that point from one node to another are called directed , while edges that have no direction are called undirected . Edges may also be associated with a weight or be unweighted , as we saw in Chapter 2 , Trees, Heaps, and Graphs .

  Note

  The terms "node" and "vertex" can be used interchangeably when we talk about graphs. In this chapter, we shall stick with "vertex."

  Graphs are some of the most versatile data structures – so much so that other linked data structures such as trees and linked lists are known to be just special cases of graphs. What makes graphs useful is that they are the general representation of relationships (represented as edges ) between objects (represented as nodes

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Hands-On Data Structures and Algorithms with Python

  • Dr. Basant Agarwal(Author)
  • 2022(Publication Date)
  • Packt Publishing

    (Publisher)

  9

  Graphs and Algorithms

  Graphs are a non-linear data structure, in which the problem is represented as a network by connecting a set of nodes with edges, like a telephone network or social network. For example, in a graph, nodes can represent different cities while the links between them represent edges. Graphs are one of the most important data structures; they are used to solve many computing problems, especially when the problem is represented in the form of objects and their connection, e.g. to find out the shortest path from one city to another city. Graphs are useful data structures for solving real-world problems in which the problem can be represented as a network-like structure. In this chapter, we will be discussing the most important and popular concepts related to graphs.

  In this chapter, we will learn about the following concepts:

  • The concept of the graph data structure
  • How to represent a graph and traverse it
  • Different operations and their implementation on graphs

  First, we will be looking into the different types of graphs.

  Graphs

  A graph is a set of a finite number of vertices (also known as nodes) and edges, in which the edges are the links between vertices, and each edge in a graph joins two distinct nodes. Moreover, a graph is a formal mathematical representation of a network, i.e. a graph G is an ordered pair of a set V of vertices and a set E of edges, given as G = (V, E) in formal mathematical notation.

  An example of a graph is shown in Figure 9.1 :

  Figure 9.1: An example of a graph

  The graph G = (V, E) in Figure 9.1 can be described as below:

  • V = {A, B, C, D, E}
  • E = {{A, B}, {A, C}, {B, C}, {B, D}, {C, D}, {D, D}, {B, E}, {D, E}}
  • G = (V, E)

  Let’s discuss some of the important definitions of a graph:

  • Node or vertex : A point or node in a graph is called a vertex. In the preceding diagram, the vertices or nodes are A , B , C , D , and E and are denoted by a dot.
  • Edge : This is a connection between two vertices. The line connecting A and B

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Discrete Mathematics

  Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography

  • Sriraman Sridharan, R. Balakrishnan(Authors)
  • 2019(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 1 Graph Algorithms I

  The aim of physical sciences is not the provision of pictures, but the discovery of laws governing the phenomena and the application of these laws to discover new phenomena. If a picture exists, so much the better. Whether a picture exists or not is only a matter of secondary importance.

  P. Dirac

  In this chapter, we study various Algorithms on Graphs. Unfortunately, the graphs are not manipulated by their geometrical representation inside a computer. We start with two important representations of graphs: the adjacency matrix representation and the adjacency list representation. Of course, we have to choose a representation so that the operations of our algorithm can be performed in order to minimize the number of elementary operations.

  After seeing how the graphs are represented inside a computer, two minimum spanning tree algorithms in a connected simple graph with weights associated to each edge, one due to Prim and the other invented by Kruskal are presented. Then, shortest path problems in a weighted directed graph are studied. First, the single-source shortest path problem due to Dijkstra is presented. As an application, an algorithm is given to test the bipartiteness of a graph. Next, a single-source shortest path algorithm for negative edge weights is given. Then, all-pairs shortest path problem due to Floyd and the transitive closure algorithm by Warshall are given. Floyd’s algorithm is applied to find eccentricities of vertices, radius and diameter of a graph.

  Finally, we study a well-known graph traversal technique, called depth-first search. As applications of the graph traversal method, we study the algorithms to find connected components, biconnected components, strongly connected components, topological sort and program evaluation and research technique (PERT). In the last subsection, we study the famous NP-complete problem, traveling salesman problem (TSP) and present the brute-force algorithm and two approximate algorithms. For basic properties of graphs and digraphs, the reader may see [6

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Integer and Combinatorial Optimization

  • Laurence A. Wolsey, George L. Nemhauser(Authors)
  • 2014(Publication Date)
  • Wiley-Interscience

    (Publisher)

  I.3

  Graphs and Networks

  1. INTRODUCTION

  In this section we give the terminology and some elementary results of graph theory. For our purposes the language of graphs is nearly as important as the results, which are elementary and given without proof.

  In the remaining sections, we define some classical optimization problems on graphs and present algorithms to solve them. All of these problems are linear programming problems and, excluding the minimum-weight spanning tree problem, are in the class of linear programming problems known as network flow problems . Their structure makes it possible to solve them by special-purpose algorithms that are more efficient than the simplex method.

  These problems are of interest to us because they frequently arise as subproblems in the solution of integer programs. The algorithms presented in the following sections are examples of classes of algorithms that are used to solve some of the problems considered in Parts II and III. We will introduce the ideas of recursive, greedy, augmenting, primal-dual, and specialized simplex algorithms. So this chapter also has the pedagogical objective of introducing different algorithmic approaches in a simple setting. To explain the basic ideas succinctly, we have deliberately chosen to present simple, rather than efficient, versions of the algorithms. Thus, in this chapter, the reader should not necessarily expect the algorithmic details that yield efficient implementations.

  A graph G = (V, E ) consists of a finite, nonempty set V = {1, 2, … , m } and a set E = {e 1 , e 2 , …, e n ) whose elements are subsets of V of size 2, that is,

  ek

  = (i ,j ), where i , j ∈ V . The elements of V are called nodes , and the elements of E are called edges . Thus graphs are a mechanism for specifying certain pairs of a set.

  Graphs can be represented pictorially in R 2 by points and lines. The points or nodes are placed arbitrarily in the plane, and a line connects points i and j if e = (i , j ) ∈ E . A graph with five nodes and seven edges is shown in Figure 1.1

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Optimization Algorithms for Networks and Graphs

  • James Evans(Author)
  • 2017(Publication Date)
  • CRC Press

    (Publisher)

  Chapter 2 . As some of these optimization algorithms build upon others, the order of presentation is restricted, and these considerations have dictated the sequencing of the chapters of this text.

  1.2 Some Essential Concepts and Definitions

  To decrease the dependence between chapters, some basic concepts and definitions that are needed throughout are presented here. The motivation for these definitions will be reserved to later chapters where applications are discussed in greater depth. Unless specified otherwise, these definitions apply to both directed and undirected graphs.

  We assume that the reader is familiar with basic set notation such as set membership (∈), union (∪), intersection (∩), and subset (⊆). If S is a set, then S ∪ {e } will be written as S + e. If e ∈ S, then S − {e } will be written as S − e. |S| denotes the cardinality of the set S , that is, the number of elements in S. Finally, S ⊕ T = S ∪ T − S ∩ T is the symmetric difference of sets S and T .

  An edge that has both of its endpoints as the same vertex is called a loop. In Fig. 1.5 , edge e 2 is a loop. (Most graphs that we shall consider in this text will contain neither loops nor multiple edges. This will be assumed unless otherwise stated.) If a graph is loopless, does not contain multiple edges, and |X| = m and |E| = n (that is, the graph has m vertices and n edges), then n ≤ m (m − l)/2. Why? A graph in which every pair of vertices are connected by an edge is called a complete graph .

  Fig. 1.5 A graph containing a loop.

  Fig. 1.6 Example of a planar graph.

  A graph is planar if it can be drawn with no two edges crossing each other. The graph in Fig. 1.6a is planar even though it is drawn with two edges crossing each other. Figure 1.6b

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Discrete Mathematics for Computer Science

  An Example-Based Introduction

  • Jon Pierre Fortney(Author)
  • 2020(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  9

  Graph Theory

  Graph theory is used to model many kinds of real world situations, relations, and processes that include communication networks, data organization, and computational devices. Many of the tasks that programmers, computer engineers, and computer scientists need to solve are made much easier by using graph theory. Developing algorithms to handled graphs is very important in computer science. This makes it necessary for you to understand the basic ideas of graph theory.

  9.1 Basic Definitions

  The word graph in the phrase graph theory is very different from what the word graph means when we looked at functions. Now the word graph refers to something else entirely.

  Definition 1. A graph is a set of points called vertex (or vertex) and a set of lines called edges such that each edge is attached to a vertex at each end.

  Very often the vertices are labeled to tell them apart. Two vertices that are connected by an edge are called adjacent vertices. An edge is said to be incident to the vertex to which it is attached. The various edges that are connected to a single vertex are said to be incident to each other. The number of vertices of a graph is called the order of the graph. A graph must have one vertex but it is allowable for a graph to have no edges. A graph that has no edges is sometimes called a null graph.

  Example 9.1

  A graph with six vertices and seven edges. This graph has order six. The vertices are labeled with capital letters.

  A graph that is entirely connected is called a connected graph. However, it is possible for a graph to be disconnected and have several pieces. These pieces are called components of the graph.

  Example 9.2

  A disconnected order nine graph with three components. One component consists of only a single vertex.

  Graphs are made up of a set of vertices, called the vertex set, and a set of edges, called an edge set. Vertices and edges can be labeled many different ways, but for now we will label vertices with capital letters. In order to write down the edge set we have to have a way of labeling edges. In this book the edges will usually be labeled by the two vertices connected by the edge. For example, an edge that connects vertices A and B can be labeled by

  A B

  ¯

  or

  B A

  ¯

  . Usually we will stick with alphabetical ordering and write this edge as

  A B

  ¯

  Sign up to read

  Learn more about book