87,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Graphs and Networks
A unique blend of graph theory and network science for mathematicians and data science professionals alike.
Featuring topics such as minors, connectomes, trees, distance, spectral graph theory, similarity, centrality, small-world networks, scale-free networks, graph algorithms, Eulerian circuits, Hamiltonian cycles, coloring, higher connectivity, planar graphs, flows, matchings, and coverings, Graphs and Networks contains modern applications for graph theorists and a host of useful theorems for network scientists.
The book begins with applications to biology and the social and political sciences and gradually takes a more theoretical direction toward graph structure theory and combinatorial optimization. A background in linear algebra, probability, and statistics provides the proper frame of reference.
Graphs and Networks also features:
- Applications to neuroscience, climate science, and the social and political sciences
- A research outlook integrated directly into the narrative with ideas for students interested in pursuing research projects at all levels
- A large selection of primary and secondary sources for further reading
- Historical notes that hint at the passion and excitement behind the discoveries
- Practice problems that reinforce the concepts and encourage further investigation and independent work
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 433
Veröffentlichungsjahr: 2022
Ähnliche
Table of Contents
Cover
Title Page
Copyright
Dedication
List of Figures
Preface
1 From Königsberg to Connectomes
1.1 Introduction
1.2 Isomorphism
1.3 Constructions and Minors
Exercises
Topics for Deeper Study
Notes
2 Fundamental Topics
2.1 Trees
2.2 Distance
2.3 Degree Sequences
2.4 Matrices
Exercises
Topics for Deeper Study
Notes
3 Similarity and Centrality
3.1 Similarity Measures
3.2 Centrality Measures
3.3 Eigenvector and Katz Centrality
3.4 PageRank
Exercises
Topics for Deeper Study
Notes
4 Types of Networks
4.1 Small‐World Networks
4.2 Scale‐Free Networks
4.3 Assortative Mixing
4.4 Covert Networks
Exercises
Topics for Deeper Study
Notes
5 Graph Algorithms
5.1 Traversal Algorithms
5.2 Greedy Algorithms
5.3 Shortest Path Algorithms
Exercises
Topics for Deeper Study
Notes
6 Structure, Coloring, Higher Connectivity
6.1 Eulerian Circuits
6.2 Hamiltonian Cycles
6.3 Coloring
6.4 Higher Connectivity
6.5 Menger's Theorem
Exercises
Topics for Deeper Study
Notes
7 Planar Graphs
7.1 Properties of Planar Graphs
7.2 Euclid's Theorem on Regular Polyhedra
7.3 The Five Color Theorem
7.4 Invariants for Non‐planar Graphs
Exercises
Topics for Deeper Study
Notes
8 Flows and Matchings
8.1 Flows in Networks
8.2 Stable Sets, Matchings, Coverings
8.3 Min–Max Theorems
8.4 Maximum Matching Algorithm
Exercises
Topics for Deeper Study
Notes
Appendix A: Linear Algebra
Appendix B: Probability and Statistics
Appendix C: Complexity of Algorithms
Notes
Appendix D: Stacks and Queues
Bibliography
Index
End User License Agreement
List of Illustrations
Chapter 1
Figure 1.1 The bridges of Königsberg.
Figure 1.2 The prism graph.
Figure 1.3 An example of a graph, multigraph, digraph, and network.
Figure 1.4 Traveling salesman network.
Figure 1.5 Strongly connected digraphs.
Figure 1.6 Complete graphs.
Figure 1.7 Paths, cycles, and wheels.
Figure 1.8 Bipartite and tripartite graphs.
Figure 1.9 Star graphs.
Figure 1.10 Example of trees.
Figure 1.11 Subgraphs.
Figure 1.12 Two drawings of a planar graph.
Figure 1.13
C. elegans
connectome.
Figure 1.14
C. elegans
in‐degree (top) and out‐degree (bottom) distributions...
Figure 1.15 Three pairs of isomorphic graphs.
Figure 1.16 The non‐isomorphic graphs on
vertices.
Figure 1.17 The non‐identical graphs on
vertices.
Figure 1.18 Shapes of graphs.
Figure 1.19 The Erdős‐1 collaboration graph.
Figure 1.20 Two non‐isomorphic graphs and their decks of vertex‐deletions.
Figure 1.21 An example of a join.
Figure 1.22 Two examples of Cartesian products.
Figure 1.23 The four‐dimensional cube.
Figure 1.24
and
.
Figure 1.25 Examples of complements.
Figure 1.26 Examples of a subdivision.
Figure 1.27 Line graphs.
Figure 1.28 Forbidden induced subgraphs for line graphs.
Figure 1.29 Example of edge‐deletions and edge‐contractions.
Figure 1.30 Petersen graph.
Figure 1.31 Examples of graphs and digraphs.
Figure 1.32 Pairs of graphs for isomorphism testing.
Figure 1.33 A graph that contains all nine forbidden induced subgraphs for l...
Chapter 2
Figure 2.1 Non‐isomorphic trees on
vertices.
Figure 2.2 Spanning trees.
Figure 2.3 An example for Cayley's tree counting theorem.
Figure 2.4 A tree with a left and right vertex.
Figure 2.5 Eccentricity, diameter, and radius.
Figure 2.6 Cut vertices and bridges.
Figure 2.7 Cospectral graphs with respect to the adjacency matrix.
Figure 2.8 Examples of graphs and digraphs.
Figure 2.9 Three pairs of cospectral graphs.
Chapter 3
Figure 3.1 Customer‐item bipartite graph.
Figure 3.2 A graph and a digraph for centrality measures.
Figure 3.3 A graph and a digraph.
Figure 3.4 Schoch and Brandes graphs.
Figure 3.5 A small town map.
Chapter 4
Figure 4.1
with a standard scale and a log–log scale.
Figure 4.2 The in‐degree distribution of the high energy physics citation di...
Figure 4.3 Classification of 1958 couples based on race.
Figure 4.4 Assortativity function for the Erdős‐1 collaboration graph.
Figure 4.5 Regional Schools Network and Organizations Network.
Chapter 5
Figure 5.1 Step‐by‐step explanation of DFS and BFS.
Figure 5.2 Kruskal's and Prim's algorithms.
Figure 5.3 A Weighted Digraph.
Figure 5.4 Dijkstra's Algorithm.
Figure 5.5 Examples of weighted graphs.
Figure 5.6 Example of a weighted digraph.
Chapter 6
Figure 6.1 Hierholzer's algorithm.
Figure 6.2 Eulerizing graphs.
Figure 6.3 Hamiltonian graphs.
Figure 6.4 Kirkman's graph and
.
Figure 6.5 Non‐Hamiltonian graphs.
Figure 6.6 Closure of a graph.
Figure 6.7 Graph coloring.
Figure 6.8 Greedy Coloring Algorithm.
Figure 6.9 Vertex and edge connectivity.
Figure 6.10 Ear decompositions.
Figure 6.11 An example for Menger's Theorem
Figure 6.12 Deletion and contraction of the edges of
.
Chapter 7
Figure 7.1 Stereographic projection.
Figure 7.2 Geometric dual.
Figure 7.3 Non‐isomorphic graphs with isomorphic geometric duals.
Figure 7.4 Schlegel diagram of a cube.
Figure 7.5 Graphs that do not correspond to convex polyhedra.
Figure 7.6 Platonic solids.
Figure 7.7 Tutte's counterexample to Tait's conjecture.
Figure 7.8
with 3 edge crossings.
Figure 7.9
embedded on the torus.
Chapter 8
Figure 8.1 Network flows.
Figure 8.2 Flow augmenting path.
Figure 8.3 Stable sets, matchings, and coverings.
Figure 8.4 A system of distinct representatives.
Figure 8.5
‐augmenting path.
Figure 8.6 Matchings and blossoms.
Figure 8.7
‐alternating trees.
Figure 8.8 Flower.
Figure 8.9 A graph with a matching.
Figure 8.10 A graph with a larger matching.
4
Figure D.1 Example of a stack.
Figure D.2 Example of a queue.
Guide
Cover Page
Table of Contents
Title Page
Copyright
Dedication
List of Figures
Preface
Begin Reading
Appendix A Linear Algebra
Appendix B Probability and Statistics
Appendix C Complexity of Algorithms
Appendix D Stacks and Queues
Bibliography
Index
End User License Agreement
Pages
iii
iv
v
xi
xii
xiii
xiv
xv
xvi
xvii
xviii
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
227
228
229
230
231
233
234
235
236
237
238
239
240
241
242
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
Graphs and Networks
S. R. Kingan
Brooklyn College and
The Graduate Center,
City University of New York,
New York, NY, USA.
This edition first published 2022
© 2022 John Wiley and Sons, Inc.
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.
The right of S. R. Kingan to be identified as the author of this work has been asserted in accordance with law.
Registered Office
John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA
Editorial Office
111 River Street, Hoboken, NJ 07030, USA
For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.
Wiley also publishes its books in a variety of electronic formats and by print‐on‐demand. Some content that appears in standard print versions of this book may not be available in other formats.
Limit of Liability/Disclaimer of Warranty
The contents of this work are intended to further general scientific research, understanding, and discussion only and are not intended and should not be relied upon as recommending or promoting scientific method, diagnosis, or treatment by physicians for any particular patient. In view of ongoing research, equipment modifications, changes in governmental regulations, and the constant flow of information relating to the use of medicines, equipment, and devices, the reader is urged to review and evaluate the information provided in the package insert or instructions for each medicine, equipment, or device for, among other things, any changes in the instructions or indication of usage and for added warnings and precautions. While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
Library of Congress Cataloging‐in‐Publication Data
Names: Kingan, Sandra, 1966‐ author.
Title: Graphs and networks / Sandra Kingan.
Description: First edition. | Hoboken, NJ : Wiley, 2022. | Includes bibliographical references and index.
Identifiers: LCCN 2021010555 (print) | LCCN 2021010556 (ebook) | ISBN 9781118937181 (cloth) | ISBN 9781118937204 (adobe pdf) | ISBN 9781118937273 (epub)
Subjects: LCSH: Graph theory. | System analysis.
Classification: LCC QA166 .K545 2021 (print) | LCC QA166 (ebook) | DDC 511/.5–dc23
LC record available at https://lccn.loc.gov/2021010555
LC ebook record available at https://lccn.loc.gov/2021010556
Cover Design: Wiley
Cover Image: © Wikipedia
To my father Sion Reuben and
in loving memory of my mother Shery Reuben
List of Figures
Figure 1.1
The bridges of Königsberg.
Figure 1.2
The prism graph.
Figure 1.3
An example of a graph, multigraph, digraph, and network.
Figure 1.4
Traveling salesman network.
Figure 1.5
Strongly connected digraphs.
Figure 1.6
Complete graphs.
Figure 1.7
Paths, cycles, and wheels.
Figure 1.8
Bipartite and tripartite graphs.
Figure 1.9
Star graphs.
Figure 1.10
Example of trees.
Figure 1.11
Subgraphs.
Figure 1.12
Two drawings of a planar graph.
Figure 1.13
C. elegans
connectome.
Figure 1.14
C. elegans
in‐degree (top) and out‐degree (bottom) distributions.
Figure 1.15
Three pairs of isomorphic graphs.
Figure 1.16
The non‐isomorphic graphs on
vertices.
Figure 1.17
The non‐identical graphs on
vertices.
Figure 1.18
Shapes of graphs.
Figure 1.19
The Erdős‐1 collaboration graph.
Figure 1.20
Two non‐isomorphic graphs and their decks of vertex‐deletions.
Figure 1.21
An example of a join.
Figure 1.22
Two examples of Cartesian products.
Figure 1.23
The four‐dimensional cube.
Figure 1.24
and
.
Figure 1.25
Examples of complements.
Figure 1.26
Examples of a subdivision.
Figure 1.27
Line graphs.
Figure 1.28
Forbidden induced subgraphs for line graphs.
Figure 1.29
Example of edge‐deletions and edge‐contractions.
Figure 1.30
Petersen graph.
Figure 1.31
Examples of graphs and digraphs.
Figure 1.32
Pairs of graphs for isomorphism testing.
Figure 1.33
A graph that contains all nine forbidden induced subgraphs for line graphs.
Figure 2.1
Non‐isomorphic trees on
vertices.
Figure 2.2
Spanning trees.
Figure 2.3
An example for Cayley's tree counting theorem.
Figure 2.4
A tree with a left and right vertex.
Figure 2.5
Eccentricity, diameter, and radius.
Figure 2.6
Cut vertices and bridges.
Figure 2.7
Cospectral graphs with respect to the adjacency matrix.
Figure 2.8
Examples of graphs and digraphs.
Figure 2.9
Three pairs of cospectral graphs.
Figure 3.1
Customer‐item bipartite graph.
Figure 3.2
A graph and a digraph for centrality measures.
Figure 3.3
A graph and a digraph.
Figure 3.4
Schoch and Brandes graphs.
Figure 3.5
A small town map.
Figure 4.1
with a standard scale and a log–log scale.
Figure 4.2
The in‐degree distribution of the high energy physics citation digraph.
Figure 4.3
Classification of 1958 couples based on race.
Figure 4.4
Assortativity function for the Erdős‐1 collaboration graph.
Figure 4.5
Regional Schools Network and Organizations Network.
Figure 5.1
Step‐by‐step explanation of DFS and BFS.
Figure 5.2
Kruskal's and Prim's algorithms.
Figure 5.3
A Weighted Digraph.
Figure 5.4
Dijkstra's Algorithm.
Figure 5.5
Examples of weighted graphs.
Figure 5.6
Example of a weighted digraph.
Figure 6.1
Hierholzer's algorithm.
Figure 6.2
Eulerizing graphs.
Figure 6.3
Hamiltonian graphs.
Figure 6.4
Kirkman's graph and
.
Figure 6.5
Non‐Hamiltonian graphs.
Figure 6.6
Closure of a graph.
Figure 6.7
Graph coloring.
Figure 6.8
Greedy Coloring Algorithm.
Figure 6.9
Vertex and edge connectivity.
Figure 6.10
Ear decompositions.
Figure 6.11
An example for Menger's Theorem
Figure 6.12
Deletion and contraction of the edges of
.
Figure 7.1
Stereographic projection.
Figure 7.2
Geometric dual.
Figure 7.3
Non‐isomorphic graphs with isomorphic geometric duals.
Figure 7.4
Schlegel diagram of a cube.
Figure 7.5
Graphs that do not correspond to convex polyhedra.
Figure 7.6
Platonic solids.
Figure 7.7
Tutte's counterexample to Tait's conjecture.
Figure 7.8
with 3 edge crossings.
Figure 7.9
embedded on the torus.
Figure 8.1
Network flows.
Figure 8.2
Flow augmenting path.
Figure 8.3
Stable sets, matchings, and coverings.
Figure 8.4
A system of distinct representatives.
Figure 8.5
‐augmenting path.
Figure 8.6
Matchings and blossoms.
Figure 8.7
‐alternating trees.
Figure 8.8
Flower.
Figure 8.9
A graph with a matching.
Figure 8.10
A graph with a larger matching.
Figure D.1
Example of a stack.
Figure D.2
Example of a queue.
Preface
Network science is another name for the modern applications of graph theory and should be studied alongside the usual theorems and techniques in a graph theory course. On the other hand, data scientists, biologists, physicists, and social scientists using networks as models might be interested in the theory behind the results they use. This book attempts to bridge the growing division between graph theory and network science by weaving theory, algorithms, and applications together into the narrative. Only the theorems are numbered because it is through them that the subject unfolds. Moreover, a curated selection of theorems is presented to make the text read like a story, except that this is not fiction and the story never ends.
Chapter 1 presents a broad overview of the book and the basic concepts and examples used throughout the book. Chapter 2 presents foundational topics such as trees, distance, and matrices that represent graphs. Chapters 3 and 4 contain applications found in network science books such as centrality measures, small‐world networks, and scale‐free networks. Their inclusion early in the book indicates their importance and emphasizes how little classical graph theory these applications require. They do, however, require a working knowledge of elementary linear algebra, probability, and statistics. The required concepts are in Appendices A and B. Chapter 5 and Appendices C and D provide an introduction to graph algorithms including graph traversal algorithms, greedy algorithms, and shortest path algorithms. Subsequently, algorithms are treated as an integral part of the story. Chapter 6 is a collection of results on Eulerian circuits, Hamiltonian cycles, coloring, and higher connectivity including Menger's Theorem and the Splitter Theorem. Chapter 7 provides an introduction to planar graphs. Chapter 8 is on flows, stable sets, matchings, and coverings, and ends with Edmonds' Blossom Algorithm, one of the finest examples of a graph algorithm.
The following two quotes by Jacob Lawrence and Albert Einstein, respectively, capture my approach to writing this book: “when the subject is strong, simplicity is the only way to treat it” and “everything should be made as simple as possible, but not simpler.” The book is full of results with short and simple proofs designed to build confidence in reading and understanding proofs. On the other hand, applications such as Google's PageRank require a fairly good grasp of linear algebra. Explaining PageRank without mentioning eigenvalues is certainly possible, however, doing so detracts from the ideas behind this application.
This book is written so that students can review the material and come prepared for a discussion in the classroom. The selection of results in this book gradually increases in difficulty and makes self–study possible. The exercises encourage playing with examples and experimentation. Each chapter has a list of topics suitable for independent study projects and research experiences.
The book also serves as a guide for navigating the large amount of free graph theory and network science resources on the web. Most papers can be obtained within seconds via a web search. Many older textbooks are freely available on the Internet. All these excellent resources for further study are built into the narrative. Students are encouraged to begin gathering original sources as a matter of routine. A seemingly random collection of papers may initially have no connection, but gradually patterns will appear and point toward a research project.
My husband Robert Kingan helped me with the algorithms, figures and references. This book would never have been completed without his encouragement and assistance. My sons Rohan, Arun, and Ravi cheered me on. My colleagues from the New York combinatorics group Kira Adaricheva, Deepak Bal, Nadia Benakli, Jonathan Cutler, Ezra Halleck, Joseph Malkevitch, Eric Rowland, Kerry Ojakian, Peter Winkler, and Mingxian Zhong gave valuable feedback. Many thanks to Noemi Halpern and Murray Hochberg for their long standing support and encouragement and the anonymous reviewers for their nice reviews of my original book proposal. My students helped me by finding typos and errors. I was able to refine explanations by teaching the same topics over and over again. Last, but not least, Susanne Filler, the original acquisitions editor for this book, the expert team at Wiley, Inc. Kimberly Hill, Kalli Schultea, and Gayathree Sekar have been patient and easy to work with. I am grateful to all noted here and to many others who helped in bringing this book to fruition.
My goal in writing this book will be accomplished if students find the material interesting; perhaps interesting enough to pursue research in it. I wrote the book so that chapters can be added ad infinitum. Is your favorite topic missing? Let me know and I'll write a chapter on it and post it online. This is a living and growing book. The book that you hold in your hands is the beginning of a never–ending story.
S. R. Kingan
Brooklyn College and The Graduate Center
The City University of New York
New York, NY
1From Königsberg to Connectomes
Section 1.1 is a broad introduction to graph theory and network science. Sections 1.2 and 1.3 introduce the nuts and bolts of the subject. Section 1.2 describes when two graphs may be considered the same. Section 1.3 describes ways of obtaining new graphs from old ones and ends with a detailed discussion on minors.
1.1 Introduction
Our story begins in eighteenth century Königsberg, now known as Kaliningrad, a Russian city between Poland and Lithuania. The citizens of Königsberg enjoyed taking walks across the seven bridges over the river Pregel. Some had noticed that they could not cross all the bridges exactly once and return home. Swiss mathematician Leonhard Euler heard about this puzzle and wrote a paper on it called “Solution of a problem relating to the geometry of position” (Euler, 1736). His paper had the simple schematic representation of a map shown in Figure 1.1, where the land masses are labeled . This drawing subsequently became the point and line drawing that is called a graph. The points are called vertices or nodes and the lines are called edges or links.1
Euler explained that if there was a way of walking along the edges of the graph, crossing every edge exactly once, and returning to the starting vertex, then one would have to enter and leave a vertex the same number of times. Therefore every vertex must have an even number of edges incident to it. Further, he observed that this necessary condition was also sufficient. Euler did not prove sufficiency. A young German mathematician by the name of Carl Hierholzer gave the first complete proof of this result (Hierholzer, 1873).
Figure 1.1 The bridges of Königsberg.
Let us change the question slightly and ask “Is there a way of walking along the edges of the graph so as to cross every vertex exactly once, and return to the starting vertex?” This question, posed in the mid‐nineteenth century independently by British mathematicians Thomas Kirkman and William Hamilton (Kirkman, 1856; Hamilton, 1858), is still unresolved. There are many theorems giving necessary conditions and many giving sufficient conditions. However, a theorem giving a necessary and sufficient condition, if such a theorem exists, remains elusive.
A graph is defined as a finite non‐empty set of objects called vertices or nodes together with a set of unordered pairs of distinct vertices called edges or links. Typically a graph is denoted by the letter , the vertex set by or just when the context is clear, and the edge set by or . The number of vertices is called the order of and the number of edges is called the size of . Throughout the book stands for the number of vertices and stands for the number of edges. All this information is summarized by writing .2
The graph in Figure 1.2 is called the prism graph since it looks like a flattened rectangular prism viewed from the top. It has vertex set
and edge set
where , , , , , , , , and . The edges are unordered pairs of vertices, so we may write, for example, . Two vertices linked by an edge are called adjacent vertices. Two edges with a common vertex are called adjacent edges. For example, and are adjacent vertices and and are adjacent edges. The end vertices of an edge are said to be incident to the edge. For example, is incident to edge .
Figure 1.2 The prism graph.
The degree of a vertex , denoted by , is the number of edges incident to it. In a graph with vertices, the degree of each vertex is at most since each vertex can be joined to at most of the remaining vertices. The degree sequence of a graph is an unordered list of the degrees. The minimum degree is denoted by and the maximum degree is denoted by . If all the vertices have the same degree, then the graph is called a regular graph. For example, the prism graph in Figure 1.2 is a regular graph since every vertex has degree 3. A regular graph of degree 3 is called a cubic graph. The neighborhood of vertex , denoted by , is the set of all vertices joined by an edge to . By convention is not in .
The graph with just one vertex is called the trivial graph and a graph with vertices, but no edges, is called an isolated graph. A vertex with no edges incident to it is called an isolated vertex.
A directed graph (also called digraph) is a graph whose edges have a direction. The directed edges, called arcs, are ordered pairs of vertices. The arrow on arc points from to . Vertex is called the initial vertex and vertex is called the terminal vertex. The outdegree of vertex , denoted by , is the number of arcs that have as the initial vertex. The indegree of vertex , denoted by , is the number of arcs that have as the terminal vertex. The degree sequence of a digraph with vertices, where each vertex has indegree and outdegree , is given by the list of ordered pairs .
Figure 1.3 An example of a graph, multigraph, digraph, and network.
A loop is an edge from a vertex to itself. Multiple edges between a pair of vertices are called parallel edges. A multigraph is a graph with loops or parallel edges. The Königsburg bridge graph shown in Figure 1.1 is a multigraph.3
A graph that has a real number associated with each edge is called a network.4 The numbers are called weights or costs. Figure 1.3 gives an example of a graph, digraph, multigraph, and network.
A complex network is a real‐world network, so large and complicated that it can only be studied empirically. Vertices and edges of a complex network may not be fully known or may be constantly changing. Complex networks are everywhere. Examples include:
The neurons in the brain linked by synapses (called a connectome);
The Internet with wired or wireless links between computers;
The World Wide Web with hypertext links connecting webpages;
Networks of people where the link is based on some sort of relationship (called social networks); and
Networks of people where the link is catching a contagious disease such as Ebola or COVID‐19 (called epidemic or pandemic networks).
The study of complex networks has become an established interdisciplinary field called Network Science that is populated by physicists, biologists, computer scientists, and social scientists.
A walk in a graph is an ordered sequence of vertices and edges
where is an edge for .5 Vertices and edges may be repeated in a walk. A trail is a walk with no edge repeated. A path is a walk with no vertex repeated. A closed walk is one in which the first and last vertex are the same. Closed trails and paths are defined in a similar manner. A closed trail is called a circuit. A closed path is called a cycle.
For example, in the prism graph shown in Figure 1.2
is a walk from to . Notice how vertices and edges are repeated. In a trail vertices may be repeated, but not edges. For example,
is a trail from to . In a path vertices are not repeated, and consequently edges are not repeated. For example,
is a path from to and
is a cycle. For paths and cycles we may use just vertices or just edges since there are no repetitions and therefore no cause for confusion. The aforementioned path may be written as and the cycle may be written as . Alternatively, we may refer to this particular path and cycle by their edges as and , respectively.
Two walks, trails, or paths are equal if they have exactly the same vertices and edges. The length of a walk, trail, path, circuit, or cycle is the number of edges in it (counting repetitions when relevant). The girth of a graph is defined as the length of the shortest cycle in the graph. A cycle of length 3 is called a triangle.
A circuit that crosses every edge in the graph exactly once is called an Eulerian circuit, and a graph with an Eulerian circuit is called an Eulerian graph. A cycle that crosses each vertex in the graph exactly once is called a Hamiltonian cycle, and a graph with a Hamiltonian cycle is called a Hamiltonian graph. As mentioned earlier. Euler gave a complete characterization of graphs with Eulerian circuits, however, a necessary and sufficient condition for the presence of a Hamiltonian cycle is not known.
Suppose a salesman travels to each of cities exactly once and returns home. The cities form the vertices of a graph and the routes between cities are the edges. The weights on the edges are the costs of traveling from one city to the other. Consider the problem of finding the cheapest route. For example, in the network shown in Figure 1.4, we could list all possible routes (that would be routes) to check which one is the cheapest route. This brute‐force approach would work for five cities, but what if the traveling salesman is visiting 100 cities? The number of possible routes is . Is there an efficient algorithm? No one knows. This is called the Traveling Salesman Problem, and it is one of the Clay Institute's million dollar problems.6
Walks, trails, paths, and cycles in a digraph are defined in a similar manner with the understanding that the direction of the edges must be taken into account while navigating the digraph. A directed path in a digraph is an ordered sequence of distinct vertices , where is an arc for . A directed cycle is a closed directed path.
A non‐trivial graph is connected if there is a path between every pair of vertices. Otherwise the graph is disconnected. By convention the trivial graph is considered to be connected. The distance between a pair of distinct vertices and in a connected graph , denoted by , is the length of the shortest path between and . The diameter, denoted by , is the maximum distance between any pair of vertices. For example, the prism graph shown in Figure 1.2 has diameter 2.
A connected digraph is one whose underlying graph is connected. If, for every pair of vertices and , there are directed paths from to and from to , then the digraph is called strongly connected. The digraph in Figure 1.3 is connected, but not strongly connected. There is no directed path from to . Figure 1.5 displays two strongly connected digraphs.
Figure 1.4 Traveling salesman network.
Figure 1.5 Strongly connected digraphs.
In a strongly connected digraph the directed distance between vertices and is the length of the shortest directed path from to . Note that in a digraph is not necessarily the same as . The diameter of a strongly connected digraph is the maximum distance between any pair of vertices. The first digraph in Figure 1.5 has diameter 4 and the second has diameter 3.
The graph in which every pair of vertices is joined by an edge is called a complete graph. The complete graph on vertices is denoted by (see Figure 1.6). The number of edges in is since every pair of vertices is joined by an edge. Similarly, the digraph in which every pair of vertices and is joined by arcs and is called a complete digraph. The number of arcs in a complete digraph on vertices is .
Next, let us look at some frequently used examples of graphs. These are the toy examples we will use to understand new concepts. The path , for , the cycle graph , for , and the wheel graph , for are three families of graphs shown in Figure 1.7. Observe that for the number of edges is ; for the number of edges is ; and for the number of edges is since the number of spokes in the wheel graph is .
A graph is called bipartite if its vertex set can be written as , where and are disjoint and every edge joins a vertex in to a vertex in . A graph is called complete bipartite if every vertex in is joined to every vertex in . A complete bipartite graph with vertices in and vertices in is denoted by .
Figure 1.6 Complete graphs.
Figure 1.7 Paths, cycles, and wheels.
We can generalize this notion to ‐partite graphs, where the vertex set is partitioned into pairwise disjoint subsets in such a way that every edge joins a vertex in to a vertex in , for and . A graph is called complete‐partite if every vertex in is joined to every vertex in . A complete ‐partite graph with vertices in is denoted by . Figure 1.8 shows examples of bipartite and tripartite graphs. The complete bipartite graph with vertices is called the star graph. See Figure 1.9.
Graphs with no cycles are called acyclic graphs. A connected acyclic graph is called a tree. An acyclic graph is called a forest. The terminology is evocative of trees in a forest. The term tree appears in an 1857 paper by British mathematician Arthur Cayley titled “On the theory of the analytical forms called trees” (Cayley, 1857).7 Cayley was trying to enumerate the isomers of saturated hydrocarbons such as methane, ethane, butane, etc., which have the form . An isomer is a molecule with the same chemical formula as another molecule, but with a different arrangement of atoms and different properties. These molecules can be represented by trees as shown in Figure 1.10.
Figure 1.8 Bipartite and tripartite graphs.
Figure 1.9 Star graphs.
There are many ways to define a substructure of a graph. The most obvious way is to delete some vertices and edges. A graph is a subgraph of a graph if and . In the definition of subgraph we understand that if an edge is in , then both its end vertices are in . A proper subgraph of is a subgraph that is not the empty set or . A subgraph with is called a spanning subgraph. Figure 1.11 displays a graph and three subgraphs , , and . Observe that is a spanning subgraph.
Figure 1.10 Example of trees.
Figure 1.11 Subgraphs.
Sometimes we may want to pick a subset of vertices and look at the subgraph obtained by taking all the edges present that join those vertices. Such a subgraph is said to be “induced” by the subset of vertices. Let . The subgraph induced by , called an induced subgraph, has vertex set and edge set those edges in incident with two vertices in . For example, subgraph in Figure 1.11 is induced by , whereas subgraph is not an induced subgraph.
A subgraph that is a complete graph is called a clique. A maximal clique in a graph is a complete subgraph that cannot be made larger by adding more vertices. A maximum clique is a maximal clique that has the most number of vertices.
A graph is called planar if it can be drawn on the plane without crossing edges. Otherwise it is called non‐planar. Figure 1.12 gives an example of a planar graph. In the first rendition it is drawn with edges crossing. However, a re‐drawing shows that it can be drawn without edges crossing. This graph is with one edge deleted. What about and ? A few attempts to draw them without crossing edges will reveal that it is impossible. This is because and are non‐planar.
A map corresponds to a type of planar graph. Vertices can be placed on the countries and two vertices are joined by an edge if the corresponding countries share a common border. Mapmakers have known since antiquity that at most four colors are needed to color two adjacent countries with different colors (countries that meet in a point may be colored the same color). This belief came to be known as the “Four Color Conjecture.” It was brought to the attention of British mathematician Augustus de Morgan in 1852 by one of his students Federick Guthrie, who attributed it to his brother Francis Guthrie (Biggs et al., 1976). De Morgan wrote about it to Hamilton who replied saying he did not find it interesting. In 1976 two American computer scientists from the University of Illinois at Urbana Champaign, Kenneth Appel and Wolfgang Haken, proved the Four Color Conjecture. Their proof is notable in that their mathematical arguments reduced the proof to case‐checking of nearly cases for which they used a computer. Initially some mathematicians were suspicious of a proof with a computer component, but in time that attitude changed. To commemorate the occasion the university postmark had the slogan “Four colors suffice.” A subsequent proof with fewer cases has also been published (Robertson et al., 1997a).
Figure 1.12 Two drawings of a planar graph.
In 1930 Polish mathematician Kazimierz Kuratowski proved that every non‐planar graph contains either or as a substructure called a subdivision (Kuratowski, 1930). A subdivision of a graph is obtained by placing vertices on edges. Klaus Wagner built on this by proving that every non‐planar graph contains either or as a substructure called a minor (Wagner, 1937). A minor of a graph is obtained by deleting edges (and any isolated vertices formed as a result) and “contracting edges.” An edge is contracted by shrinking it and fusing its end vertices into one vertex. Subdivisions and minors are described in detail in Section 1.3.
A class of graphs is said to be closed under minors if every minor of a graph in is also in . A graph that is not in is called a minimal excluded minor8 if all of its proper minors are in . Wagner conjectured that every infinite class of graphs closed under minors has a finite set of minimal excluded minors. This conjecture was confirmed by Neil Robertson and Paul Seymour in a series of 23 papers the first of which appeared in 1983 (Robertson and Seymour, 1983) and the last of which appeared in 2010 (Robertson and Seymour, 2010). These papers totaling over 500 pages proved the conjecture as well as dozens of related results and mapped out a thriving research genre.
In the 1930s considerable progress was made in graph theory. In addition to Kuratowski and Wagner's structural result, Karl Menger proved a major connectivity result (Menger, 1927), Frank Ramsey introduced what we now call Ramsey Theory (Ramsey, 1930), Phillip Hall solved the Marriage Problem (Hall, 1935), Hassler Whitney introduced matroids (Whitney, 1935), and Dénes König wrote the first graph theory textbook (König, 1936).9 Less well known is a graph theoretical development in social psychology. At the 1933 meeting of the New York Medical Society, psychiatrist Jacob L. Moreno presented a graph showing the friendship of boys and girls in a fourth grade class. His work appeared in the New York Times in an article dated April 3, 1933 titled “Emotions mapped by Geography.” He is credited with making a far‐sighted statement:
If we ever get to the point of charting a whole city or a whole nation, we would have a picture of a vast solar system of intangible structures, powerfully influencing conduct, as gravitation does in space. Such an invisible structure underlies society and has its influence in determining the conduct of society as a whole.
Moreno's friendship graph is cited by sociologists as the first example of a social network. His 1934 book Who Shall Survive: A New Approach to the Problem of Human Interrelations (Moreno, 1934) has, among other things, several examples of social networks (he called them sociograms) with detailed instructions for drawing them using color, size, and shape of vertices to convey information.
For small graphs it makes sense to list the degrees of the vertices and talk about the degree sequence. For large graphs the list of degrees is too long. So we talk about the frequency distribution of the degrees. The degree distribution of a graph is a frequency histogram with the degrees on the ‐axis and the number of vertices of each degree on the ‐axis. The indegree distribution and outdegree distribution of a digraph are defined in a similar manner.
In a 1965 study of the citation digraph, where vertices are scientific papers and an arc from to indicates cites , physicist and historian Derek de Solla Price observed that the degree distribution of the citation digraph followed the power law function, , where and are constants. Most papers had three to seven citations and only a few papers had many citations (Price, 1965). Graphs whose degree distributions follow the power law function are called scale‐free networks. The name scale‐free comes from the observation that since most vertices have small degree and a few have large degree, the average of the degrees is meaningless.
Meanwhile social psychologist Stanley Milgram conducted his “small‐world” experiment, where he randomly selected a group of individuals and gave them letters addressed to someone they didn't know. The goal of the experiment was for each person to send the letter to a person they knew, who in turn sent the letter to a person they knew, and so on. On average Milgram found that the letters reached their destination through six connections (Milgram, 1963). Subsequently these ideas led to the notion of small‐world graphs (Watts and Strogatz, 1998).
A centrality measure is a way of quantifying the most important people in a social network. This approach to determining the importance of an individual based on relations with others in the network, and not just on the individual's attributes, was evidently a paradigm shift in sociological thinking. In 1998 Sergey Brin and Larry Page, two Stanford University students, developed a new type of centrality measure called PageRank to determine the importance of a webpage (Brin and Page, 1998). Their company, Google, needs no introduction. In 2004 Harvard student Marc Zuckerberg and his company Facebook made social networks a household term. In 2016 fake news spread through networks of like‐minded individuals creating echo‐chambers and 2020 brought us the coronavirus pandemic and the unprecedented quarantine and lock‐down. Contact‐tracing to form the network of people exposed to COVID‐19 entered our lexicon. The killing of unarmed black men and women created an uprising and the “Black Lives Matter” movement was born. Predictive‐policing based on a smattering of mathematics including graph theory and a large dose of bias appears to have fallen out of favor, for the time being at least.
With this brief initiation into tribal knowledge, let us begin with what is universally considered the first proposition in graph theory.
Proposition 1.1.1. The sum of the degrees of the vertices in a graph is twice the number of edges.
Proof. Each edge has exactly two end vertices and therefore contributes exactly two to the sum of the degrees.
Let be a graph with vertices and edges. We may write Proposition 1.1.1 as
Proposition 1.1.2. The number of vertices of odd degree is even.
Proof. Let be the set of vertices of even degree and be the set of vertices of odd degree. By Proposition 1.1.1
Observe that is even because it is a sum of even numbers. Moreover, is clearly even, so must be even. Since each vertex has odd degree, the only way to get an even sum is if the number of odd degree vertices is even.
Proposition 1.1.2 is called the Handshake Lemma. At a party, consider the people as vertices and assume that two people shaking hands are linked by an edge. We can be certain that the number of people who greet an odd number of acquaintances is even.
Proposition 1.1.3. In a digraph the sum of the indegrees is equal to the sum of the outdegrees and this sum is equal to the number of arcs.
Proof. Every arc leaves exactly one vertex and enters exactly one vertex. So every arc contributes one to the sum of the indegrees and one to the sum of the outdegrees.
Let be a digraph with vertices and arcs. We may write Proposition 1.1.3 as
The last proposition in this section is a straightforward example of a constructive proof (König, 1936).
Proposition 1.1.4. Letbe a graph with maximum degree. There exists a regular graph of degreethat containsas an induced subgraph.
Proof. If is a regular graph, then there is nothing to prove. Therefore suppose is not a regular graph. Let be a copy of and link the corresponding vertices in and whose degrees are less than . Call the resulting graph . If is regular, then is the required regular graph containing as an induced subgraph. If not, let be a copy of and link corresponding vertices whose degrees are less than . Continue like this until we arrive at a regular graph of degree , where , as shown in the following diagram.
A graph and a regular graph with as an induced subgraph.
Note that the proof of Proposition 1.1.4 gives a method for constructing a regular graph containing as an induced subgraph, but not necessarily the smallest regular graph containing .
Returning to complex networks, the graph that consists of neurons as vertices and the synapses that connect neurons as edges is called a connectome. Depending on the context, it refers to the neurons in the brain or to the neurons in the entire nervous system. The idea that the nervous system is composed of a finite number of nerve cells linked to other cells forming a digraph goes back to Spanish pathologist Santiago Ramón y Cajal in the beginning of the twentieth century. At that time, the “Neuron doctrine” was controversial. Camillo Golgi, inventor of a silver staining technique in 1873, had proposed that the nervous system was a continuous single thread. Cajal proposed a discrete model for the brain of a chicken (Garcia‐Lopez et al., 2010
