Graphs

6 Key excerpts on "Graphs"

• 

  eBook - ePub

  Routledge Revivals: Science as a Questioning Process (1996)

  • Nigel Sanitt(Author)
  • 2017(Publication Date)
  • Routledge

    (Publisher)

  Reduced to a more abstract level, the connection with ordinary graphical representation of functions in mathematics can be appreciated. Normally, one would represent y, for example, as a function of x, pictorially as a curve or graph using Cartesian coordinates. In graph theory instead of taking a continuous range of values, x and y form a direct set of integer values. Each value of x may then be represented as a point, and the mapping of x onto y may be represented as a line joining each of the two values, x and y. The diagram or graph thus obtained has the same abstract form as Euler's graph which he used to solve the Königsberg bridge problem, see figure 3.2. Figure 3.1 Leonhard Euler. (Reproduced by permission of Mary Evans Picture Library.) Figure 3.2 Euler graph for the Königsberg bridge problem. The seven bridges are labelled a to g, and the four separate land areas that the bridges span are labelled A to D. Figure 3.3 Diagram representing the caveman's water cycle questions and answers. The tremendous power of graph theory lies in its flexibility in that it can be thought of either formally in set-theoretical terms, geometrically as in Euler Graphs or even algebraically [2]. For the reader not familiar with this branch of mathematics, one advantage of graph theory is that its objects of study can easily be visualized by the use of graphical examples. For our purposes, the set theoretical definition of a graph inexorably ties graph theory in as the mathematical formalism to represent scientific theories. Formally, a graph G = (v, e) is a finite non-empty set v of elements called vertices, together with a set e of two element subsets of v called edges. Basically, if any sets of objects are connected to each other then they can form a graph. Recall our example of the caveman creating a theory about the water cycle

  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 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
• 

  eBook - ePub

  Graphs Theory and Applications

  With Exercises and Problems

  • Jean-Claude Fournier(Author)
  • 2013(Publication Date)
  • Wiley-ISTE

    (Publisher)

  section 6.4 ).

  1.2 Definition of Graphs

  An (undirected) graph G is defined by two finite sets:3 a non-void set X of elements called vertices , a set E (which can be empty) of elements called edges , with for each edge e two associated vertices, x and y , distinct or not, called the endvertices of e .

  1.2.1 Notation

  We write G = (X , E ). The sets X and E can be denoted by X (G ) and E (G ). The cardinality of X , that is the number of vertices, is usually denoted by n or nG . The cardinality of E , that is, the number of edges, is denoted by m or

  mG

  . The pair of endvertices of an edge e is simply denoted by xy (or yx ) instead of the customary mathematical notation {x , y } when x ≠ y .

  1.2.2 Representation

  It is both usual and practical to draw a graph in a plane in the following manner: the vertices are represented by dots and the edges by simple lines (which can be mathematically defined with precision) connecting two endvertices (see Figure 1.2 ).

  There are, of course, many possible representations for a particular graph because of the different ways there are to place the vertices dots and to trace the edge lines in the plane. For certain applications it is important to find a drawing which shows the structure of the graph, or some of its properties, in relation to the application studied. One example of this is the representation on a screen of the potential task graph in scheduling tasks (discussed in Chapter 6

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Handbook of Graph Theory

  • Jonathan L. Gross, Jay Yellen, Ping Zhang(Authors)
  • 2013(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 1

  Introduction to Graphs

  Section 1.1 Fundamentals of Graph Theory

  Jonathan L. Gross Columbia University Jay Yellen Rollins College

  Introduction

  Configurations of nodes and connections occur in a great diversity of applications. They may represent physical networks, such as electrical circuits, roadways, or organic molecules. They are also used in representing less tangible interactions as might occur in ecosystems, sociological relationships, databases, or in the flow of control in a computer program.

  1.1.1 Graphs and DiGraphs

  Any mathematical object involving points and connections between them may be called a graph . If all the connections are unidirectional, it is called a digraph . Our highly inclusive definition in this initial section of the Handbook permits fluent discussion of almost any particular modification of the basic model that has ever been called a graph.

  Basic Terminology

  Definitions

  D1 : A graph G = (V , E ) consists of two sets V and E .

  • The elements of V are called vertices (or nodes ).
  • The elements of E are called edges .
  • Each edge has a set of one or two vertices associated to it, which are called its endpoints . An edge is said to join its endpoints.

  NOTATION : The subscripted notations V G and E G (or V (G ) and E (G )) are used for the vertex- and edge-sets when G is not the only graph under consideration.

  D2 : If vertex v is an endpoint of edge e , then v is said to be incident on e , and e is incident on v .

  D3: A vertex u is adjacent to vertex v if they are joined by an edge.

  D4: Two adjacent vertices may be called neighbors .

  D5: Adjacent edges are two edges that have an endpoint in common.

  D6: A proper edge is an edge that joins two distinct vertices.

  D7: A multi-edge

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Foundations of Discrete Mathematics with Algorithms and Programming

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

    (Publisher)

  Chapter 4

  Introduction to Graph Theory

  Modélisation: Remplacer du visible compliqué par l’invisible simple.

  J. Perrin

  Mathematics is a reflection of the real-world in the mirror of our thinking.

  G. Polya

  One picture is worth more than a long discourse.

  Napoléon Bonaparte

  The chapter starts with the idea of a graph and basic definitions. An informal, intuitive introduction to NP-complete problems is given. Then multiGraphs, simple Graphs, degree sequences, some special Graphs, Graphs and subGraphs, walks, paths and cycles are introduced. Then we study Graphs and puzzles, and Ramsey numbers. Finally, graph algebra is studied.

  4.1 The Idea of a Graph

  Intuitively, a graph is a diagram consisting of a finite set of points (called vertices ) together with a finite set of arrows , each arrow joining a certain ordered pair of vertices. Here, vertices and arrows are undefined terms like points and lines in geometry. Many real-world situations can be abstracted by means of the concept of the graph. Graphs can be used as mathematical models for systems involving binary relations . A mathematical model is a reflection of some real-world situation. A model must mirror certain essential features of a real situation, but not all. A mathematical model is also a simplification that allows us to study the relevant properties and ignore the others. A model can be smaller or larger or roughly the same size as the thing it represents.

  Vertices of a graph may be interpreted as cities and arcs as highways joining the corresponding pairs of cities or vertices as computers and arcs as possible direct communication between the corresponding computers.

  More formally, we define a graph as follows [1 ]:

  The number of systems of terminology presently used in graph theory is equal, to a close approximation, to the number of graph theorists.

  Richard P. Stanley

  Sign up to read

  Learn more about book