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.

• Cydweddiad mwyaf (maximum matching), a elwir hefyd yn gydweddiad prifoledd mwyaf, yw cydweddiad sy'n cynnwys y nifer fwyaf posibl o ymylon. Efallai mai nifer o gydweddiadau mwyaf. Rhif cydweddiad $\nu (G)$ graff $G$ 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.

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 Nodyn:Math.

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

$|A\setminus B|\le 2|B\setminus A|.$

Ymhellach gwelwn fod

$|A|=|A\cap B|+|A\setminus B|\le 2|B\cap A|+2|B\setminus A|=2|B|.$

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 $A\cup B$ yw'r fertigau, ac mae ymylon {a, b} rhwng pob elfen $a\in A$ a $b\in B$ 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.