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ŭ

1. kiel grafeon kun perfekta forigada ordo
2. kiel grafeon, kies ĉiu minimuma disigilo estas plena, kaj
3. kiel komunaĵon inter subarboj de arbo.

Ciklo (nigra) kun du kordoj (verdaj). Tiu ĉi grafeo estas kordeca. Tamen, se oni forigus unu verdan lateron, la grafeo ne plu estus kordeca, ĉar en ĝi ekzistus senĥorda 4-vertica ciklo kun 3 nigraj lateroj kaj unu verda.

La artikolo estas parto de serio pri grafeoteorio.

Plej gravaj terminoj grafeo arbo subgrafeo ciklo kliko grado de vertico grado de grafeo Elektitaj klasoj de grafeoj plena grafeo plena dukolora grafeo kohera grafeo arbo grafeo dudividebla Fenda grafeo regula grafeo grafeo de Euler grafeo de Hamilton grafeo senrelifa pli... Grafeaj algoritmoj A* Bellman-Ford Dijkstry Fleury Floyd-Warshall Johnson Kruskal Prim traserĉado de grafeo – en larĝeco – en profundo plej proksima najbaro Problemoj prezentataj kiel grafeaj problemo de vojaĝisto problemo de ĉina leteristo problemo de marŝrutigado problemo de kunigado de geedzoj Aliaj kodo de Gray diagramo de Hasse kodo de Prüfer Reprezentado de grafeo Glosaro de grafeoteorio

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 Dirac (1961), ĉ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.