Cydweddiad (damcaniaeth graffiau)

Mewn damcaniaeth graffiau, set o ymylon heb fertigau cyffredin mewn graff yw cydweddiad neu set ymylon annibynnol. Gellir trin dod o hyd i gydweddiad mewn graff deurannol fel problem llif rhwydwaith.

Diffiniadau

golygu

Os rhoddir graff G = (V, E), mae cydweddiad M mewn G yn set o ymylon nad yw'n gyfagos a does dim ohonynt yn ddolenni; hynny yw, nid oes unrhyw ddwy ymyl yn rhannu fertig cyffredin.

Mae fertig wedi'i gydweddi (neu'n ddirlawn) os yw'n ddiweddbwynt i un o'r ymylon yn y cydweddiad. Fel arall mae'r fertig heb ei gydweddi.

Mathau:

  • Cydweddiad mwyafsymaidd (maximal matching) yw cydweddiad M o graff G nad yw'n is-set o unrhyw gydweddiad arall. Mae cydweddiad M o graff G ar y mwyafsymaidd os canlyniad ychwanegu unrhyw ymyl ychwanegol yw graff nad yw'n gydweddiad. Mae'r ffigur canlynol yn dangos enghreifftiau o gydweddiadau mwyafsymaidd (coch) mewn tri graff.
 
  • Cydweddiad mwyaf (maximum matching), a elwir hefyd yn gydweddiad prifoledd mwyaf,[1] yw cydweddiad sy'n cynnwys y nifer fwyaf posibl o ymylon. Efallai mai nifer o gydweddiadau mwyaf. Rhif cydweddiad   graff   yw maint y cydweddiad mwyaf. Mae pob cydweddiad mwyafsymaidd yn gydweddiad mwyaf, ond nid yw pob cydweddiad mwyaf yn gydweddiad mwyafsymaidd. Mae'r ffigur canlynol yn dangos enghreifftiau o gydweddiadau mwyaf (coch) mewn yr un tri graff ag uchod.
 
  • Cydweddiad cyflawn (neu berffaith, neu 1-ffactor) yw cydweddiad lle mar holl fertigau'r graff wedi'u cydweddi. Hynny yw, mae pob fertig y graff yn drawol i un ymyl yn union o'r cydweddiad. Mae pob cydweddiad cyflawn yn gydweddiad fwyaf, ac felly yn gydweddiad mwyafsymaidd. Yn y ffigur uchod, dim ond rhan (b) sy'n dangos cyfatebiad perffaith. Mae cydweddiad cyflawn hefyd yn orchudd ymyl lleiaf. Mae cydweddiad cyflawn ond yn digwydd pan fydd gan y graff nifer eilrif o fertigau.
  • Cydweddiad bron-cyflawn (neu bron-perffaith) yw cydweddiad lle ond un fertig sydd heb ei gydweddi. Gall hyn ond digwydd pan fydd gan y graff nifer od o fertigau.
  • Cydweddiad anwythedig yw cydweddiad sy'n is-graff anwythedig.[2]

Priodweddau

golygu

Mewn unrhyw graff heb fertigau ynysig, mae swm y rhif cydweddiad a'r rhif gorchudd ymyl yn hafal i nifer y fertigau.[3] Os oes cydweddiad perffaith, yna'r rhif cydweddiad a rhif y gorchudd ymyl yw |V | / 2.

Os yw A a B yn ddau gydweddiad mwyafsymaidd yna |A| ≤ 2|B| ac |B| ≤ 2|A|. I weld hyn, sylwch gall pob ymyl yn B \ A fod yn gyfagos i ddwy ymyl ar y mwyaf yn A \ B oherwydd bod A yn gydweddiad; hefyd pob ymyl yn A \ B yn gyfagos i ymyl yn B \ A oherwydd bod B yn fwyafsymaidd, felly

 

Ymhellach gwelwn fod

 

Cymwysiadau

golygu

Mae gan gydweddiadau mewn graffiau deurannol cymwysiadau mewn problemau aseinio[4]. Os oes set A o dasgau a set B o weithwyr, gallwn gynhyrchu graff deurannol, lle elfennau   yw'r fertigau, ac mae ymylon {a, b} rhwng pob elfen   a   os yw'r gweithiwr b yn gallu gwneud tasg a. Mae cydweddiad yn y graff hwn yn dynodi un ffordd o aseinio'r tasgau A i'r gweithwyr B. Mae canfod cydweddiad cyflawn yn golygu bydd gan bob gweithiwr tasg a pob tasg gweithiwr, a chydweddiad mwyaf yw'r aseiniad gorau posib. Mae hwn yn briodol am nifer o broblemau, er enghraifft aseinio gwaed i gleifion, neu drefnu gemau chwaraeon.

Cyfeiriadau

golygu
  1. Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.
  2. Cameron, Kathie (1989), "Induced matchings", Discrete Applied Mathematics 24 (1–3): pp. 97–102, doi:10.1016/0166-218X(92)90275-F, MR 1011265
  3. Gallai, Tibor (1959), "Über extreme Punkt- und Kantenmengen", Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2: pp. 133–138.
  4. Burkard, Rainer E. (2009). Assignment problems. Dell'Amico, Mauro., Martello, Silvano., Society for Industrial and Applied Mathematics. Philadelphia, Pa.: Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104). ISBN 978-0-89871-775-4. OCLC 693952745.