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 
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.

 File:Maximal-matching.svg

 Cydweddiad mwyaf (maximum matching), a elwir hefyd yn gydweddiad prifoledd mwyaf,Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5. 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.

 File:Maximum-matching-labels.svg

 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.

 Priodweddau 
Mewn unrhyw graff heb fertigau ynysig, mae swm y rhif cydweddiad a'r rhif gorchudd ymyl yn hafal i nifer y fertigau.. Os oes cydweddiad perffaith, yna'r rhif cydweddiad a rhif y gorchudd ymyl yw .

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



Ymhellach gwelwn fod



 Cymwysiadau 
Mae gan gydweddiadau mewn graffiau deurannol cymwysiadau mewn problemau aseinio. 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 

Categori:Cyfuniadeg