Graph Theory
Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to model pairwise relations between objects. It involves the exploration of properties and applications of graphs, such as paths, cycles, connectivity, and coloring. Graph theory has applications in various fields including computer science, operations research, and social network analysis.
7 Key excerpts on "Graph Theory"
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- Jesus Rogel-Salazar(Author)
- 2020(Publication Date)
- Chapman and Hall/CRC(Publisher)
...We need to be mindful, of course, of the data privacy issues that may arise when sourcing information from various social media platforms and other sources of information. This is not just important in the analysis of social networks, but indeed more general to any data science work we are involved with. Be a good Jackalope data scientist! 3.2 Let’s Make a Connection: Graphs and Networks N OW THAT WE HAVE A better idea of the applications and usefulness of networks, it is time to provide some of the notions that underpin the framework that enables us to understand the connections (edges) between the actors (nodes) in a given network. That framework is largely built around Graph Theory, a branch of mathematics interested in the properties of graphs. As we saw in the previous section, the basic idea of graphs was introduced by Euler and in this section we will address some important aspects we need to understand to work with graphs, but we will not cover Graph Theory in its full glorious interconnectedness. Graph Theory is a branch of mathematics interested in the properties of graphs. Up until now we have defined a graph in a loose way. Let us correct that and define a graph G as an object that consists of a collection of nodes or vertices V, and arcs or edges E, that connect pairs of vertices and can be expressed as G = (V, E). We will refer to an arc as a directed connection between two nodes. If we consider two nodes υ 1 and υ 2 in G, an arc will be denoted as the ordered pair (υ 1, υ 2). If the connection is undirected, we will refer to it as an edge and will be denoted as (υ 1 : υ 2). Notice that the order in this case is irrelevant. G = (V, E) denotes the graph G with nodes V and edges E. The neighbours of a node υ i are denoted as N (υ i) and are all the nodes immediately connected to υ i. A walk in graph G is a sequence that traverses the graph from neighbour to neighbour. The length | s | of the walk is the number of lines it contains...
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 - 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- Gary Chartrand(Author)
- 2012(Publication Date)
- Dover Publications(Publisher)
...*Chapter 10 Graphs and Other Mathematics Graph Theory has close relationships with several mathematical areas. In this chapter we consider three of these areas: matrices, topology, and groups. 10.1 Graphs and Matrices A 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. Let G be a graph of order p with vertices denoted by v 1, v 2,..., v p. Then the adjacency matrix A = A (G) = [ a ij ] is that p x p matrix in which a ij = 1 if v i and v j are adjacent and a ij = 0 otherwise. Thus, the matrix A is a (0, 1) matrix (i.e., every entry of A is 0 or 1); the main diagonal of A consists entirely of 0’s (i.e., a ii = 0 for i = 1, 2,..., p); and A is symmetric (i.e., a ij = a ji for 1 ≤ i ≤ p and 1 ≤ j ≤ p). A graph G and its adjacency matrix are given in Figure 10.1. Figure 10.1 Note that the adjacency matrix of a graph G ordinarily depends on how we label the vertices. For example, the graph G of Figure 10.1 is shown again in Figure 10.2 with a different labeling, resulting in a different adjacency matrix. Although the matrices of Figures 10.1 and 10.2 are unequal (as matrices), they represent isomorphic graphs. Figure 10.2 One interesting property of an adjacency matrix of a graph concerns the entries of its various powers...
eBook - ePub- Wai Kai Chen(Author)
- 2004(Publication Date)
- Academic Press(Publisher)
...2 Circuit Analysis: A Graph-Theoretic Foundation Krishnaiyan Thulasiraman, School of Computer Science, University of Oklahoma, Norman, Oklahoma, USA M.N.S. Swamy, Department of Electrical and Computer Engineering, Concordia University, Montreal, Quebec, Canada 2.1. Introduction 2.2. Basic Concepts and Results 2.2.1. Graphs 2.2.2. Basic Theorems 2.2.3. Cuts, Circuits, and Orthogonality 2.2.4. Incidence, Circuit, and Cut Matrices of a Graph 2.3. Graphs and Electrical Networks 2.3.1. Loop and Cutset Transformations 2.4. Loop and Cutset Systems of Equations 2.4.1. Loop Method of Network Analysis 2.4.2. Cutset Method of Network Analysis 2.5. Summary 2.1 Introduction The theory of graphs has played a fundamental role in discovering structural properties of electrical circuits. This should not be surprising because graphs, as the reader shall soon see, are good pictorial representations of circuits and capture all their structural characteristics. This chapter develops most results that form the foundation of graph theoretic study of electrical circuits. A comprehensive treatment of these developments may be found in Swamy and Thulasiraman (1981). All theorems in this chapter are stated without proofs. The development of Graph Theory in this chapter is self-contained except for the definitions of standard and elementary results from set theory and matrix theory. 2.2 Basic Concepts and Results 2.2.1 Graphs A graph G = (V, E) consists of two sets: a finite set V = (v 1, v 2, … v n) of elements called vertices and a finite set E = (e 1, e 2, … e n) of elements called edges. If the edges of G are identified with ordered pairs of vertices, then G is called a directed or an oriented graph; otherwise, it is called an undirected or an unoriented graph. Graphs permit easy pictorial representations. In a pictorial representation, each vertex is represented by a dot, and each edge is represented by a line joining the dots associated with the edge...
eBook - ePubPhilosophy of Mathematics
An Introduction to a World of Proofs and Pictures
- James Robert Brown(Author)
- 2005(Publication Date)
- Routledge(Publisher)
...G′ = 〈{a,b,c,d,e}, {{a,b}, {b,c}, {b,d}}〉 has five vertices and three edges. Note that the basic definition of a graph is given completely in set theory terms. 3 No sooner are such definitions and examples given, than the typical text on Graph Theory says that it would be natural to show a picture of the graphs. Our two examples, G and G′, look like this: Looking at both the set theory definition and at the diagram, it is little wonder that working mathematicians (as well as the rest of us onlookers) have a strong preference for the picture. Nevertheless, the set theory definition proves to be very useful, for example, in letting us know that Figure 7.2 is a picture of the same graph as Figure 7.1(b), in spite of their very different appearances. Figure 7.1 The graphs G (left) and G′ (right) A planar graph is one which can be drawn with no edges crossing. The graph (known as K 4) in Figure 7.3(a) can be redrawn as in Figure 7.3(b). (K 4 is called a complete graph because each vertex is joined to every other vertex.) The so-called utility graph (Figure 7-4) is not a planar graph. (Try redrawing it without any crossing lines; you will quickly become convinced that it cannot be done.) Figures 7.3 and 7.4 The graph 7.3(a) is planar since it can be redrawn as 7.3(b); 7.4 is not planar There are different ways of proving a graph non-planar. One way uses the Jordan Curve Theorem which says that any simple closed curve divides the plane into two regions and that any continuous line from inside to outside cuts the boundary. The ideas of crossings, being planar, and the use of the Jordan Curve Theorem, etc. all make essential use of the diagrammatic representation of graphs. A fundamental theorem in Graph Theory is Euler’s theorem which we saw earlier in connection with polyhedra (and will see again below)...
