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,^[1] 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.^[2]

Priodweddau

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 | \leq 2| B |$ ac $| B | \leq 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

|A\setminus B|\leq 2|B\setminus A|.

Ymhellach gwelwn fod

|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.

Cymwysiadau

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

↑ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.
↑ Cameron, Kathie (1989), "Induced matchings", Discrete Applied Mathematics 24 (1–3): pp. 97–102, doi:10.1016/0166-218X(92)90275-F, MR 1011265
↑ Gallai, Tibor (1959), "Über extreme Punkt- und Kantenmengen", Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2: pp. 133–138.
↑ 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.

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

[1]

[2]

[3]

[4]