Kordeca grafeo

En grafeoteorio, ĥordeca grafo aŭ kordeca grafeo estas grafeo, en kiu ĉiu ciklo kun pli ol tri verticoj havas ĥordon (aŭ kordon), t.e. lateron ne apartenantan al la ciklo, kiu ligas du verticojn el la ciklo. Ekvivalente, ĉiu induktita ciklo en la grafeo estu precize 3-vertica. Oni povas priskribi kordecan grafeon ankaŭ
 kiel grafeon kun perfekta forigada ordo
 kiel grafeon, kies ĉiu minimuma disigilo estas plena, kaj
 kiel komunaĵon inter subarboj de arbo.

 Perfekta forigado kaj efika rekonado 
Perfekta forigada ordo en grafeo temas pri ordo de la verticoj tia, ke por ĉiu vertico v, v kaj la najbaroj de v sekvantaj v en la ordo faras kliko. Grafeo havas kordecon se kaj nur se ĝi havas perfektan forigadan ordon..

 Minimuma disiganto 
Grafeoteorie, verticaro disiganta estas aro da verticoj tia, ke se forigita, la grafeo iĝos disa; disiganto estas minimuma se ĝi ne havas severan subaron kiu mem estas disiganto. Laŭ teoremo de , ĉiu minimuma disiganto en kordeca grafeo estas plena; Dirac utiligis ĉi tiun propraĵon por pruvi ke kordeca grafeo estas perfekta.

 Kordecigo kaj arbolarĝo 
G estu hazarda grafeo, kordecigito de G estas kordeca grafeo, kiu enhavas G kiel subgrafeo. La arbolarĝo de G estas la nombro da verticoj en la plej granda kliko de la kordecigito kiu minimumigas la nombron. k-arbo estas grafeo tia, ke ne eblas aldoni novan lateron sen grandigi ĝian arbolarĝon trans k. Tial, k-arboj estas siaj propraj kordecigitoj, kaj estas subaro de kordecaj grafeoj. Oni ankaŭ povas difini variajn klasojn de grafeoj per kordecigo..

 Notes 

Kategorio:Grafeteorio