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 .

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

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

## Cyfeiriadau 
Categori:Cyfuniadeg