Chapter 41
Bipartite Graphs and Matrices
Bryan L. Shader
University of Wyoming
An m × n matrix is naturally associated with a bipartite graph, and the structure of the matrix is reflected by the combinatorial properties of the associated bipartite graph. This chapter discusses the fundamental structural theorems for matrices that arise from this association, and describes their implications for linear algebra.
41.1 Basics of Bipartite Graphs
This section introduces the various properties and families of bipartite graphs that have special significance for linear algebra.
Definitions:
A graph G is bipartite provided its vertices can be partitioned into disjoint subsets U and V such that each edge of G has the form {u, υ}, where u ∈ U and υ ∈
Get Handbook of Linear Algebra, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
