Matching Theory

Matching Theory

Masoud Barah, Ehsan Mazaheri
Copyright: © 2013 |Pages: 15
DOI: 10.4018/978-1-4666-2661-4.ch010
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

Matching theory has a fundamental role in graph theory and combinatorial optimization. The authors introduce the concepts of covering and matching, which have a close relationship. The chapter aims to introduce the matching theory from an industrial engineer’s point of view. To clarify the application of matching theory, two major maximum matching algorithms are described and implemented in two well-known industrial engineering problems.
Chapter Preview
Top

Introduction

To describe the matching theory, we first introduce covering and independent sets of graph G.

Coverings

Vertex covers and edge covers are two subsets of graph G (E, V). While a vertex cover is a subset of vertices, an edge cover is a subset of edges of graph G. The definitions of these two subsets are presented as follows.

Vertex Cover

A Vertex cover of graph G is a subset C of vertices V so that each edge of G is incident to one vertex of this subset, at the minimum. A vertex cover is shown by black vertices in figure 1.

Figure 1.

A vertex cover (black vertices)

978-1-4666-2661-4.ch010.f01

A minimum vertex cover C* is a vertex cover with the minimum possible number of vertices. Minimum vertex cover is not unique necessarily and it is possible to have more than one minimum vertex cover in a graph. The number of vertices in a vertex cover of G is entitled the vertex cover number which is denoted by β(G). A minimal vertex cover is a vertex cover which is not possible to convert it to a vertex cover by omitting a vertex of it. A minimum vertex cover is a minimal vertex cover as well, but conversely, a minimal vertex cover is not a minimum vertex cover necessarily. An example of a minimum vertex cover and a minimal vertex cover is illustrated in figure 2.

Figure 2.

A minimum vertex cover (a) a minimal vertex cover (b)

978-1-4666-2661-4.ch010.f02

Edge Cover

An edge cover of graph G is a subset C of edges E so that each vertex of G is incident to one edge of this subset, at the minimum. An edge cover is shown by dashed lines in figure 3.

Figure 3.

An edge cover (dashed lines)

978-1-4666-2661-4.ch010.f03

A minimum edge cover C* is an edge cover which its edge cover number is minimum. The number of edges in a minimum edge cover of G is named the edge cover number which is denoted by 978-1-4666-2661-4.ch010.m01(G). Minimum edge cover, similar to the minimum vertex cover, is not unique necessarily and it is possible to have more than one minimum edge cover in a graph. A minimal edge cover is an edge cover which none of its subsets is an edge cover as well. A minimum edge cover is always a minimal edge cover as well, but conversely, a minimal edge cover is not a minimum edge cover necessarily. An example of a minimum edge cover and a minimal edge cover is illustrated in figure 4.

Figure 4.

A minimum edge cover (a) a minimal edge cover (b)

978-1-4666-2661-4.ch010.f04

Complete Chapter List

Search this Book:
Reset