Matching

Материал из WEGA
Версия от 17:20, 31 мая 2011; Glk (обсуждение | вклад) (Новая страница: «'''Matching''' --- паросочетание. For a graph <math>G = (V,E)</math>, a subset <math>E' \subseteq E</math> such that for all edges <math>e, e' \in E'<…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Matching --- паросочетание.

For a graph [math]\displaystyle{ G = (V,E) }[/math], a subset [math]\displaystyle{ E' \subseteq E }[/math] such that for all edges [math]\displaystyle{ e, e' \in E' }[/math] with [math]\displaystyle{ e \neq e' }[/math] [math]\displaystyle{ e \cap e' = \emptyset }[/math] holds. A maximum-cardinality matching is a matching which contains a maximum number of edges. A perfect matching is a matching in which every vertex of the graph is an end-point of some element of the matching. Not every graph contains a perfect matching.