Diferite formulări ale problemelor corelările
1.Zadacha despre nunti. Să presupunem că avem un set finit de băieți, fiecare dintre care este familiarizat cu un subset al unui set finit de fete. În cazul în care, toți băieții se pot căsători, astfel încât fiecare căsătorit cu o prietenă?
2. transversal sau sistem de reprezentanți distincte (PSA). Fie S = Si. Sm> - familie la sfârșitul subseturi de subseturi E. Sk nu sunt neapărat diferite și se pot suprapune. Sistemul de diferiți reprezentanți ai familiei S (sau S într-o familie transversală) este orice subset C = CI. cm> de m elemente ale E astfel încât. În cazul în care, există o transversală?
Toate elementele setului sunt diferite, prin urmare, „sistemul de reprezentanți distincte.“ Nume
Exemple problemă RPC. mulți profesori care lucrează în universități, cărora le place să înființeze comisii. Odată ce comisiile pluralitate Prof. formate, ele decid să formeze comitete (CC). QC este compus din reprezentanți ai prezidarea comisiilor ordinare. Se aplică următoarele reguli:
a) fiecare comitet are exact un reprezentant în QC;
b) nici unul din CC poate să nu fie reprezentative pentru mai mult de un comitet.
Întrebarea este - este posibil ca fiecare comisie să aleagă un scaun, astfel încât nici un profesor nu a fost presedinte de mai mult de un comitet.
3. potrivire potrivire perfectă (sau set independent de margini) este setul de muchii, în care nu există două nervuri adiacente.
Fie G (V1 V2 E ..) - graf bipartit. potrivire perfectă de la V1 la V2 este numit de potrivire, acoperind vârfuri V1. În cazul în care, există o potrivire perfectă de la V1 la V2?
În general, obiectivul 1, 2 și 3 - este una și aceeași sarcină. Într-adevăr, problema se reduce la 1 3 după cum urmează. V1 - mulți tineri, V2 - multe fete margini - băieți fete. În acest caz, o potrivire perfecta - setul dorit de nunti. Sarcina 2 se reduce la 3 după cum urmează. Fie V1. = S, V2. = E, nervura (Sk, ei) există în cazul în care. În acest caz, o potrivire perfectă - transversală necesară. Astfel, sarcina 1. 2 și 3 au un răspuns general: dacă și numai dacă
care este stabilită prin următoarea teoremă.
Fie G (V. E) - grafic, A - subset de vârfuri V, adică Atunci să-i fie notată cu - mulțimea tuturor nodurilor adiacente noduri A.
Teorema (Hall). Fie G (V1 V2 E ..) - graf bipartit. potrivire perfectă a V1 V2 există dacă și numai dacă ().
Dovada. Să presupunem că există o potrivire perfectă a V1 V2. Apoi vine | A | noduri V2. asociat la înălțimile mulțimii A, și poate altceva. Astfel, | A | .
Adăugați noul G două vârfuri u și v. astfel încât partea de sus și adiacente la toate nodurile de V1. iar vertex v este adiacent la toate nodurile V2. potrivire perfectă de la V1 la V2 dacă și numai dacă există | V1 | vertex-disjunctă simplu (u, v) -chains (Fig. 37). Este clar că | P (. U v) | (Deoarece V1 partajat nodurile u și v).
Prin teorema lui Menger max | P (și, v) | = Min | R (și, v) | = | R |, unde R - setul cel mai mic dintre nodurile de separare set u și v. Avem. Vom arăta că. Să ,,. Apoi. Într-adevăr, în cazul în care, ar exista un "sens giratoriu" cale (și, v1, v2, v) (vezi. Fig. 37) și S nu ar fi separarea stabilită pentru u și v. Avem. În consecință ,.
Fig. 37. dovada teoremei lui Hall