Kordeca grafeo

El Vikipedio, la libera enciklopedio
Jump to navigation Jump to search
Unu cirkvito (nigra) kun du kordoj (verdaj). La jena grafeo estas kordeca. Sed se oni forigas unu verdan  lateron la grafeo ne plu estus kordeca, ĉar estus unu 4-vertica ciklo kun 3 nigraj lateroj.
La artikolo estas parto de serio pri grafeteorio.




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


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 grafeteorio


vidi  diskuti  redakti

En grafeoterio, kordeca grafeo estas grafeo en kiu ĉiu ciklo kun pli ol kvar verticoj havas kordon, latero ne apartenanta al la ciklo sed ligas du verticojn el la ciklo. Ekvivalente, ĉiu induktita ciklo en la grafeo estu precize 3-vertica. Oni povas ankaŭ priskribi kordecan grafeon

  1. kiel grafeo kun perfekta forigada ordo
  2. kiel grafeo kies ĉiuj minimuma disigilo estas plena, kaj
  3. kiel komunaĵo inter subarboj de arbo.

Perfekta forigado kaj efika rekonado[redakti | redakti fonton]

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

Minimuma disiganto[redakti | redakti fonton]

Grafeteorie, 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[redakti | redakti fonton]

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

Notes[redakti | redakti fonton]

  1. Fulkerson, D. R.; Gross, O. A. (1965), "Incidence matrices and interval graphs", Pacific J. Math 15: 835–855, doi:10.2140/pjm.1965.15.835, http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572 .
  2. Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", Discrete Applied Mathematics 79 (1-3): 171–188, doi:10.1016/S0166-218X(97)00041-3 .