Fenda grafeo

En grafeoteorio, fenda grafeo estas grafeo en kiu la verticoj povas esti disdividitaj en klikon kaj sendependan aron.

La dispartigo en klikon kaj sendependan aron ne nepre estas unika; ekzemple, la vojo a-b-c estas fenda grafeo, verticoj de kiu povas esti disdividitaj en tri malsamaj manieroj:

 kliko {a, b} kaj la sendependa aro {c}
 kliko {b, c} kaj la sendependa aro {a}
 kliko {b} kaj la sendependa aro {a, c}

Fendaj grafeoj povas esti karakterigitaj per iliaj konkluditaj subgrafeoj, grafeo estas fenda se kaj nur se neniu konkludita subgrafeo estas ciklo sur kvar aŭ kvin verticoj, aŭ paro de disaj lateroj (la komplemento de 4-ciklo).

Fendaj grafeoj estis unue studitaj de Földes kaj Hammer en du paperoj en 1977, kaj sendepende prezentitaj de Tiŝkeviĉ kaj Ĉernjak en 1979.

 Rilato al aliaj grafeaj familioj 
Komplemento de fenda grafeo estas denove fenda grafeo. Alia karakterigado de fendaj grafeoj estas per komplementigo: fenda grafeo estas ĥorda grafeo kies komplemento estas ankaŭ ĥorda. Ĝuste kiel ĥordaj grafeoj estas la komunaĵaj grafeoj de subarboj de arboj, fendaj grafeoj estas la komunaĵaj grafeoj de malsamaj substeloj de steloj. Preskaŭ ĉiuj ĥordaj grafeoj estas fendaj grafeoj, kiel Bender kaj aliaj en 1985 montris; tio estas, en la limigo kiam n strebas al malfinio, la frakcio de n-verticaj ĥordaj grafeoj kiuj estas fendaj proksimiĝas al 1. Ĉar ĥordaj grafeoj estas perfektaj, tiel fendaj grafeoj estas perfektaj. La duopa fendaj grafeoj, familio de grafeoj derivitaj de fendaj grafeoj per duobligo de ĉiu vertico (tiel la kliko iĝas kontraŭkongruantan kaj la sendependa aro iĝas kongruantan), estas unu el kvin bazaj klasoj de perfektaj grafeoj de kiu ĉiuj la aliaj povas esti formitaj en la pruvo de Ĉudnovski kaj aliaj en 2006 de la forta perfekta grafea teoremo.

Grafeo estas ambaŭ fenda grafeo kaj intervala grafeo se kaj nur se ĝia komplemento estas ambaŭ fenda grafeo kaj komparebleca grafeo. La fenda komparebleca grafeo, kaj pro tio ankaŭ la fenda intervala grafeo, povas esti karakterigita per aro de tri malpermesitaj konkluditaj subgrafeoj. La fenda kungrafeo estas akurate la sojla grafeo, kaj la fenda permuta grafeo estas akurate la intervala grafeo kiu havas intervalan grafeon kiel komplemento. Fenda grafeo havas kunkoloran nombron 2.

 Maksimuma kliko kaj maksimuma sendependa aro 
Estu G esti fenda grafeo, disdividita en klikon C kaj sendependan aron I. Tiam ĉiu maksimuma kliko en fenda grafeo estas C mem, aŭ la najbaraĵo de vertico en I. Tial ĉe fenda grafeo, estas facile identigi la maksimuman klikon, kaj ankaŭ la maksimuman sendependan aron per konsidero de komplementa grafeo. En ĉiu fenda grafeo, unu el la sekvaj tri eblecoj veras:

 C estas la maksimuma kliko kaj I estas la maksimuma sendependa aro. En ĉi tiu okazo, G havas unikan dispartigon (C, I) en klikon kaj sendependan aron.
 Tie ekzistas vertico x en I tia ke C ∪ {x} estas plena. En ĉi tiu okazo, C ∪ {x} estas la maksimuma kliko kaj I estas la maksimuma sendependa aro.
 Tie ekzistas vertico x en C tia ke I ∪ {x} estas sendependa. En ĉi tiu okazo, I ∪ {x} estas la maksimuma sendependa aro kaj C estas la maksimuma kliko.

Iuj optimumigaj problemoj, inkluzivante kolorigon de grafeo, kiuj estas NP-plenaj sur pli ĝeneralaj grafeoj, estas simplaj sur fendaj grafeoj.

 Vico de gradoj de verticoj 
Tio ĉu donita grafeo estas fenda povas esti kontrolite havante nur vicon de gradoj de ĉiuj ĝiaj verticoj. Tio estas ke supozu ke du grafeoj havas la propraĵon ke, por ĉiu i, ambaŭ grafeoj havas egale multajn verticojn de grado i (verticoj kun i najbaraj lateroj); tiam aŭ ambaŭ grafeoj estas fendaj aŭ ambaŭ ne estas fendaj. Pli detale, ordigu gradojn de verticoj en n-vertica grafeo G en la ordigitan vicon d1 ≥ d2 ≥ ... ≥ dn, kaj estu m esti la plej granda valoro de i tia ke di ≥ i-1. Tiam G estas fenda grafeo se kaj nur se

En ĉi tiu okazo, la m verticoj kun la plej grandaj gradoj formas maksimuman klikon en G, kaj la ceteraj verticoj estas sendependa aro.

 Kalkulado de fendaj grafeoj 
Royle en 2000 montris ke fendaj grafeoj kun n nemarkitaj verticoj estas en reciproke unuvalora rilato kun certaj familioj de Sperner. Uzante ĉi tiun rilaton, li donis formulon por la kvanto de neizomorfiaj fendaj grafeoj de n verticoj. Ĉi tiuj kvantoj por n=1, 2, 3, ... estas

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ...

Ĉi tiu rezulto estis sendepende pruvita pli frue de Tiŝkeviĉ kaj Ĉernjak en 1990.

 Referencoj 
  - vico de kvantoj de neizomorfiaj fendaj grafeoj de n verticoj por n=1, 2, 3, ...








Kategorio:Grafeteorio