Vertico (grafeteorio)

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Grafeo kun 6 verticoj kaj 7 lateroj

En grafeteorio, vertico estas la fundamenta unuo el kiuj grafeoj estas formitaj: sendirekta grafeo konsistas el aro de verticoj kaj aro de lateroj (neordigitaj paroj de verticoj), kaj orientita grafeo konsistas el aro de verticoj kaj aro de arkoj (ordigitaj duopoj de verticoj). De vidpunkto de grafeteorio, vertico estas traktata kiel senpropraĵa kaj nedividebla objekto.

Vertico w estas najbara al alia vertico v se la grafeo enhavas lateron (v, w). La najbaraĵo de vertico v estas konkludita subgrafeo de la grafeo, formita per ĉiuj verticoj najbaraj al v.

La grado de vertico en grafeo estas la kvanto de lateroj incida al ĝi. Izola vertico estas vertico kun grada 0. Folia vertico estas vertico kun grado 1. En orientita grafeo, oni povas distingi la eksterengradon (kvanto de elirantaj lateroj) kaj la enengradon (kvanto de alirantaj lateroj); fonta vertico estas vertico kun enengrado 0, lavuja vertico estas vertico kun eksterengrado 0.

Grafeo estas vertico-transitiva se ĝi havas simetriojn kiuj mapas ĉiu verticon al ĉiu la alian vertico. En la ĉirkaŭteksto de grafea numerado kaj grafea izomorfio gravas distingi inter markita verticoj kaj nemarkitaj verticoj. Markita vertico estas vertica kiu estas asociita kun superflua informo kiu ebligas distingi ĝin de la alia markitaj verticoj; du grafeoj povas esti konsiderataj kiel izomorfia nur se la rilatoj inter paroj de iliaj verticaj kun egalaj markoj. Nemarkita vertico estas tiu kiu povas esti anstataŭigita per ĉiu la alia vertico nur surbaze de ĝia konekteco en la grafeo.

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]