Grafeo

aro de objektoj nomataj kiel verticoj kunigitaj de ligoj nomataj kiel eĝoj aŭ lateroj
Temas pri... Ĉi tiu artikolo temas pri kunigitaj verticoj. Por informoj pri grafika prezento de funkcio, vidu la artikolon grafikaĵo.

En matematiko kaj komputiko, grafeo estas (neformale) aro da objektoj nomataj verticoj kunigitaj de ligoj nomataj eĝojlateroj. Kutime, grafeo estas prezentata kiel aro da punktoj (la verticoj) ligitaj per linioj (la eĝoj). Depende de la apliko, iuj eĝoj povas esti direktitaj.

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


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


vidi  diskuti  redakti
Nedirektita grafeo kun 6 verticoj kaj 7 lateroj

Grafeo estas baza objekto en grafeoteorio.

Difinoj redakti

Difinoj de grafeo en grafeoteorio varias en la literaturo. Jen estas unu el la konvencioj.

Nedirektita grafeo redakti

 

Nedirektita grafeografeo G estas ordigita duopo G := (V, E):

  • V estas aro de verticoj,
  • E estas aro de neorditaj paroj de verticoj, difinantaj la eĝojnliniojn.
  • La verticoj apartenantaj al eĝo estas nomataj finpunktoj, aŭ finaj verticoj de la eĝo.

V (kaj de ĉi tie E) kutime estas finia aro, kaj multaj el la konataj rezultoj ne estas veraj (aŭ estas iom malsamaj) por nefinia grafeoj, ĉar multaj el la argumentoj ne validas en la nefinia kazo.

Orientita grafeo redakti

 

Orientita grafeoG estas ordigita duopo G:=(V, A) kun

  • V, aro de verticoj,
  • A, aro de ordigitaj duopoj de verticoj, nomataj direktitaj eĝoj, arkoj, aŭ sagoj. Eĝo e = (x, y) estas konsiderata kiel direktita de x al y; y estas nomata la kapo kaj x estas nomata la vosto de la eĝo.

Miksita grafeo redakti

Miksita grafeo G estas ordita triopo G := (V,E,A) kie V, E kaj A estas difinitaj kiel pli supre.

Ecoj de grafeoj redakti

Du eĝoj de grafeo) estas nomataj najbaraj, se ili havas komunan verticon. Simile, du verticoj estas nomataj najbaraj se ili havas komunan eĝon, do ili estas kunigitaj per eĝo. Vertico kaj eĝo, kiu ligas ĝin al alia vertico, estas nomataj incidaj.

Vidu ankaŭ redakti